Network-Based Approximate Linear Programming for Discrete Optimization

References

• Achterberg T, Bixby RE, Gu Z, Rothberg E, Weninger D (2019) Presolve reductions in mixed integer programming. INFORMS J. Comput. Forthcoming.Google Scholar
• Adelman D (2004) A price-directed approach to stochastic inventory/routing. Oper. Res. 52(4):499–514.Link, Google Scholar
• Adelman D, Barz C (2014) A unifying approximate dynamic programming model for the economic lot scheduling problem. Math. Oper. Res. 39(2):374–402.Link, Google Scholar
• Antoniadis A, Huang CC, Ott S, Verschae J (2013) How to pack your items when you have to buy your knapsack. Chatterjee K, Sgall J, eds. Proc. 38th Internat. Sympos. Math. Foundations Comput. Sci. (Springer, Berlin, Heidelberg), 62–73.Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2012) New state-space relaxations for solving the traveling salesman problem with time windows. INFORMS J. Comput. 24(3):356–371.Link, Google Scholar
• Bean JC, Birge JR, Smith RL (1987) Aggregation in dynamic programming. Oper. Res. 35(2):215–220.Link, Google Scholar
• Bergman D, Cire A (2018) Nonlinear discrete optimization with state space decompositions. Management Sci. 64(10):4700–4720.Link, Google Scholar
• Bergman D, Cire A, van Hoeve WJ, Hooker J (2016) Decision Diagrams for Optimization, Artificial Intelligence: Foundations, Theory, and Algorithms (Springer, Cham, Switzerland).Google Scholar
• Bertsekas DP (2012) Dynamic Programming and Optimal Control: Approximate Dynamic Programming, vol. 2, 4th ed. (Athena Scientific, Nashua, NH).Google Scholar
• Bertsekas DP (2017) Dynamic Programming and Optimal Control, vol. 1, 4th ed. (Athena Scientific, Belmont, MA).Google Scholar
• Bertsimas D, Demir R (2002) An approximate dynamic programming approach to multidimensional knapsack problems. Management Sci. 48(4):550–565.Link, Google Scholar
• Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization, vol. 6 (Athena Scientific, Charlestown, MA).Google Scholar
• Blado D, Hu W, Toriello A (2016) Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes. SIAM J. Optim. 26(3):1625–1648.Crossref, Google Scholar
• Bouarab H, El Hallaoui I, Metrane A, Soumis F (2017) Dynamic constraint and variable aggregation in column generation. Eur. J. Oper. Res. 262(3):835–850.Crossref, Google Scholar
• Büyüktahtakın IE (2011) Dynamic programming via linear programming. Cochran JJ, Cox Jr LA, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Castro PM, Grossmann IE, Veldhuizen P, Esplin D (2014) Optimal maintenance scheduling of a gas engine power plant using generalized disjunctive programming. AIChE J. 60(6):2083–2097.Crossref, Google Scholar
• Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145–164.Crossref, Google Scholar
• Cire AA, van Hoeve WJ (2013) Multivalued decision diagrams for sequencing problems. Oper. Res. 61(6):1411–1428.Link, Google Scholar
• Clautiaux F, Hanafi S, Macedo R, Voge MÉ, Alves C (2017) Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints. Eur. J. Oper. Res. 258(2):467–477.Crossref, Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2010) Extended formulations in combinatorial optimization. 4OR 8(1):1–48.Google Scholar
• Danubio J, Hassen P (2017) Shopper path to purchase: The three biggest decisions you can influence. Accessed November 14, 2019, https://www.slideshare.net/dkcvoom/shopper-path-to-purchase-three-biggest-decisions-you-can-influence.Google Scholar
• de Farias DP, Van Roy B (2003) The linear programming approach to approximate dynamic programming. Oper. Res. 51(6):850–865.Link, Google Scholar
• de Farias DP, Van Roy B (2004) On constraint sampling for the linear programming approach to approximate dynamic programming. Math. Oper. Res. 29(3):462–478.Link, Google Scholar
• Demir R (2000) An approximate dynamic programming approach to discrete optimization. Unpublished doctoral dissertation, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Desai VV, Farias VF, Moallemi CC (2012) Approximate dynamic programming via a smoothed linear program. Oper. Res. 60(3):655–674.Link, Google Scholar
• Drozdowski M, Jaehn F, Paszkowski R (2017) Scheduling position-dependent maintenance operations. Oper. Res. 65(6):1657–1677.Link, Google Scholar
• Elhallaoui I, Metrane A, Soumis F, Desaulniers G (2010) Multi-phase dynamic constraint aggregation for set partitioning type problems. Math. Programming 123(2):345–370.Crossref, Google Scholar
• Eppen GD, Martin RK (1987) Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper. Res. 35(6):832–848.Link, Google Scholar
• Fomeni FD, Letchford AN (2014) A dynamic programming heuristic for the quadratic knapsack problem. INFORMS J. Comput. 26(1):173–182.Link, Google Scholar
• Frangioni A (2002) Generalized bundle methods. SIAM J. Optim. 13(1):117–156.Crossref, Google Scholar
• Fukasawa R, Barboza AS, Toriello A (2016) On the strength of approximate linear programming relaxations for the traveling salesman problem. Working paper, Georgia Institute of Technology, Atlanta.Google Scholar
• Garcia de la Banda M, Stuckey PJ, Chu G (2011) Solving talent scheduling with dynamic programming. INFORMS J. Comput. 23(1):120–137.Link, Google Scholar
• Gouveia L (1998) Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput. 10(2):180–188.Link, Google Scholar
• Gurobi Optimization L (2017) Gurobi optimizer reference manual. Accessed December 3, 2017, http://www.gurobi.com.Google Scholar
• Hojjat A, Turner J, Cetintas S, Yang J (2017) A unified framework for the scheduling of guaranteed targeted display advertising under reach and frequency requirements. Oper. Res. 65(2):289–313.Link, Google Scholar
• Karp RM, Held M (1967) Finite-state processes and dynamic programming. SIAM J. Appl. Math. 15(3):693–718.Crossref, Google Scholar
• Kocuk B, Jeon H, Dey SS, Linderoth J, Luedtke J, Sun XA (2016) A cycle-based formulation and valid inequalities for DC power transmission problems with switching. Oper. Res. 64(4):922–938.Link, Google Scholar
• Lima RM, Grossmann IE (2017) On the solution of nonconvex cardinality Boolean quadratic programming problems: A computational study. Comput. Optim. Appl. 66(1):1–37.Crossref, Google Scholar
• Lin Q, Nadarajah S, Soheili N (2019) Revisiting approximate linear programming using a saddle point based reformulation and root finding solution approach. Management Sci. Forthcoming.Google Scholar
• Martin RK (1987) Generating alternative mixed-integer programming models using variable redefinition. Oper. Res. 35(6):820–831.Link, Google Scholar
• Mingozzi A, Bianco L, Ricciardelli S (1997) Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints. Oper. Res. 45(3):365–377.Link, Google Scholar
• Nadarajah S, Margot F, Secomandi N (2015) Relaxations of approximate linear programs for the real option management of commodity storage. Management Sci. 61(12):3054–3076.Link, Google Scholar
• Otto A, Li X, Pesch E (2017) Two-way bounded dynamic programming approach for operations planning in transshipment yards. Transportation Sci. 51(1):325–342.Link, Google Scholar
• Powell WB (2007) Approximate Dynamic Programming: Solving the Curses of Dimensionality (Wiley-Interscience, Hoboken, NJ).Crossref, Google Scholar
• Rogers DF, Plante RD, Wong RT, Evans JR (1991) Aggregation and disaggregation techniques and methodology in optimization. Oper. Res. 39(4):553–582.Link, Google Scholar
• Rudin C, Passonneau RJ, Radeva A, Dutta H, Ierome S, Isaac D (2010) A process for predicting manhole events in Manhattan. Machine Learn. 80(1):1–31.Crossref, Google Scholar
• Sadykov R, Vanderbeck F (2013) Column generation for extended formulations. Eur. J. Comput. Optim. 1(1):81–115.Crossref, Google Scholar
• Schweitzer PJ, Seidmann A (1985) Generalized polynomial approximations in Markovian decision processes. J. Math. Anal. Appl. 110(2):568–582.Crossref, Google Scholar
• Tarjan RE, Yannakakis M (1984) Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3):566–579.Crossref, Google Scholar
• Teo CP, Shu J (2004) Warehouse-retailer network design problem. Oper. Res. 52(3):396–408.Link, Google Scholar
• Tilk C, Irnich S (2017) Dynamic programming for the minimum tour duration problem. Transportation Sci. 51(2):549–565.Link, Google Scholar
• Tong C, Topaloglu H (2014) On the approximate linear programming approach for network revenue management problems. INFORMS J. Comput. 26(1):121–134.Link, Google Scholar
• Toriello A (2014) Optimal toll design: A lower bound framework for the asymmetric traveling salesman problem. Math. Programming 144(1–2):247–264.Crossref, Google Scholar
• Toriello A, Haskell WB, Poremba M (2014) A dynamic traveling salesman problem with stochastic arc costs. Oper. Res. 62(5):1107–1125.Link, Google Scholar
• Tulabandhula T, Rudin C, Jaillet P (2011) The Machine Learning and Traveling Repairman Problem (Springer, Berlin, Heidelberg), 262–276.Crossref, Google Scholar
• Vossen T, Zhang D (2015) Reductions of approximate linear programs for network revenue management. Oper. Res. 63(6):1352–1371.Link, Google Scholar