×

Locally ideal formulations for piecewise linear functions with indicator variables. (English) Zbl 1287.90039

Summary: We consider mixed integer linear programming (MIP) formulations for piecewise linear functions (PLFs) that are evaluated when an indicator variable is turned on. We describe modifications to standard MIP formulations for PLFs with desirable theoretical properties and superior computational performance in this context.

MSC:

90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alguacil, N.; Motto, A. L.; Conejo, A. J., Transmission expansion planning: a mixed-integer LP approach, IEEE Trans. Power Syst., 18, 1070-1077 (2003)
[2] Balakrishnan, A.; Graves, S. C., A composite algorithm for a concave-cost network flow problem, Networks, 19, 175-202 (1989) · Zbl 0673.90034
[3] Balas, E., Disjunctive programming, (Ann. Discrete Math. 5: Discrete Optim. (1979), North Holland), 3-51 · Zbl 0409.90061
[5] Borghetti, A.; Member, S.; Ambrosio, C. D.; Lodi, A.; Martello, S., An MILP approach for short-term hydro scheduling and unit commitment with head-dependent reservoir, IEEE Trans. Power Syst., 23, 1115-1124 (2008)
[6] Carrion, M.; Arroyo, J. M., A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem, IEEE Trans. Power Syst., 21, 1371-1378 (2006)
[7] Croxton, K. L.; Gendron, B.; Magnanti, T. L., Comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems, Manage. Sci., 49, 1268-1273 (2003) · Zbl 1232.90311
[8] Dantzig, G., On the significance of solving linear programming problems with some integer variables, Econometrica, 28, 30-44 (1960) · Zbl 0089.16101
[9] Geißler, B.; Martin, A.; Morsi, A.; Schewe, L., Using piecewise linear functions for solving MINLPs, (Lee, J.; Leyffer, S., Mixed Integer Nonlinear Programming. Mixed Integer Nonlinear Programming, The IMA Vol. in Math. and its Appl., volume 154 (2012), Springer), 287-314 · Zbl 1242.90132
[10] Günlük, O.; Linderoth, J., Perspective relaxation of mixed integer nonlinear programs with indicator variables, Math. Program., 104, 186-203 (2010)
[11] Günlük, O.; Linderoth, J., Perspective reformulation and applications, (Lee, J.; Leyffer, S., Mixed Integer Nonlinear Programming. Mixed Integer Nonlinear Programming, The IMA Vol. in Math. and its Appl., vol. 154 (2012), Springer), 61-92 · Zbl 1242.90134
[12] Gupta, V.; Grossmann, I. E., An efficient multiperiod MINLP model for optimal planning of offshore oil and gas field infrastructure, Ind. Eng. Chem. Res., 51, 6823-6840 (2012)
[13] Jeroslow, R. G.; Lowe, J. K., Modelling with integer variables, (Math. Program. at Oberwolfach II. Math. Program. at Oberwolfach II, Math. Program. Stud., vol. 22 (1984), Springer: Springer Berlin Heidelberg), 167-184 · Zbl 0554.90081
[14] Keha, A. B.; de Farias, I. R.; Nemhauser, G. L., Models for representing piecewise linear cost functions, Oper. Res. Lett., 32, 44-48 (2004) · Zbl 1056.90107
[15] Lee, J.; Wilson, D., Polyhedral methods for piecewise-linear functions I: the lambda method, Discrete Appl. Math., 108, 269-285 (2001) · Zbl 1002.90038
[16] Lodish, L., CALLPLAN: an interactive salesman’s call planning system, Manage. Sci., 18 (1971)
[17] Markowitz, H. M.; Manne, A. S., On the Solution of Discrete Programming Problems, Econometrica, 25, 84-110 (1957) · Zbl 0078.34005
[18] Martin, A.; Möller, M.; Moritz, S., Mixed integer models for the stationary case of gas network optimization, Math. Program., 105, 563-582 (2006) · Zbl 1085.90035
[19] Meyer, R. R., Integer and mixed-integer programming models: general properties, J. Optim. Theory Appl., 16, 191-206 (1976) · Zbl 0283.90032
[20] Padberg, M., Approximating separable nonlinear functions via mixed zero-one programs, Oper. Res. Lett., 27, 1-5 (2000) · Zbl 0960.90065
[21] Padberg, M. W.; Rijal, M. P., (Location, Scheduling, Design and Integer Programming. Location, Scheduling, Design and Integer Programming, International Series in Operations Research & Management Science, vol. 3 (1996), Springer: Springer Boston) · Zbl 0879.68075
[23] Vielma, J. P.; Ahmed, S.; Nemhauser, G., Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions, Oper. Res., 58, 303-315 (2009) · Zbl 1226.90046
[24] Vielma, J. P.; Nemhauser, G. L., Modeling disjunctive constraints with a logarithmic number of binary variables and constraints, Math. Program., 128, 49-72 (2009) · Zbl 1218.90137
[25] Zoltners, A.; Sinha, P., Integer programming models for sales resource allocation, Manage. Sci., 26, 242-260 (1980) · Zbl 0442.90049
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.