IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v79y2021i3d10.1007_s10589-021-00285-4.html
   My bibliography  Save this article

An effective logarithmic formulation for piecewise linearization requiring no inequality constraint

Author

Listed:
  • F. J. Hwang

    (University of Technology Sydney)

  • Yao-Huei Huang

    (Fu Jen Catholic University)

Abstract

One of the commonly used techniques for tackling the nonconvex optimization problems in which all the nonlinear terms are univariate is the piecewise linear approximation by which the nonlinear terms are reformulated. The performance of the linearization technique primarily depends on the quantities of variables and constraints required in the formulation of a piecewise linear function. The state-of-the-art linearization method introduces $$2\lceil \log _2 m\rceil$$ 2 ⌈ log 2 m ⌉ inequality constraints, where m is the number of line segments in the constructed piecewise linear function. This study proposes an effective alternative logarithmic scheme by which no inequality constraint is incurred. The price that more continuous variables are needed in the proposed scheme than in the state-of-the-art method is less than offset by the simultaneous inclusion of a system of equality constraints satisfying the canonical form and the absence of any inequality constraint. Our numerical experiments demonstrate that the developed scheme has the computational superiority, the degree of which increases with m.

Suggested Citation

  • 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.
  • Handle: RePEc:spr:coopap:v:79:y:2021:i:3:d:10.1007_s10589-021-00285-4
    DOI: 10.1007/s10589-021-00285-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-021-00285-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10589-021-00285-4?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Li, Han-Lin & Yu, Chian-Son, 1999. "A global optimization method for nonconvex separable programming problems," European Journal of Operational Research, Elsevier, vol. 117(2), pages 275-292, September.
    2. Li, Han-Lin & Chang, Ching-Ter, 1998. "An approximately global optimization method for assortment problems," European Journal of Operational Research, Elsevier, vol. 105(3), pages 604-612, March.
    3. Lap Mui Ann Chan & Ana Muriel & Zuo-Jun Shen & David Simchi-Levi, 2002. "On the Effectiveness of Zero-Inventory-Ordering Policies for the Economic Lot-Sizing Model with a Class of Piecewise Linear Cost Structures," Operations Research, INFORMS, vol. 50(6), pages 1058-1067, December.
    4. 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.
    5. Li, Han-Lin & Chang, Ching-Ter & Tsai, Jung-Fa, 2002. "Approximately global optimization for assortment problems using piecewise linearization techniques," European Journal of Operational Research, Elsevier, vol. 140(3), pages 584-589, August.
    6. Li, Han-Lin & Fang, Shu-Cherng & Huang, Yao-Huei & Nie, Tiantian, 2016. "An enhanced logarithmic method for signomial programming with discrete variables," European Journal of Operational Research, Elsevier, vol. 255(3), pages 922-934.
    7. Steffen Rebennack, 2016. "Computing tight bounds via piecewise linear functions through the example of circle cutting problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 84(1), pages 3-57, August.
    8. Holmberg, Kaj & Ling, Jonas, 1997. "A Lagrangean heuristic for the facility location problem with staircase costs," European Journal of Operational Research, Elsevier, vol. 97(1), pages 63-74, February.
    9. Aghezzaf, E.H. & Wolsey, L.A., 1994. "Modelling piecewise linear concave costs in a tree partitioning problem," LIDAM Reprints CORE 1088, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. Ossama Kettani & Muhittin Oral, 1990. "Equivalent Formulations of Nonlinear Integer Problems for Efficient Optimization," Management Science, INFORMS, vol. 36(1), pages 115-119, January.
    11. 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.
    12. Han-Lin Li & Hao-Chun Lu & Chia-Hui Huang & Nian-Ze Hu, 2009. "A Superior Representation Method for Piecewise Linear Functions," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 314-321, May.
    13. Daniel Bienstock & Oktay Günlük, 1996. "Capacitated Network Design---Polyhedral Structure and Computation," INFORMS Journal on Computing, INFORMS, vol. 8(3), pages 243-259, August.
    14. Thomas L. Magnanti & Prakash Mirchandani & Rita Vachani, 1995. "Modeling and Solving the Two-Facility Capacitated Network Loading Problem," Operations Research, INFORMS, vol. 43(1), pages 142-157, February.
    15. Holmberg, Kaj, 1994. "Solving the staircase cost facility location problem with decomposition and piecewise linearization," European Journal of Operational Research, Elsevier, vol. 75(1), pages 41-61, May.
    16. Tsai, Jung-Fa, 2007. "An optimization approach for supply chain management models with quantity discount policy," European Journal of Operational Research, Elsevier, vol. 177(2), pages 982-994, March.
    17. Han-Lin Li & Yao-Huei Huang & Shu-Cherng Fang, 2013. "A Logarithmic Method for Reducing Binary Variables and Inequality Constraints in Solving Task Assignment Problems," INFORMS Journal on Computing, INFORMS, vol. 25(4), pages 643-653, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shao, Yu & Zhou, Xinhong & Yu, Tingchao & Zhang, Tuqiao & Chu, Shipeng, 2024. "Pump scheduling optimization in water distribution system based on mixed integer linear programming," European Journal of Operational Research, Elsevier, vol. 313(3), pages 1140-1151.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Ram Kumar P N, 2013. "On Modeling The Step Fixed-Charge Transportation Problem," Working papers 134, Indian Institute of Management Kozhikode.
    6. Han-Lin Li & Yao-Huei Huang & Shu-Cherng Fang, 2017. "Linear Reformulation of Polynomial Discrete Programming for Fast Computation," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 108-122, February.
    7. 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.
    8. Tsai, Jung-Fa, 2007. "An optimization approach for supply chain management models with quantity discount policy," European Journal of Operational Research, Elsevier, vol. 177(2), pages 982-994, March.
    9. 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.
    10. Christina N. Burt & Lou Caccetta, 2014. "Equipment Selection for Surface Mining: A Review," Interfaces, INFORMS, vol. 44(2), pages 143-162, April.
    11. Li, Han-Lin & Fang, Shu-Cherng & Huang, Yao-Huei & Nie, Tiantian, 2016. "An enhanced logarithmic method for signomial programming with discrete variables," European Journal of Operational Research, Elsevier, vol. 255(3), pages 922-934.
    12. Feng Li & Zhou Xu & Zhi-Long Chen, 2020. "Production and Transportation Integration for Commit-to-Delivery Mode with General Shipping Costs," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1012-1029, October.
    13. Ioannis Gamvros & Bruce Golden & S. Raghavan, 2006. "The Multilevel Capacitated Minimum Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 348-365, August.
    14. Nicolas Andalaft & Pablo Andalaft & Monique Guignard & Adrian Magendzo & Alexis Wainer & Andres Weintraub, 2003. "A Problem of Forest Harvesting and Road Building Solved Through Model Strengthening and Lagrangean Relaxation," Operations Research, INFORMS, vol. 51(4), pages 613-628, August.
    15. Alejandro Montoya & Mario C. Vélez–Gallego & Juan G. Villegas, 2016. "Multi-product capacitated facility location problem with general production and building costs," Netnomics, Springer, vol. 17(1), pages 47-70, July.
    16. Wang, Julong & Liu, Zhixue & Li, Feng, 2024. "Integrated production and transportation scheduling problem under nonlinear cost structures," European Journal of Operational Research, Elsevier, vol. 313(3), pages 883-904.
    17. Nowak, Maciek & Hewitt, Mike & Bachour, Hussam, 2019. "Mileage bands in freight transportation," European Journal of Operational Research, Elsevier, vol. 272(2), pages 549-564.
    18. Sanjay Jena & Jean-François Cordeau & Bernard Gendron, 2015. "Modeling and solving a logging camp location problem," Annals of Operations Research, Springer, vol. 232(1), pages 151-177, September.
    19. Sridhar, Varadharajan & Park, June S., 2000. "Benders-and-cut algorithm for fixed-charge capacitated network design problem," European Journal of Operational Research, Elsevier, vol. 125(3), pages 622-632, September.
    20. Fang Yang & Yao-Huei Huang, 2021. "An optimization approach for winner determination problem considering transportation cost discounts," Journal of Global Optimization, Springer, vol. 80(3), pages 711-728, July.

    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:spr:coopap:v:79:y:2021:i:3:d:10.1007_s10589-021-00285-4. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.