Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function

References

• Ahmed S, King AJ, Parija G (2003) A multi-stage stochastic integer programming approach for capacity expansion under uncertainty. J. Global Optim. 26(1):3–24.Crossref, Google Scholar
• 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
• Alonso-Ayuso A, Escudero LF, Garín A, Ortuño MT, Pérez G (2003) An approach for strategic supply chain planning under uncertainty based on stochastic 0-1 programming. J. Global Optim. 26(1):97–124.Crossref, Google Scholar
• Alonso-Ayuso A, Escudero LF, Ortuño MT (2000) A stochastic 0-1 program based approach for the air traffic flow management problem. Eur. J. Oper. Res. 120(1):47–62.Crossref, Google Scholar
• Applegate DL, Bixby RE, Chvatal V, Cook WJ (2011) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Beale EML (1955) On minimizing a convex function subject to linear inequalities. J. Royal Statist. Soc. Ser. B Methodology 17(2):173–184.Google Scholar
• Beheshti B, Özaltın OY, Zare MH, Prokopyev OA (2015) Exact solution approach for a class of nonlinear bilevel knapsack problems. J. Global Optim. 61(2):291–310.Crossref, Google Scholar
• Birge JR (1997) State-of-the-art-survey stochastic programming: Computation and applications. INFORMS J. Comput. 9(2):111–133.Link, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar
• Bixby RE (2012) A brief history of linear and mixed-integer programming computation. Documenta Mathematica Extra Volume: Optimization Stories, 107–121.Google Scholar
• Blair CE (1995) A closed-form representation of mixed-integer program value functions. Math. Programming 71(2):127–136.Crossref, Google Scholar
• Blair CE, Jeroslow RG (1982) The value function of an integer program. Math. Programming 23(1):237–273.Crossref, Google Scholar
• Blair CE, Jeroslow RG (1984) Constructive characterizations of the value-function of a mixed-integer program: I. Discrete Appl. Math. 9(3):217–233.Crossref, Google Scholar
• Blair CE, Jeroslow RG (1985) Constructive characterizations of the value function of a mixed-integer program: II. Discrete Appl. Math. 10(3):227–240.Crossref, Google Scholar
• Bodur M, Dash S, Günlük O, Luedtke J (2017) Strengthened Benders cuts for stochastic integer programs with continuous recourse. INFORMS J. Comput. 29(1):77–91.Link, Google Scholar
• Brotcorne L, Hanafi S, Raid M (2009) A dynamic programming algorithm for the bilevel knapsack problem. Oper. Res. Lett. 37(3):215–218.Crossref, Google Scholar
• Brotcorne L, Hanafi S, Raid M (2013) One-level reformulation of the bilevel knapsack problem using dynamic programming. Discrete Optim. 10(1):1–10.Crossref, Google Scholar
• Calvete HI, Galé C (2007) Linear bilevel multi-follower programming with independent followers. J. Global Optim. 39(3):409–417.Crossref, Google Scholar
• Candler W, Townsley R (1982) A linear two-level programming problem. Comput. Oper. Res. 9(1):59–76.Crossref, Google Scholar
• Carøe CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1):37–45.Crossref, Google Scholar
• Carøe CC, Tind J (1997) A cutting-plane approach to mixed 0-1 stochastic integer programs. Eur. J. Oper. Res. 101(2):306–316.Crossref, Google Scholar
• Carøe CC, Tind J (1998) L-shaped decomposition of two-stage stochastic programs with integer recourse. Math. Programming 83(1):451–464.Crossref, Google Scholar
• Colson B, Marcotte P, Savard G (2007) An overview of bilevel optimization. Ann. Oper. Res. 153(1):235–256.Crossref, Google Scholar
• Constantin I, Florian M (1995) Optimizing frequencies in a transit network: A nonlinear bilevel programming approach. Internat. Trans. Oper. Res. 2(2):149–164.Crossref, Google Scholar
• Cook W, Gerards AMH, Schrijver A, Tardos É (1986) Sensitivity theorems in integer linear programming. Math. Programming 34(3):251–264.Crossref, Google Scholar
• Côté J, Marcotte P, Savard G (2003) A bilevel modelling approach to pricing and fare optimisation in the airline industry. J. Revenue Pricing Management 2(1):23–36.Crossref, Google Scholar
• Dantzig GB (1955) Linear programming under uncertainty. Management Sci. 1(3–4):197–206.Link, Google Scholar
• Dawande MW, Hooker JN (2000) Inference-based sensitivity analysis for mixed integer/linear programming. Oper. Res. 48(4):623–634.Link, Google Scholar
• DeNegre ST, Ralphs TK (2009) A branch-and-cut algorithm for integer bilevel linear programs. Chinneck JW, Kristjansson B, Saltzman MJ, eds. Operations Research and Cyber-Infrastructure, (Springer US, Boston), 65–78.Crossref, Google Scholar
• Gade D, Küçükyavuz S, Sen S (2012) Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs. Math. Programming 144(1–2):1–26.Google Scholar
• Gilmore PC, Gomory RE (1966) The theory and computation of knapsack functions. Oper. Res. 14(6):1045–1074.Link, Google Scholar
• Greenberg HJ (1998) Advances in computational and stochastic optimization, logic programming, and heuristic search. Greenberg HJ, ed. An Annotated Bibliography for Post-Solution Analysis in Mixed Integer Programming and Combinatorial Optimization, Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search (Kluwer Academic Publishers, Norwell, MA), 97–147.Google Scholar
• Güzelsoy M (2009) Dual methods in mixed integer linear programming. PhD thesis, Lehigh University, Bethlehem, PA.Google Scholar
• Güzelsoy M, Ralphs TK (2007) Duality for mixed-integer linear programs. Internat. J. Oper. Res. 4(3):118–137.Google Scholar
• Hansen P, Jaumard B, Savard G (1992) New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Statist. Comput. 13(5):1194–1217.Crossref, Google Scholar
• Hassanzadeh A, Ralphs TK (2014) A generalization of Benders’ algorithm for two-stage stochastic optimization problems with mixed integer recourse. Accessed July 1, 2018, http://www.optimization-online.org/DB_FILE/2014/08/4474.pdf.Google Scholar
• Hearn DW, Ramana MV (1998) Solving congestion toll pricing models. Marcotte P, Nguyen S, eds. Equilibrium and Advanced Transportation Modelling (Springer US, Boston), 109–124.Crossref, Google Scholar
• Huang K, Ahmed S (2010) A stochastic programming approach for planning horizons of infinite horizon capacity planning problems. Eur. J. Oper. Res. 200(1):74–84.Crossref, Google Scholar
• Jeroslow RG (1985) The polynomial hierarchy and a simple model for competitive analysis. Math. Programming 32(2):146–164.Crossref, Google Scholar
• Keller B, Bayraksan G (2012) Disjunctive decomposition for two-stage stochastic mixed-binary programs with generalized upper bound constraints. INFORMS J. Comput. 24(1):172–186.Link, 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–3):275–296.Crossref, Google Scholar
• Küçükyavuz S, Sen S (2017) An introduction to two-stage stochastic mixed-integer programming. Leading developments from INFORMS communities. TutORials Oper. Res. (INFORMS, Catonsville, MD), 1–27.Google Scholar
• Lamperski JB, Schaefer AJ (2015) A polyhedral characterization of the inverse-feasible region of a mixed-integer program. Oper. Res. Lett. 43(6):575–578.Crossref, Google Scholar
• Laporte G, Louveaux F (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3):133–142.Crossref, Google Scholar
• Lim C, Smith JC (2007) Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39(1):15–26.Crossref, Google Scholar
• Lodi A, Ralphs TK, Woeginger G (2014) Bilevel programming and the separation problem. Math. Programming 146(1):437–458.Crossref, Google Scholar
• Loridan P, Morgan J (1996) Weak via strong Stackelberg problem: New results. J. Global Optim. 8(3):263–287.Crossref, Google Scholar
• Louveaux FV, van der Vlerk MH (1993) Stochastic programming with simple integer recourse. Math. Programming 61(1):301–325.Crossref, Google Scholar
• Lu J, Shi C, Zhang G (2006) On bilevel multi-follower decision making: General framework and solutions. Inform. Sci. 176(11):1607–1627.Crossref, Google Scholar
• Lulli G, Sen S (2004) A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems. Management Sci. 50(6):786–796.Link, Google Scholar
• Martin RK (1999) Large Scale Linear and Integer Optimization: A Unified Approach (Springer Science & Business Media, New York).Crossref, Google Scholar
• Mersha AG, Dempe S (2006) Linear bilevel programming with upper level constraints depending on the lower level solution. Appl. Math. Comput. 180(1):247–254.Google Scholar
• Moore JT, Bard JF (1990) The mixed integer linear bilevel programming problem. Oper. Res. 38(5):911–921.Link, Google Scholar
• Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization (Wiley-Interscience, New York).Crossref, Google Scholar
• Ntaimo L (2010) Disjunctive decomposition for two-stage stochastic mixed-binary programs with random recourse. Oper. Res. 58(1):229–243.Link, Google Scholar
• Ntaimo L (2013) Fenchel decomposition for stochastic mixed-integer programming. J. Global Optim. 55(1):141–163.Crossref, Google Scholar
• Ntaimo L, Sen S (2008) A comparative study of decomposition algorithms for stochastic combinatorial optimization. Comput. Optim. Appl. 40(3):299–319.Crossref, Google Scholar
• Özaltın OY, Prokopyev OA, Schaefer AJ (2010) The bilevel knapsack problem with stochastic right-hand sides. Oper. Res. Lett. 38(4):328–333.Crossref, 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
• Özaltın OY, Prokopyev OA, Schaefer AJ, Roberts MS (2011) Optimizing the societal benefits of the annual influenza vaccine: A stochastic programming approach. Oper. Res. 59(5):1131–1143.Link, Google Scholar
• Qi Y, Sen S (2017) The ancestral Benders’ cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming. Math. Programming 161(1):193–235.Crossref, Google Scholar
• Ralphs T, Adams E (2016) Computational optimization research at Lehigh: Bilevel optimization problem library. Accessed July 1, 2018, https://coral.ise.lehigh.edu/data-sets/bilevel-instances.Google Scholar
• Ryan K, Rajan D, Ahmed S (2015) Scenario decomposition for 0-1 stochastic programs: Improvements and asynchronous implementation. Accessed July 1, 2018, http://www.optimization-online.org/DB_FILE/2015/11/5201.pdf.Google Scholar
• Schrage L, Wolsey L (1985) Sensitivity analysis for branch and bound integer programming. Oper. Res. 33(5):1008–1023.Link, 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(1–3):229–252.Crossref, Google Scholar
• Sen S (2005) Algorithms for stochastic mixed-integer programming models. Aardal K, Nemhauser GL, Weismantel R, eds. Discrete Optimization, Handbooks in Operations Research and Management Science, vol. 12 (Elsevier, New York), 515–558.Crossref, Google Scholar
• Sen S, Higle LJ (2005) The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Math. Programming 104(1):1–20.Crossref, Google Scholar
• Sen S, Sherali HD (2006) Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Math. Programming 106(2):203–223.Crossref, Google Scholar
• Sherali H, Fraticelli B (2002) A modification of Benders’ decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse. J. Global Optim. 22(1–4):319–342.Crossref, Google Scholar
• Sherali HD, Smith JC (2009) Two-stage stochastic hierarchical multiple risk problems: Models and algorithms. Math. Programming 120(2):403–427.Crossref, Google Scholar
• Sherali HD, Soyster AL, Murphy FH (1983) Stackelberg-Nash-Cournot equilibria: Characterizations and computations. Oper. Res. 31(2):253–276.Link, Google Scholar
• Sherali HD, Zhu X (2006) On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables. Math. Programming 108(2):597–616.Crossref, Google Scholar
• Shylo OV, Prokopyev OA, Schaefer AJ (2012) Stochastic operating room scheduling for high-volume specialties under block booking. INFORMS J. Comput. 25(4):682–692.Link, Google Scholar
• Sturmfels B, Thomas RR (1997) Variation of cost functions in integer programming. Math. Programming 77(2):357–387.Crossref, Google Scholar
• Tahernejad SA, DeNegre ST, Ralphs TK (2016) A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Accessed July 1, 2018, http://www.optimization-online.org/DB_FILE/2017/04/5977.pdf.Google Scholar
• Tang Y, Richard JP, Smith JC (2016) A class of algorithms for mixed-integer bilevel min–max optimization. J. Global Optim. 66(2):225–262.Crossref, 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
• Wang H, Horng J (1996a) Directed perturbation analysis of an integer program. J. Math. Anal. Appl. 201(2):447–460.Crossref, Google Scholar
• Wang H, Horng J (1996b) Structural approach to parametric analysis of an IP on the case of the right-hand side. Eur. J. Oper. Res. 92(1):148–156.Crossref, Google Scholar
• Williams HP (1996) Constructing the value function for an integer linear programme over a cone. Comput. Optim. Appl. 6(1):15–26.Crossref, Google Scholar
• Wolsey LA (1981) Integer programming duality: Price functions and sensitivity analysis. Math. Programming 20(1):173–195.Crossref, Google Scholar
• Wu H, Küçükyavuz S (2018) A two-stage stochastic programming approach for influence maximization in social networks. Comput. Optim. Appl. 69(3):563–595.Crossref, Google Scholar
• Xu P, Wang L (2014) An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Comput. Oper. Res. 41:309–318.Crossref, Google Scholar
• Yen JW, Birge JR (2006) A stochastic programming approach to the airline crew scheduling problem. Transportation Sci. 40(1):3–14.Link, Google Scholar
• Yuan Y, Sen S (2009) Enhanced cut generation methods for decomposition-based branch and cut for two-stage stochastic mixed-integer programs. INFORMS J. Comput. 21(3):480–487.Link, Google Scholar
• Zheng Y, Zhu Z, Yuan L (2016) Partially-shared pessimistic bilevel multi-follower programming: Concept, algorithm, and application. J. Inequalities Appl. 2016(1):15.Crossref, Google Scholar
• Zou J, Ahmed S, Sun A (2016) Partially adaptive stochastic optimization for electric power generation expansion planning. Accessed July 1, 2018, http://www.optimization-online.org/DB_FILE/2015/01/4721.pdf.Google Scholar