Construction of Value Functions of Integer Programs with Finite Domain

References

• Ahmed S, Tawarmalani M, Sahinidis NV (2004) A finite branch-and-bound algorithm for two-stage stochastic integer programs. Math. Programming 100(2):355–377.Crossref, Google Scholar
• Ajayi T, Thomas C, Schaefer AJ (2022) The gap function: Evaluating integer programming models over multiple right-hand sides. Oper. Res. 70(2):1259–1270.Link, Google Scholar
• Alfant RM, Ajayi T, Schaefer AJ (2023) Evaluating mixed-integer programming models over multiple right-hand sides. Oper. Res. Lett.. 51(4):414–420.Crossref, Google Scholar
• Antley E (2021) Integrated value function global optimization approaches for two-stage stochastic programs. Unpublished PhD thesis, Rice University, Houston.Google Scholar
• Bansal A, Berg BP, Huang YL (2021) A value function-based approach for robust surgery planning. Comput. Oper. Res. 132:105313.Crossref, Google Scholar
• Basu A, Ryan CT, Sankaranarayanan S (2021) Mixed-integer bilevel representability. Math. Programming 185(1):163–197.Crossref, Google Scholar
• Bertsimas D, Kim CW (2023) A prescriptive machine learning approach to mixed-integer convex optimization. INFORMS J. Comput. 35(6):1225–1241.Link, Google Scholar
• Bertsimas D, Stellato B (2022) Online mixed-integer optimization in milliseconds. INFORMS J. Comput. 34(4):2229–2248.Link, Google Scholar
• Blair C (1995) A closed-form representation of mixed-integer program value functions. Math. Programming 71(2):127–136.Crossref, Google Scholar
• Blair CE, Jeroslow RG (1977) The value function of a mixed integer program: I. Discrete Math. 19(2):121–138.Crossref, Google Scholar
• Blair CE, Jeroslow RG (1979) The value function of a mixed integer program: II. Discrete Math. 25(1):7–19.Crossref, Google Scholar
• Blair CE, Jeroslow RG (1982) The value function of an integer program. Math. Programming 23(1):237–273.Crossref, Google Scholar
• Brown S, Zhang W, Ajayi T, Schaefer AJ (2021) A Gilmore-Gomory construction of integer programming value functions. Oper. Res. Lett. 49(4):522–529.Crossref, Google Scholar
• Dempe S, Kue FM (2017) Solving discrete linear bilevel optimization problems using the optimal value reformulation. J. Global Optim. 68(2):255–277.Crossref, Google Scholar
• Fallah S, Ralphs TK, Boland NL (2024) On the relationship between the value function and the efficient frontier of a mixed integer linear optimization problem. Math. Methods Oper. Res. 100(1):175–220.Crossref, Google Scholar
• Guzelsoy M, Ralphs TK (2007) Duality for mixed-integer linear programs. Internat. J. Oper. Res. 4(3):118–137.Google Scholar
• Huang Y, Zhang J (2025) Construction of value functions of integer programs with finite domain. https://doi.org/10.1287/ijoc.2024.0757.cd, https://github.com/INFORMSJoC/2024.0757.Google Scholar
• Kong N, Schaefer AJ, Hunsaker B (2006) Two-stage integer programs with stochastic right-hand sides: A superadditive dual approach. Math. Programming 108(2):275–296.Crossref, Google Scholar
• Lozano L, Smith JC (2017) A value-function-based exact approach for the bilevel mixed-integer programming problem. Oper. Res. 65(3):768–786.Link, Google Scholar
• Nemhauser GL, Wolsey LA (1999) Integer and Combinatorial Optimization (John Wiley & Sons, New York).Google Scholar
• Özaltın OY, Prokopyev OA, Schaefer AJ (2012) Two-stage quadratic integer programs with stochastic right-hand sides. Math. Programming 133(1–2):121–158.Crossref, Google Scholar
• Ralphs TK, Hassanzadeh A (2014) On the value function of a mixed integer linear optimization problem and an algorithm for its construction. COR@L Technical Report 14T–004, Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA.Google Scholar
• Schultz R, Stougie L, Van Der Vlerk MH (1998) Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis. Math. Programming 83:229–252.Crossref, Google Scholar
• Tahernejad S, Ralphs TK, DeNegre ST (2020) A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Math. Programming Comput. 12(4):529–568.Crossref, Google Scholar
• Tavaslıoğlu O, Prokopyev OA, Schaefer AJ (2019) Solving stochastic and bilevel mixed-integer programs via a generalized value function. Oper. Res. 67(6):1659–1677.Link, Google Scholar
• Trapp AC, Prokopyev OA (2015) A note on constraint aggregation and value functions for two-stage stochastic integer programs. Discrete Optim. 15:37–45.Crossref, Google Scholar
• Trapp AC, Prokopyev OA, Schaefer AJ (2013) On a level-set characterization of the value function of an integer program and its application to stochastic programming. Oper. Res. 61(2):498–511.Link, Google Scholar
• Wolsey LA (1981) Integer programming duality: Price functions and sensitivity analysis. Math. Programming 20(1):173–195.Crossref, Google Scholar
• Zenarosa GL, Prokopyev OA, Pasiliao EL (2021) On exact solution approaches for bilevel quadratic 0–1 knapsack problem. Ann. Oper. Res. 298(1–2):555–572.Crossref, Google Scholar
• Zhang J, Özaltın OY (2017) Single-ratio fractional integer programs with stochastic right-hand sides. IISE Trans. 49(6):579–592.Crossref, Google Scholar
• Zhang J, Özaltın OY (2021) Bilevel integer programs with stochastic right-hand sides. INFORMS J. Comput. 33(4):1644–1660.Abstract, Google Scholar
• Zhang J, Özaltın OY, Trapp AC (2025) Solving a class of two-stage stochastic nonlinear integer programs using value functions. J. Global Optim. 91(1):129–153.Crossref, Google Scholar