Single-ratio fractional integer programs with stochastic right-hand sides

ABSTRACT

We present an equivalent value function reformulation for a class of single-ratio Fractional Integer Programs (FIPs) with stochastic right-hand sides and propose a two-phase solution approach. The first phase constructs the value functions of FIPs in both stages. The second phase solves the reformulation using a global branch-and-bound algorithm or a level-set approach. We derive some basic properties of the value functions of FIPs and utilize them in our algorithms. We show that in certain cases our approach can solve instances whose extensive forms have the same order of magnitude as the largest stochastic quadratic integer programs solved in the literature.

KEYWORDS:

• Fractional integer programming
• stochastic integer programming
• value functions
• superadditive duality

Funding

This research is partially supported by National Science Foundation Grant CMMI-1436177.

Additional information

Notes on contributors

Junlong Zhang

Junlong Zhang is currently a Ph.D. student in the Edward P. Fitts Department of Industrial & Systems Engineering at North Carolina State University. He received his bachelor’s degree in Automation from Northwestern Polytechnic University, China, and a master’s degree in Transportation from The Hong Kong Polytechnic University. His research interests are in stochastic programming and bi-level programming and their applications in transportation, logistics, and health care.

Osman Y. Özaltın

Osman Y. Özaltın is an Assistant Professor in the Edward P. Fitts Department of Industrial and Systems Engineering and a member of the Personalized Medicine Faculty Cluster at the North Carolina State University. He received his M.S. and Ph.D. degrees in Industrial Engineering from the University of Pittsburgh. His bachelor’s degree is in Industrial Engineering from Bogazici University, Turkey. His research interests span theoretical, computational, and applied aspects of mathematical programming, focusing on hierarchical optimization problems arising in public health, personalized medical decision making, and healthcare delivery. His methods include integer programming, combinatorial optimization, stochastic programming, bi-level programming, and quadratic programming.