×

Mixed integer linear programming formulation techniques. (English) Zbl 1338.90277

Summary: A wide range of problems can be modeled as Mixed Integer Linear Programming (MIP) problems using standard formulation techniques. However, in some cases the resulting MIP can be either too weak or too large to be effectively solved by state of the art solvers. In this survey we review advanced MIP formulation techniques that result in stronger and/or smaller formulations for a wide class of problems.

MSC:

90C11 Mixed integer programming
90C10 Integer programming

Software:

CPLEX; SCIP; XPRESS
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] T. Achterberg, {\it Constraint Integer Programming}, Ph.D. thesis, TU Berlin,2007. · Zbl 1169.90414
[2] T. Achterberg, {\it SCIP: Solving constraint integer programs}, Math. Program. Comput., 1 (2009), pp. 1-41. · Zbl 1171.90476
[3] W. Adams and R. Forrester, {\it A simple recipe for concise mixed 0-1 linearizations}, Oper. Res. Lett., 33 (2005), pp. 55-61. · Zbl 1076.90030
[4] W. Adams and R. Forrester, {\it Linear forms of nonlinear expressions: New insights on old ideas}, Oper. Res. Lett., 35 (2007), pp. 510-518. · Zbl 1149.90396
[5] W. Adams, R. Forrester, and F. Glover, {\it Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs}, Discrete Optim., 1 (2004), pp. 99-120. · Zbl 1091.90040
[6] W. Adams and S. Henry, {\it Base-2 expansions for linearizing products of functions of discrete variables}, Oper. Res., 60 (2012), pp. 1477-1490. · Zbl 1287.90033
[7] W. Adams and H. Sherali, {\it A tight linearization and an algorithm for zero-one quadratic programming problems}, Management Sci., 32 (1986), pp. 1274-1290. · Zbl 0623.90054
[8] F. Al-Khayyal and J. Falk, {\it Jointly constrained biconvex programming}, Math. Oper. Res., 8 (1983), pp. 273-286. · Zbl 0521.90087
[9] G. Angulo, S. Ahmed, S. S. Dey, and V. Kaibel, {\it Forbidden vertices}, Math. Oper. Res., to appear; doi:10.1287/moor.2014.0673. · Zbl 1316.90021
[10] E. Balas, {\it Disjunctive programming}, Ann. Discrete Math., 5 (1979), pp. 3-51. · Zbl 0409.90061
[11] E. Balas, {\it Disjunctive programming and a hierarchy of relaxations for discrete optimization problems}, SIAM J. Algebraic Discrete Methods, 6 (1985), pp. 466-486. · Zbl 0592.90070
[12] E. Balas, {\it On the convex-hull of the union of certain polyhedra}, Oper. Res. Lett., 7 (1988), pp. 279-283. · Zbl 0663.90061
[13] E. Balas, {\it Disjunctive programming: Properties of the convex hull of feasible points}, Discrete Appl. Math., 89 (1998), pp. 3-44. · Zbl 0921.90118
[14] K. M. Ball, {\it An elementary introduction to modern convex geometry}, in Flavors of Geometry, S. Levy, ed., Math. Sci. Res. Inst. Publ. 31, Cambridge University Press, Cambridge, 1997, pp. 1-58. · Zbl 0901.52002
[15] C. Barnhart, E. Johnson, G. Nemhauser, M. Savelsbergh, and P. Vance, {\it Branch-and-price: Column generation for solving huge integer programs}, Oper. Res., 46 (1996), pp. 316-329. · Zbl 0979.90092
[16] A. Barvinok and E. Veomett, {\it The computational complexity of convex bodies}, in Surveys on Discrete and Computational Geometry: Twenty Years Later, J. Goodman, J. Pach, and R. Pollack, eds., Contemp. Math. 453, AMS, Providence, RI, 2008, pp. 117-138. · Zbl 1145.52002
[17] E. M. L. Beale and J. A. Tomlin, {\it Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables}, in OR 69: Proceedings of the Fifth International Conference on Operational Research, J. Lawrence, ed., Tavistock Publications, 1970, pp. 447-454.
[18] N. Beaumont, {\it An algorithm for disjunctive programs}, European J. Oper. Res., 48 (1990), pp. 362-371. · Zbl 0744.90062
[19] A. Ben-Tal and A. Nemirovski, {\it On polyhedral approximations of the second-order cone}, Math. Oper. Res., 26 (2001), pp. 193-205. · Zbl 1082.90133
[20] D. Bertsimas, S. Gupta, and G. Lulli, {\it Dynamic resource allocation: A flexible and tractable modeling framework}, European J. Oper. Res., 236 (2014), pp. 14-26. · Zbl 1338.90158
[21] D. Bertsimas and J. Tsitsiklis, {\it Introduction to Linear Optimization}, Athena Scientific, 1997.
[22] D. Bertsimas and R. Weismantel, {\it Optimization over Integers}, Dynamic Ideas, 2005.
[23] R. Bixby, M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling, {\it MIP: Theory and practice–closing the gap}, in System Modelling and Optimization, 1999, pp. 19-50. · Zbl 0986.90025
[24] R. Bixby, M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling, {\it Mixed-integer programming: A progress report}, in The Sharpest Cut: The Impact of Manfred Padberg and His Work, SIAM, Philadelphia, PA, 2004, Chap. 18, pp. 309-325. · Zbl 1152.90542
[25] R. Bixby and E. Rothberg, {\it Progress in computational mixed integer programming: A look back from the other side of the tipping point}, Ann. Oper. Res., 149 (2007), pp. 37-41. · Zbl 1213.90011
[26] C. Blair, {\it Representation for multiple right-hand sides}, Math. Programming, 49 (1990), pp. 1-5. · Zbl 0717.90100
[27] D. Bricker, {\it Reformulation of special ordered sets for implicit enumeration algorithms, with applications in nonconvex separable programming}, AIIE Trans., 9 (1977), pp. 195-203.
[28] M. N. Broadie, {\it A theorem about antiprisms}, Linear Algebra Appl., 66 (1985), pp. 99-111. · Zbl 0565.52006
[29] S. Burer and A. Letchford, {\it Non-convex mixed-integer nonlinear programming: A survey}, Surv. Oper. Res. Manag. Sci., 17 (2012), pp. 97-106.
[30] R. D. Carr and G. Lancia, {\it Compact vs. exponential-size LP relaxations}, Oper. Res. Lett., 30 (2002), pp. 57-65. · Zbl 1027.90059
[31] R. D. Carr and G. Lancia, {\it Compact optimization can outperform separation: A case study in structural proteomics}, 4OR, 2 (2004), pp. 221-233. · Zbl 1061.65049
[32] R. Carvajal, M. Constantino, M. Goycoolea, J. P. Vielma, and A. Weintraub, {\it Imposing connectivity constraints in forest planning models}, Oper. Res., 61 (2013), pp. 824-836. · Zbl 1291.90341
[33] C. Cavalcante, C. C. de Souza, M. Savelsbergh, Y. Wang, and L. Wolsey, {\it Scheduling projects with labor constraints}, Discrete Appl. Math., 112 (2001), pp. 27-52. · Zbl 0984.90012
[34] J. Cochran, L. A. Cox, Jr., P. Keskinocak, J. Kharoufeh, and J. Smith, {\it Wiley Encyclopedia of Operations Research and Management Science}, John Wiley & Sons, 2011.
[35] M. Conforti, G. Cornuéjols, and G. Zambelli, {\it Extended formulations in combinatorial optimization}, 4OR, 8 (2010), pp. 1-48. · Zbl 1219.90193
[36] M. Conforti, G. Cornuéjols, and G. Zambelli, {\it Integer Programming}, Grad. Texts in Math. 271, Springer, 2014. · Zbl 1307.90001
[37] M. Conforti and L. Wolsey, {\it Compact formulations as a union of polyhedra}, Math. Programming, 114 (2008), pp. 277-289. · Zbl 1145.90044
[38] A. Conn and M. Mongeau, {\it Discontinuous piecewise linear optimization}, Math. Programming, 80 (1998), pp. 315-380. · Zbl 0901.90163
[39] W. Cook, {\it Fifty-plus years of combinatorial integer programming}, in 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, Springer-Verlag, New York, 2010, Chap. 12, pp. 387-430. · Zbl 1187.90008
[40] W. Cook, {\it In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation}, Princeton University Press, Princeton, NJ, 2011.
[41] D. Coppersmith and J. Lee, {\it Parsimonious binary-encoding in integer programming}, Discrete Optim., 2 (2005), pp. 190-200. · Zbl 1131.90034
[42] K. L. Croxton, B. Gendron, and T. L. Magnanti, {\it Variable disaggregation in network flow problems with piecewise linear costs}, Oper. Res., 55 (2007), pp. 146-157. · Zbl 1167.90602
[43] C. D’Ambrosio, A. Lodi, and S. Martello, {\it Piecewise linear approximation of functions of two variables in MILP models}, Oper. Res. Lett., 38 (2010), pp. 39-46. · Zbl 1182.90064
[44] G. B. Dantzig, {\it Discrete-variable extremum problems}, Oper. Res., 5 (1957), pp. 266-277. · Zbl 1414.90353
[45] G. B. Dantzig, {\it On the significance of solving linear-programming problems with some integer variables}, Econometrica, 28 (1960), pp. 30-44. · Zbl 0089.16101
[46] I. R. de Farias, E. Kozyreff, R. Gupta, and M. Zhao, {\it Branch-and-cut for separable piecewise linear optimization and intersection with semi-continuous constraints}, Math. Program. Comput., 5 (2013), pp. 75-112. · Zbl 1267.90076
[47] I. R. de Farias Jr., M. Zhao, and H. Zhao, {\it A special ordered set approach for optimizing a discontinuous separable piecewise linear function}, Oper. Res. Lett., 36 (2008), pp. 234-238. · Zbl 1163.90758
[48] J. Desrosiers and M. E. Lübbecke, {\it Branch-Price-and-Cut Algorithms}, in Wiley Encyclopedia of Operations Research and Management Science, John Wiley & Sons, 2011. · Zbl 1231.90296
[49] S. Dey and D. Morán R., {\it Some properties of convex hulls of integer points contained in general convex sets}, Math. Programming, 141 (2013), pp. 507-526. · Zbl 1300.90018
[50] B. Dilkina and C. Gomes, {\it Solving connected subgraph problems in wildlife conservation}, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Comput. Sci. 6140, A. Lodi, M. Milano, and P. Toth, eds., Springer, Berlin, Heidelberg, 2010, pp. 102-116. · Zbl 1285.68155
[51] P. Domschke, B. Geißler, O. Kolb, J. Lang, A. Martin, and A. Morsi, {\it Combination of nonlinear and linear optimization of transient gas networks}, INFORMS J. Comput., 23 (2011), pp. 605-617. · Zbl 1243.90030
[52] Fair Isaac Corporation, {\it FICO Xpress Optimization Suite}, http://www.fico.com/en/Products/DMTools/Pages/FICO-Xpress-Optimization-Suite.aspx.
[53] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf, {\it Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds}, in Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, 2012, H. J. Karloff and T. Pitassi, eds., ACM, New York, 2012, pp. 95-106. · Zbl 1286.90125
[54] R. Fourer, {\it A simplex algorithm for piecewise-linear programming I: Derivation and proof}, Math. Programming, 33 (1985), pp. 204-233. · Zbl 0579.90084
[55] R. Fourer, {\it A simplex algorithm for piecewise-linear programming II: Finiteness, feasibility and degeneracy}, Math. Programming, 41 (1988), pp. 281-315. · Zbl 0656.90062
[56] R. Fourer, {\it A simplex algorithm for piecewise-linear programming III: Computational analysis and applications}, Math. Programming, 53 (1992), pp. 213-235. · Zbl 0773.90045
[57] B. Geißler, A. Martin, A. Morsi, and L. Schewe, {\it Using piecewise linear functions for solving MINLPs}, in Mixed Integer Nonlinear Programming, J. Lee and S. Leyffer, eds., Math. Appl. 154, Springer, New York, 2012, pp. 287-314. · Zbl 1242.90132
[58] F. Glover, {\it Improved linear integer programming formulations of nonlinear integer problems}, Management Sci., 22 (1975), pp. 455-460. · Zbl 0318.90044
[59] F. Glover, {\it Improved MIP formulation for products of discrete and continuous variables}, J. Inf. Optim. Sci., 5 (1984), pp. 69-71. · Zbl 0534.90065
[60] F. Glover and E. Woolsey, {\it Converting the \(0-1\) polynomial programming problem to a 0-1 linear program}, Oper. Res., 22 (1974), pp. 180-182. · Zbl 0272.90049
[61] M. X. Goemans, {\it Smallest compact formulation for the permutahedron}, Math. Program., to appear; doi:10.1007/s10107-014-0757-1. · Zbl 1322.90048
[62] C. Gounaris, R. Misener, and C. A. Floudas, {\it Computational comparison of piecewise-linear relaxations for pooling problems}, Indust. Engrg. Chem. Res., 48 (2009), pp. 5742-5766.
[63] B. Grünbaum, {\it Convex Polytopes}, Grad. Texts in Math., Springer, 2003.
[64] S. Gueye and P. Michelon, {\it Miniaturized linearizations for quadratic \(0/1\) problems}, Ann. Oper. Res., 140 (2005), pp. 235-261. · Zbl 1091.90043
[65] S. Gueye and P. Michelon, {\it A linearization framework for unconstrained quadratic (0-1) problems}, Discrete Appl. Math., 157 (2009), pp. 1255-1266. · Zbl 1169.90406
[66] M. Guignard, C. Ryu, and K. Spielberg, {\it Model tightening for integrated timber harvest and transportation planning}, European J. Oper. Res., 111 (1998), pp. 448-460. · Zbl 0938.90007
[67] M. Guignard and K. Spielberg, {\it Logical reduction methods in zero-one programming: Minimal preferred variables}, Oper. Res., 29 (1981), pp. 49-74. · Zbl 0452.90044
[68] M. Guignard-Spielberg and K. Spielberg, {\it Integer Programming: State of the Art and Recent Advances}, Ann. Oper. Res. 139, Springer, New York, 2005. · Zbl 1213.90031
[69] Gurobi Optimization, {\it The Gurobi Optimizer}, available online from http://www.gurobi.com.
[70] P. Hansen, {\it Methods of nonlinear 0-1 programming}, Ann. Discrete Math., 5 (1979), pp. 53-70. · Zbl 0426.90063
[71] P. Hansen and C. Meyer, {\it Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem}, Discrete Appl. Math., 157 (2009), pp. 1267-1290. · Zbl 1178.90251
[72] I. Harjunkoski, R. Pörn, T. Westerlund, and H. Skrifvars, {\it Different strategies for solving bilinear integer non-linear programming problems with convex transformations}, Comput. Chem. Engrg., 21 (1997), pp. S487-S492. · Zbl 0955.90095
[73] R. Hemmecke and R. Weismantel, {\it Representation of sets of lattice points}, SIAM J. Optim., 18 (2007), pp. 133-137. · Zbl 1145.90043
[74] S. M. Henry, {\it Tight Polyhedral Representations of Discrete Sets using Projections, Simplices, and Base-\(2\) Expansions}, Ph.D. thesis, Clemson University, 2011.
[75] J. N. Hooker, {\it Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction}, Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, 2000. · Zbl 0974.90001
[76] J. N. Hooker, {\it A principled approach to mixed integer/linear problem formulation}, in Operations Research and Cyber-Infrastructure, J. W. Chinneck, B. Kristjansson, and M. J. Saltzman, eds., Oper. Res./Comput. Sci. Interfaces Ser. 47, Springer, New York, 2009, pp. 79-100.
[77] J. N. Hooker, {\it Hybrid modeling}, in Hybrid Optimization: The Ten Years of CPAIOR, P. Van Hentenryck and M. Milano, eds., Springer Optim. Appl. 45, Springer, 2011, pp. 11-62. · Zbl 1206.90177
[78] J. N. Hooker, {\it Integrated Methods for Optimization}, 2nd ed., Internat. Ser. Oper. Res. Management Sci. 170, Springer, 2012. · Zbl 1263.90002
[79] J. N. Hooker and M. A. Osorio, {\it Mixed logical-linear programming}, Discrete Appl. Math., 96 (1999), pp. 395-442. · Zbl 0945.90031
[80] R. Horst and H. Tuy, {\it Global Optimization: Deterministic Approaches}, Springer, 2003. · Zbl 0867.90105
[81] T. Ibaraki, {\it Integer programming formulation of combinatorial optimization problems}, Discrete Math., 16 (1976), pp. 39-52. · Zbl 0357.90042
[82] IBM ILOG, {\it CPLEX High-Performance Mathematical Programming Engine}, \burlhttp://www.ibm.com/software/integration/optimization/cplex/.
[83] R. G. Jeroslow, {\it Some basis theorems for integral monoids}, Math. Oper. Res., 3 (1978), pp. 145-154. · Zbl 0404.90061
[84] R. G. Jeroslow, {\it Representations of unbounded optimization problems as integer programs}, J. Optim. Theory Appl., 30 (1980), pp. 339-351. · Zbl 0393.90062
[85] R. G. Jeroslow, {\it Representability in mixed integer programming I: Characterization results}, Discrete Appl. Math., 17 (1987), pp. 223-243. · Zbl 0618.90069
[86] R. G. Jeroslow, {\it Alternative formulations of mixed integer programs}, Ann. Oper. Res., 12 (1988), pp. 241-276.
[87] R. G. Jeroslow, {\it A simplification for some disjunctive formulations}, European J. Oper. Res., 36 (1988), pp. 116-121. · Zbl 0647.90055
[88] R. G. Jeroslow, {\it Logic-Based Decision Support: Mixed Integer Model Formulation}, Ann. Discrete Math. 40, North-Holland, Amsterdam, 1989. · Zbl 0698.90062
[89] R. G. Jeroslow, {\it Representability of functions}, Discrete Appl. Math., 23 (1989), pp. 125-137. · Zbl 0684.90066
[90] R. G. Jeroslow and J. K. Lowe, {\it Modeling with integer variables}, Math. Programming Stud., 22 (1984), pp. 167-184. · Zbl 0554.90081
[91] R. G. Jeroslow and J. K. Lowe, {\it Experimental results on the new techniques for integer programming formulations}, J. Oper. Res. Soc., 36 (1985), pp. 393-403. · Zbl 0565.90047
[92] E. L. Johnson, G. L. Nemhauser, and M. W. P. Savelsbergh, {\it Progress in linear programming-based algorithms for integer programming: An exposition}, INFORMS J. Comput., 12 (2000), pp. 2-23. · Zbl 1052.90048
[93] W. B. Johnson and J. Lindenstrauss, eds., {\it Handbook of the Geometry of Banach Spaces. Vol.} I, North-Holland, Amsterdam, 2001. · Zbl 0970.46001
[94] M. Jünger, T. Liebling, D. Naddef, G. Nemhauser, W. Pulleyblank, G. Reinelt, G. Rinaldi, and L. Wolsey, {\it 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art}, Springer-Verlag, New York, 2010. · Zbl 1181.90003
[95] V. Kaibel, {\it Extended formulations in combinatorial optimization}, Optima, 85 (2011), pp. 2-7.
[96] V. Kaibel and A. Loos, {\it Branched polyhedral systems}, in Integer Programming and Combinatorial Optimization, 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings, F. Eisenbrand and F. B. Shepherd, eds., Lecture Notes in Comput. Sci. 6080, Springer, 2010, pp. 177-190. · Zbl 1285.90082
[97] V. Kaibel and K. Pashkovich, {\it Constructing extended formulations from reflection relations}, in Proceedings of IPCO 2011, O. Günlük and G. J. Woeginger, eds., Lecture Notes in Comput. Sci. 6655, Springer, 2011, pp. 287-300. · Zbl 1341.90148
[98] B. S. Kashin, {\it The widths of certain finite-dimensional sets and classes of smooth functions}, Izv. Akad. Nauk SSSR Ser. Mat., 41 (1977), pp. 334-351 (in Russian).
[99] A. Keha, I. de Farias, and G. Nemhauser, {\it A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization}, Oper. Res., 54 (2006), pp. 847-858. · Zbl 1167.90589
[100] O. Kettani and M. Oral, {\it Equivalent formulations of nonlinear integer problems for efficient optimization}, Management Sci., 36 (1990), pp. 115-119. · Zbl 0694.90073
[101] S. Küçükyavuz, {\it On mixing sets arising in chance-constrained programming}, Math. Programming, 132 (2012), pp. 31-56. · Zbl 1262.90110
[102] A. H. Land and A. G. Doig, {\it An automatic method for solving discrete programming problems}, Econometrica, 28 (1960), pp. 497-520. · Zbl 0101.37004
[103] J. Lee, {\it All-different polytopes}, J. Comb. Optim., 6 (2002), pp. 335-352. · Zbl 1007.90041
[104] J. Lee, {\it A celebration of 50 years of integer programming}, Optima, 76 (2008), pp. 10-14.
[105] J. Lee and F. Margot, {\it On a binary-encoded ILP coloring formulation}, INFORMS J. Comput., 19 (2007), pp. 406-415. · Zbl 1241.90087
[106] J. Lee and D. Wilson, {\it Polyhedral methods for piecewise-linear functions I: The lambda method}, Discrete Appl. Math., 108 (2001), pp. 269-285. · Zbl 1002.90038
[107] H. Li and H. Lu, {\it Global optimization for generalized geometric programs with mixed free-sign variables}, Oper. Res., 57 (2009), pp. 701-713. · Zbl 1226.90078
[108] L. Liberti, {\it Reformulations in mathematical programming: Definitions and systematics}, RAIRO Oper. Res., 43 (2009), pp. 55-85. · Zbl 1158.90390
[109] L. Liberti and N. Maculan, {\it Reformulation techniques in mathematical programming}, Discrete Appl. Math., 157 (2009), pp. 1165-1166. · Zbl 1170.90304
[110] E. Lin and D. Bricker, {\it Connecting special ordered inequalities and transformation and reformulation technique in multiple choice programming}, Comput. Oper. Res., 29 (2002), pp. 1441-1446. · Zbl 0994.90106
[111] E. Y. Lin and D. L. Bricker, {\it On the calculation of true and pseudo penalties in multiple choice integer programming}, European J. Oper. Res., 55 (1991), pp. 228-236. · Zbl 0748.90044
[112] A. Lodi, {\it Mixed integer programming computation}, in 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, Springer-Verlag, New York, 2010, Chap. 16, pp. 619-645. · Zbl 1187.90206
[113] J. K. Lowe, {\it Modelling with Integer Variables}, Ph.D. thesis, Georgia Institute of Technology, 1984. · Zbl 0554.90081
[114] J. Luedtke, S. Ahmed, and G. Nemhauser, {\it An integer programming approach for linear programs with probabilistic constraints}, Math. Programming, 122 (2010), pp. 247-272. · Zbl 1184.90115
[115] R. K. Martin, {\it Using separation algorithms to generate mixed integer model reformulations}, Oper. Res. Lett., 10 (1991), pp. 119-128. · Zbl 0747.90071
[116] R. K. Martin, R. L. Rardin, and B. A. Campbell, {\it Polyhedral characterization of discrete dynamic programming}, Oper. Res., 38 (1990), pp. 127-138. · Zbl 0711.90066
[117] G. McCormick, {\it Nonlinear Programming: Theory, Algorithms and Applications}, John Wiley & Sons, 1983. · Zbl 0563.90068
[118] R. R. Meyer, {\it On the existence of optimal solutions to integer and mixed-integer programming problems}, Math. Programming, 7 (1974), pp. 223-235. · Zbl 0292.90036
[119] R. R. Meyer, {\it Integer and mixed-integer programming models: General properties}, J. Optim. Theory Appl., 16 (1975), pp. 191-206. · Zbl 0283.90032
[120] R. R. Meyer, {\it Mixed integer minimization models for piecewise-linear functions of a single variable}, Discrete Math., 16 (1976), pp. 163-171. · Zbl 0348.90133
[121] R. R. Meyer, {\it A theoretical and computational comparison of equivalent mixed-integer formulations}, Naval Res. Logistics, 28 (1981), pp. 115-131. · Zbl 0453.90068
[122] R. R. Meyer, M. V. Thakkar, and W. P. Hallman, {\it Rational mixed-integer and polyhedral union minimization models}, Math. Oper. Res., 5 (1980), pp. 135-146. · Zbl 0434.90068
[123] R. Misener and C. A. Floudas, {\it Global optimization of large-scale generalized pooling problems: Quadratically constrained MINLP models}, Indust. Engrg. Chem. Res., 49 (2010), pp. 5424-5438.
[124] R. Misener and C. A. Floudas, {\it Piecewise-linear approximations of multidimensional functions}, J. Optim. Theory Appl., 145 (2010), pp. 120-147. · Zbl 1186.90080
[125] R. Misener and C. A. Floudas, {\it Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations}, Math. Programming, 136 (2012), pp. 155-182. · Zbl 1257.90079
[126] R. Misener, C. Gounaris, and C. A. Floudas, {\it Mathematical modeling and global optimization of large-scale extended pooling problems with the (EPA) complex emissions constraints}, Comput. Chem. Engrg., 34 (2010), pp. 1432-1456.
[127] R. Misener, J. Thompson, and C. A. Floudas, {\it APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes}, Comput. Chem. Engrg., 35 (2011), pp. 876-892.
[128] J. E. Mitchell, {\it Branch and cut}, in Wiley Encyclopedia of Operations Research and Management Science, John Wiley & Sons, 2011.
[129] R. H. Möhring, A. S. Schulz, F. Stork, and M. Uetz, {\it On project scheduling with irregular starting time costs}, Oper. Res. Lett., 28 (2001), pp. 149-154. · Zbl 1027.90040
[130] F. M. Muldoon, W. P. Adams, and H. D. Sherali, {\it Ideal representations of lexicographic orderings and base-2 expansions of integer variables}, Oper. Res. Lett., 41 (2013), pp. 32-39. · Zbl 1266.90131
[131] G. L. Nemhauser and L. A. Wolsey, {\it Integer and Combinatorial Optimization}, Wiley-Interscience, 1988. · Zbl 0652.90067
[132] W. Ogryczak, {\it A note on modeling multiple choice requirements for simple mixed integer programming solvers}, Comput. Oper. Res., 23 (1996), pp. 199-205. · Zbl 0868.90086
[133] M. Oral and O. Kettani, {\it A linearization procedure for quadratic and cubic mixed-integer problems}, Oper. Res., 40 (1992), pp. 109-116. · Zbl 0771.90072
[134] J. Owen and S. Mehrotra, {\it On the value of binary expansions for general mixed-integer linear programs}, Oper. Res., 50 (2002), pp. 810-819. · Zbl 1163.90673
[135] M. W. Padberg, {\it The boolean quadric polytope: Some characteristics, facets and relatives}, Math. Programming, 45 (1989), pp. 139-172. · Zbl 0675.90056
[136] M. W. Padberg, {\it Approximating separable nonlinear functions via mixed zero-one programs}, Oper. Res. Lett., 27 (2000), pp. 1-5. · Zbl 0960.90065
[137] M. W. Padberg and M. P. Rijal, {\it Location, Scheduling, Design, and Integer Programming}, Springer, 1996. · Zbl 0879.68075
[138] Y. Pochet and L. Wolsey, {\it Production Planning by Mixed Integer Programming}, Springer Ser. Oper. Res. Financ. Eng., Springer, 2006. · Zbl 1102.90039
[139] R. Raman and I. Grossmann, {\it Modelling and computational techniques for logic based integer programming}, Comput. Chem. Engrg., 18 (1994), pp. 563-578.
[140] T. Rothvoß, {\it The matching polytope has exponential extension complexity}, in Symposium on Theory of Computing (STOC 2014), D. B. Shmoys, ed., ACM, New York, 2014, pp. 263-272. · Zbl 1315.90038
[141] D. M. Ryan and B. A. Foster, {\it An integer programming approach to scheduling}, in Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, A. Wren, ed., North-Holland, 1981, pp. 269-280.
[142] R. Sadykov and F. Vanderbeck, {\it Column generation for extended formulations}, Electron. Notes Discrete Math., 37 (2011), pp. 357-362. · Zbl 1268.90035
[143] N. Sawaya and I. Grossmann, {\it A cutting plane method for solving linear generalized disjunctive programming problems}, Comput. Chem. Engrg., 29 (2005), pp. 1891-1913.
[144] N. Sawaya and I. Grossmann, {\it A hierarchy of relaxations for linear generalized disjunctive programming}, European J. Oper. Res., 216 (2012), pp. 70-82. · Zbl 1266.90132
[145] A. Schrijver, {\it Theory of Linear and Integer Programming}, Wiley Series in Discrete Mathematics & Optimization, John Wiley & Sons, 1998. · Zbl 0970.90052
[146] A. Schrijver, {\it Combinatorial Optimization: Polyhedra and Efficiency}, Algorithms and Combinatorics, Springer, 2003. · Zbl 1041.90001
[147] H. Sherali and W. P. Adams, {\it A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems}, Kluwer Academic Publishers, 1999. · Zbl 0926.90078
[148] D. Sommer, {\it Computational Experience with the Ophelie Mixed Integer Code}, talk presented at the International TIMS Conference, Houston, 1972.
[149] C. C. Souza and L. A. Wolsey, {\it Scheduling Projects with Labour Constraints}, relatório técnico ic-97-22, IC - UNICAMP, 1997.
[150] K. Spielberg, {\it Minimal Preferred Variable Methods in 0-1 Programming}, Tech. Report 320-3013, IBM Philadelphia Scientific Center, 1972.
[151] D. Stralberg, D. L. Applegate, S. J. Phillips, M. P. Herzog, N. Nur, and N. Warnock, {\it Optimizing wetland restoration and management for avian communities using a mixed integer programming approach}, Biological Conservation, 142 (2009), pp. 94-109.
[152] S. Szarek, {\it Convexity, complexity, and high dimensions}, in International Congress of Mathematicians. Vol. II, Eur. Math. Soc., Zürich, 2006, pp. 1599-1621. · Zbl 1120.46004
[153] A. Toriello and J. P. Vielma, {\it Fitting piecewise linear continuous functions}, European J. Oper. Res., 219 (2012), pp. 86-95. · Zbl 1244.90166
[154] F. Vanderbeck and L. Wolsey, {\it Reformulation and decomposition of integer programs}, in 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, Springer-Verlag, New York, 2010, Chap. 16, pp. 431-502. · Zbl 1187.90207
[155] J. P. Vielma, S. Ahmed, and G. L. Nemhauser, {\it Mixed-integer models for nonseparable piecewise-linear optimization: Unifying framework and extensions}, Oper. Res., 58 (2010), pp. 303-315. · Zbl 1226.90046
[156] J. P. Vielma, S. Ahmed, and G. L. Nemhauser, {\it A note on “a superior representation method for piecewise linear functions,”} INFORMS J. Comput., 22 (2010), pp. 493-497. · Zbl 1243.90131
[157] J. P. Vielma, S. Ahmed, and G. L. Nemhauser, {\it Mixed integer linear programming formulations for probabilistic constraints}, Oper. Res. Lett., 40 (2012), pp. 153-158. · Zbl 1245.90066
[158] J. P. Vielma, A. B. Keha, and G. L. Nemhauser, {\it Nonconvex, lower semicontinuous piecewise linear optimization}, Discrete Optim., 5 (2008), pp. 467-488. · Zbl 1190.90149
[159] J. P. Vielma and G. L. Nemhauser, {\it Modeling disjunctive constraints with a logarithmic number of binary variables and constraints}, in Proceedings of IPCO 2008, A. Lodi, A. Panconesi, and G. Rinaldi, eds., Lecture Notes in Comput. Sci. 5035, Springer, 2008, pp. 199-213. · Zbl 1143.90384
[160] J. P. Vielma and G. L. Nemhauser, {\it Modeling disjunctive constraints with a logarithmic number of binary variables and constraints}, Math. Programming, 128 (2011), pp. 49-72. · Zbl 1218.90137
[161] M. V. Vyve and L. A. Wolsey, {\it Approximate extended formulations}, Math. Programming, 105 (2006), pp. 501-522. · Zbl 1085.90051
[162] L. Watters, {\it Reduction of integer polynomial programming problems to zero-one linear programming problems}, Oper. Res., 15 (1967), pp. 1171-1174.
[163] H. P. Williams, {\it Experiments in the formulation of integer programming problems}, Math. Programming Stud., 2 (1974), pp. 180-197.
[164] H. P. Williams, {\it Logic and Integer Programming}, International Series in Operations Research & Management Science, Springer, 2009. · Zbl 1175.90005
[165] D. L. Wilson, {\it Polyhedral Methods for Piecewise-Linear Functions}, Ph.D. thesis, University of Kentucky, Lexington, KY, 1998.
[166] L. Wolsey, {\it Integer Programming}, Wiley Series in Discrete Mathematics and Optimization, Wiley, 1998. · Zbl 0930.90072
[167] M. Yannakakis, {\it Expressing combinatorial optimization problems by linear programs}, J. Comput. System Sci., 43 (1991), pp. 441-466. · Zbl 0748.90074
[168] S. Y\ild\iz and J. P. Vielma, {\it Incremental and encoding formulations for mixed integer programming}, Oper. Res. Lett., 41 (2013), pp. 654-658. · Zbl 1287.90040
[169] M. Zhao and I. R. de Farias, Jr., {\it The piecewise linear optimization polytope: New inequalities and intersection with semi-continuous constraints}, Math. Program., 141 (2013), pp. 217-255. · Zbl 1274.90331
[170] G. M. Ziegler, {\it Lectures on Polytopes}, Springer-Verlag, 1995. · Zbl 0823.52002
[171] Zuse Institute Berlin, {\it SCIP: Solving Constraint Integer Programs}, http://scip.zib.de/.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.