Nonconvex Piecewise Linear Functions: Advanced Formulations and Simple Modeling Tools

References

• Balakrishnan A, Graves SC (1989) A composite algorithm for a concave-cost network flow problem. Networks 19(2):175–202.Crossref, Google Scholar
• Beale EML, Tomlin JA (1970) Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. Lawrence J, ed. OR 69: Proc. Fifth Internat. Conf. Oper. Res. (Tavistock Publications, London), 447–454.Google Scholar
• Bergamini ML, Aguirre P, Grossmann I (2005) Logic-based outer approximation for globally optimal synthesis of process networks. Comput. Chemical Engrg. 29(9):1914–1933.Crossref, Google Scholar
• Bergamini ML, Grossmann I, Scenna N, Aguirre P (2008) An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms. Comput. Chemical Engrg. 32(3):477–493.Crossref, Google Scholar
• Bertsimas D, Mišić VV (2017) Robust product line design. Oper. Res. 65(1):19–37.Link, Google Scholar
• Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing. SIAM Rev. 59(1):65–98.Crossref, Google Scholar
• Bixby R, Rothberg E (2007) Progress in computational mixed integer programming—A look back from the other side of the tipping point. Ann. Oper. Res. 149:37–41.Crossref, Google Scholar
• Camm JD, Cochran JJ, Curry DJ, Kannan S (2006) Conjoint optimization: An exact branch-and-bound algorithm for the share-of-choice problem. Management Sci. 52(3):435–447.Link, Google Scholar
• Castro PM, Teles JP (2013) Comparison of global optimization algorithms for the design of water-using networks. Comput. Chemical Engrg. 52:249–261.Crossref, Google Scholar
• Codas A, Camponogara E (2012) Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing. Eur. J. Oper. Res. 217(1):222–231.Crossref, Google Scholar
• Codas A, Campos S, Camponogara E, Gunnerud V, Sunjerga S (2012) Integrated production optimization of oil fields with pressure and routing constraints: The Urucu field. Comput. Chemical Engrg. 46:178–189.Crossref, Google Scholar
• Coppersmith D, Lee J (2005) Parsimonious binary-encoding in integer programming. Discrete Optim. 2(3):190–200.Crossref, Google Scholar
• Croxton KL, Gendron B, Magnanti TL (2003) A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems. Management Sci. 49(9):1268–1273.Link, Google Scholar
• Croxton KL, Gendron B, Magnanti TL (2007) Variable disaggregation in network flow problems with piecewise linear costs. Oper. Res. 55(1):146–157.Link, Google Scholar
• D’Ambrosio C, Lodi A, Martello S (2010) Piecewise linear approximation of functions of two variables in MILP models. Oper. Res. Lett. 38(1):39–46.Crossref, Google Scholar
• Dantzig GB (1960) On the significance of solving linear programming problems with some integer variables. Econometrica 28(1):30–44.Crossref, Google Scholar
• de Farias I Jr, Zhao M, Zhao H (2008) A special ordered set approach for optimizing a discontinuous separable piecewise linear function. Oper. Res. Lett. 36(2):234–238.Crossref, Google Scholar
• de Farias IR Jr, Kozyreff E, Gupta R, Zhao M (2013) Branch-and-cut for separable piecewise linear optimization and intersection with semi-continuous constraints. Math. Programming Comput. 5(1):75–112.Crossref, Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Crossref, Google Scholar
• Fourer R, Gay DM, Kernighan B (1989) AMPL: A Mathematical Programming Language (Springer-Verlang, Berlin).Google Scholar
• Fügenschuh A, Hayn C, Michaels D (2014) Mixed-integer linear methods for layout-optimization of screening systems in recovered paper production. Optim. Engrg. 15:533–573.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability (W. H. Freeman and Company, New York).Google Scholar
• Geißler B, Martin A, Morsi A, Schewe L (2012) Using Piecewise Linear Functions for Solving MINLPs (Springer, Berlin), 287–314.Google Scholar
• Graf T, Hentenryck PV, Pradelles-Lasserre C, Zimmer L (1990) Simulation of hybrid circuits in constraint logic programming. Comput. Math. Appl. 20(9–10):45–56.Crossref, Google Scholar
• Huchette J, Vielma JP (2019a) A combinatorial approach for small and strong formulations of disjunctive constraints. Math. Oper. Res. 44(3):767–1144.Link, Google Scholar
• Huchette J, Vielma JP (2019b) A geometric way to build strong mixed-integer programming formulations. Preprint, submitted October 9, https://arxiv.org/abs/1811.10409.Google Scholar
• Huchette J, Dey SS, Vielma JP (2017) Strong mixed-integer formulations for the floor layout problem. INFOR Inform. Systems Oper. Res. 56(4):392–433.Google Scholar
• Jeroslow RG (1988) Alternative formulations of mixed integer programs. Ann. Oper. Res. 12:241–276.Crossref, Google Scholar
• Jeroslow RG, Lowe J (1984) Modelling with integer variables. Korte B, Ritter K, eds. Mathematical Programming at Oberwolfach II, Mathematical Programming Studies, vol. 22 (Springer, Berlin), 167–184.Crossref, Google Scholar
• Jeroslow RG, Lowe JK (1985) Experimental results on the new techniques for integer programming formulations. J. Oper. Res. Soc. 36(5):393–403.Crossref, Google Scholar
• Jünger M, Liebling T, Naddef D, Nemhauser G, Pulleyblank W, Reinelt G, Rinaldi G, Wolsey L (2010) 50 Years of Integer Programming 1958–2008 (Springer, Berlin).Crossref, Google Scholar
• Keha AB, de Farias IR Jr, Nemhauser GL (2004) Models for representing piecewise linear cost functions. Oper. Res. Lett. 32(1):44–48.Crossref, Google Scholar
• Keha AB, de Farias IR Jr, Nemhauser GL (2006) A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization. Oper. Res. 54(5):847–858.Link, Google Scholar
• Koch T, Hiller B, Pfetsch ME, Schewe L, eds. (2015) Evaluating Gas Network Capacities, MOS-SIAM Series on Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• Kolodziej S, Castro PM, Grossmann IE (2013) Global optimization of bilinear programs with a multiparametric disaggregation technique. J. Global Optim. 57:1039–1063.Crossref, Google Scholar
• Lee J, Wilson D (2001) Polyhedral methods for piecewise-linear functions I: The lambda method. Discrete Appl. Math. 108:269–285.Crossref, Google Scholar
• Lee J, Skipper D, Speakman E (2018) Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations. Math. Programming. 170(1):121–140.Crossref, Google Scholar
• Liu H, Wang DZ (2015) Global optimization method for network design problem with stochastic user equilibrium. Transportation Res. Part B: Methodological 72:20–39.Crossref, Google Scholar
• Magnanti TL, Stratila D (2004) Separable concave optimization approximately equals piecewise linear optimization. Bienstock D, Nemhauser G, eds. Lecture Notes in Computer Science, vol. 3064 (Springer, Berlin), 234–243.Google Scholar
• Mahlke D, Martin A, Moritz S (2010) A mixed integer approach for time-dependent gas network optimization. Optim. Methods Software 25(4):625–644.Crossref, Google Scholar
• Markowitz HM, Manne AS (1957) On the solution of discrete programming problems. Econometrica 25(1):84–110.Crossref, Google Scholar
• Martin A, Möller M, Moritz S (2006) Mixed integer models for the stationary case of gas network optimization. Math. Programming 105(2-3):563–582.Crossref, Google Scholar
• Misener R, Floudas C (2012) Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Math. Programming 136(1):155–182.Crossref, Google Scholar
• Misener R, Gounaris CE, Floudas CA (2009) Global optimization of gas lifting operations: A comparative study of piecewise linear formulations. Indust. Engrg. Chemical Res. 48(13):6098–6104.Crossref, Google Scholar
• Misener R, Thompson JP, Floudas CA (2011) APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Comput. Chemical Engrg. 35:876–892.Crossref, Google Scholar
• Muldoon F (2012) Polyhedral approximations of quadratic semi-assignment problems, disjunctive programs, and base-2 expansions of integer variables. PhD thesis, Clemson University, Clemson, SC.Google Scholar
• Muldoon FM, Adams WP, Sherali HD (2013) Ideal representations of lexicographic orderings and base-2 expansions of integer variables. Oper. Res. Lett. 41(1):32–39.Crossref, Google Scholar
• Padberg M (2000) Approximating separable nonlinear functions via mixed zero-one programs. Oper. Res. Lett. 27(1):1–5.Crossref, Google Scholar
• Rebennack S (2016) Computing tight bounds via piecewise linear functions through the example of circle cutting problems. Math. Methods Oper. Res. 84:3–57.Crossref, Google Scholar
• Rosenthal R (2014) GAMS—A User’s Guide (GAMS Development Corporation, Fairfax, VA).Google Scholar
• Savage C (1997) A survey of combinatorial Gray codes. SIAM Rev. 39(4):605–629.Crossref, Google Scholar
• Sherali HD, Wang H (2001) Global optimization of nonconvex factorable programming problems. Math. Programming 89(3):459–478.Crossref, Google Scholar
• Silva TL, Camponogara E (2014) A computational analysis of multidimensional piecewise-linear models with applications to oil production optimization. Eur. J. Oper. Res. 232(3):630–642.Crossref, Google Scholar
• Silva TL, Codas A, Camponogara E (2012) A computational analysis of convex combination models for multidimensional piecewise-linear approximation in oil production optimization. Proc. 2012 IFAC Workshop Automatic Control Offshore Oil Gas Production (Elsevier, Amsterdam), 292–298.Google Scholar
• Todd MJ (1977) Union Jack triangulations. Karamardian S, ed. Fixed Points: Algorithms and Applications (Academic Press, Inc., New York), 315–336.Google Scholar
• Tomlin J (1981) A suggested extension of special ordered sets to non-separable non-convex programming problems. North-Holland Math. Stud. 59:359–370.Crossref, Google Scholar
• Vielma JP (2015) Mixed integer linear programming formulation techniques. SIAM Rev. 57(1):3–57.Crossref, Google Scholar
• Vielma JP (2018) Embedding formulations and complexity for unions of polyhedra. Management Sci. 64(10):4721–4734.Link, Google Scholar
• Vielma JP, Nemhauser G (2011) Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Math. Programming 128(1-2):49–72.Crossref, Google Scholar
• Vielma JP, Ahmed S, Nemhauser G (2010) Mixed-integer models for nonseparable piecewise-linear optimization: Unifying framework and extensions. Oper. Res. 58(2):303–315.Link, Google Scholar
• Wang X, Camm FD, Curry DJ (2009) A branch-and-price approach to the share-of-choice product line design problem. Management Sci. 55(10):1718–1728.Link, Google Scholar
• Wilson DL (1998) Polyhedral methods for piecewise-linear functions. PhD thesis, University of Kentucky, Lexington, KY.Google Scholar
• Yildiz S, Vielma JP (2013) Incremental and encoding formulations for mixed integer programming. Oper. Res. Lett. 41(6):654–658.Crossref, Google Scholar