IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v58y2010i2p303-315.html
   My bibliography  Save this article

Mixed-Integer Models for Nonseparable Piecewise-Linear Optimization: Unifying Framework and Extensions

Author

Listed:
  • Juan Pablo Vielma

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Shabbir Ahmed

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • George Nemhauser

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

We study the modeling of nonconvex piecewise-linear functions as mixed-integer programming (MIP) problems. We review several new and existing MIP formulations for continuous piecewise-linear functions with special attention paid to multivariate nonseparable functions. We compare these formulations with respect to their theoretical properties and their relative computational performance. In addition, we study the extension of these formulations to lower semicontinuous piecewise-linear functions.

Suggested Citation

  • Juan Pablo Vielma & Shabbir Ahmed & George Nemhauser, 2010. "Mixed-Integer Models for Nonseparable Piecewise-Linear Optimization: Unifying Framework and Extensions," Operations Research, INFORMS, vol. 58(2), pages 303-315, April.
    • Handle: RePEc:inm:oropre:v:58:y:2010:i:2:p:303-315
    DOI: 10.1287/opre.1090.0721
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1090.0721
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1090.0721?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Keely L. Croxton & Bernard Gendron & Thomas L. Magnanti, 2003. "Models and Methods for Merge-in-Transit Operations," Transportation Science, INFORMS, vol. 37(1), pages 1-22, February.
    2. Keely L. Croxton & Bernard Gendron & Thomas L. Magnanti, 2003. "A Comparison of Mixed-Integer Programming Models for Nonconvex Piecewise Linear Cost Minimization Problems," Management Science, INFORMS, vol. 49(9), pages 1268-1273, September.
    3. Keely L. Croxton & Bernard Gendron & Thomas L. Magnanti, 2007. "Variable Disaggregation in Network Flow Problems with Piecewise Linear Costs," Operations Research, INFORMS, vol. 55(1), pages 146-157, February.
    4. LEE, Jon & WILSON, Dan, 2001. "Polyhedral methods for piecewise-linear functions I: the lambda method," LIDAM Reprints CORE 1493, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Ahmet B. Keha & Ismael R. de Farias & George L. Nemhauser, 2006. "A Branch-and-Cut Algorithm Without Binary Variables for Nonconvex Piecewise Linear Optimization," Operations Research, INFORMS, vol. 54(5), pages 847-858, October.
    6. Leon S. Lasdon & Allan D. Waren, 1980. "Feature Article—Survey of Nonlinear Programming Applications," Operations Research, INFORMS, vol. 28(5), pages 1029-1073, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Christensen, Tue R.L. & Labbé, Martine, 2015. "A branch-cut-and-price algorithm for the piecewise linear transportation problem," European Journal of Operational Research, Elsevier, vol. 245(3), pages 645-655.
    2. Tue R. L. Christensen & Kim Allan Andersen & Andreas Klose, 2013. "Solving the Single-Sink, Fixed-Charge, Multiple-Choice Transportation Problem by Dynamic Programming," Transportation Science, INFORMS, vol. 47(3), pages 428-438, August.
    3. Jose L. Andrade-Pineda & David Canca & Pedro L. Gonzalez-R, 2017. "On modelling non-linear quantity discounts in a supplier selection problem by mixed linear integer optimization," Annals of Operations Research, Springer, vol. 258(2), pages 301-346, November.
    4. Xiaolin Huang & Jun Xu & Shuning Wang, 2012. "Exact Penalty and Optimality Condition for Nonseparable Continuous Piecewise Linear Programming," Journal of Optimization Theory and Applications, Springer, vol. 155(1), pages 145-164, October.
    5. Pan, Shenle & Ballot, Eric & Fontane, Frédéric, 2013. "The reduction of greenhouse gas emissions from freight transport by pooling supply chains," International Journal of Production Economics, Elsevier, vol. 143(1), pages 86-94.
    6. Ali, Agha Iqbal & O'Connor, Debra J., 2010. "The impact of distribution system characteristics on computational tractability," European Journal of Operational Research, Elsevier, vol. 200(2), pages 323-333, January.
    7. Benjamin Beach & Robert Hildebrand & Joey Huchette, 2022. "Compact mixed-integer programming formulations in quadratic optimization," Journal of Global Optimization, Springer, vol. 84(4), pages 869-912, December.
    8. Naoto Katayama, 2017. "A Combined Matheuristic for the Piecewise Linear Multicommodity Network Flow Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(06), pages 1-24, December.
    9. Ram Kumar P N, 2013. "On Modeling The Step Fixed-Charge Transportation Problem," Working papers 134, Indian Institute of Management Kozhikode.
    10. Nowak, Maciek & Hewitt, Mike & Bachour, Hussam, 2019. "Mileage bands in freight transportation," European Journal of Operational Research, Elsevier, vol. 272(2), pages 549-564.
    11. F. J. Hwang & Yao-Huei Huang, 2021. "An effective logarithmic formulation for piecewise linearization requiring no inequality constraint," Computational Optimization and Applications, Springer, vol. 79(3), pages 601-631, July.
    12. Ya Ping Fang & Kaiwen Meng & Xiao Qi Yang, 2012. "Piecewise Linear Multicriteria Programs: The Continuous Case and Its Discontinuous Generalization," Operations Research, INFORMS, vol. 60(2), pages 398-409, April.
    13. Hanbazazah, Abdulkader S. & Abril, Luis & Erkoc, Murat & Shaikh, Nazrul, 2019. "Freight consolidation with divisible shipments, delivery time windows, and piecewise transportation costs," European Journal of Operational Research, Elsevier, vol. 276(1), pages 187-201.
    14. Archetti, Claudia & Bertazzi, Luca & Grazia Speranza, M., 2014. "Polynomial cases of the economic lot sizing problem with cost discounts," European Journal of Operational Research, Elsevier, vol. 237(2), pages 519-527.
    15. Silva, Thiago Lima & Camponogara, Eduardo, 2014. "A computational analysis of multidimensional piecewise-linear models with applications to oil production optimization," European Journal of Operational Research, Elsevier, vol. 232(3), pages 630-642.
    16. Fortz, Bernard & Gouveia, Luís & Joyce-Moniz, Martim, 2017. "Models for the piecewise linear unsplittable multicommodity flow problems," European Journal of Operational Research, Elsevier, vol. 261(1), pages 30-42.
    17. Hu, Qian & Lim, Andrew & Zhu, Wenbin, 2015. "The two-dimensional vector packing problem with piecewise linear cost function," Omega, Elsevier, vol. 50(C), pages 43-53.
    18. Zheng, Xiao-Xue & Chang, Ching-Ter, 2021. "Topology design of remote patient monitoring system concerning qualitative and quantitative issues," Omega, Elsevier, vol. 98(C).
    19. Juan Pablo Vielma, 2018. "Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139," Management Science, INFORMS, vol. 64(10), pages 4721-4734, October.
    20. Samir Elhedhli & Zichao Li & James H. Bookbinder, 2017. "Airfreight forwarding under system-wide and double discounts," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 165-183, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:58:y:2010:i:2:p:303-315. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.