A Comparison of Mixed-Integer Programming Models for Nonconvex Piecewise Linear Cost Minimization Problems

Keely L. Croxton
Keely L. Croxton
[email protected]
Fisher College of Business, The Ohio State University, Columbus, Ohio 43210
Search for more papers by this author
,
Bernard Gendron
Bernard Gendron
[email protected]
Département d'informatique, et de recherche opérationnelle, and Centre de recherche sur les transports, Université de Montréal, Montréal, Quebec H3C 3J7, Canada
Search for more papers by this author
,
Thomas L. Magnanti
Thomas L. Magnanti
[email protected]
School of Engineering, and Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts
Search for more papers by this author

Fisher College of Business, The Ohio State University, Columbus, Ohio 43210

Département d'informatique, et de recherche opérationnelle, and Centre de recherche sur les transports, Université de Montréal, Montréal, Quebec H3C 3J7, Canada

Search for more papers by this author

Thomas L. Magnanti

[email protected]

School of Engineering, and Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts

Search for more papers by this author

Published Online:1 Sep 2003https://doi.org/10.1287/mnsc.49.9.1268.16570

Abstract

We study a generic minimization problem with separable nonconvex piecewise linear costs, showing that the linear programming (LP) relaxation of three textbook mixed-integer programming formulations each approximates the cost function by its lower convex envelope. We also show a relationship between this result and classical Lagrangian duality theory.

Cited by
- Integration of Grid-Scaled Power-to-Heat Technology in Korea’s Power System: Operational Advantages and Future Insights for Renewable Energy Enhancement
  3 April 2026 | Energies, Vol. 19, No. 7
- When Deep Learning Meets Polyhedral Theory: A Survey
  Joey Huchette,
  Gonzalo Muñoz,
  Thiago Serra,
  Calvin Tsay
  12 March 2026 | INFORMS Journal on Computing, Vol. 0, No. 0
- Spatial Branch-and-Bound for Nonconvex Separable Piecewise Linear Optimization
  Thomas Hübner,
  Akshay Gupte,
  Steffen Rebennack
  27 June 2025 | INFORMS Journal on Computing, Vol. 38, No. 2
- Balancing Workload Fairness in Task Assignment: Modeling via Piecewise Linear Approximation
  10 February 2026 | Applied Sciences, Vol. 16, No. 4
- Building Formulations for Piecewise Linear Relaxations of Nonlinear Functions
  Bochuan Lyu,
  Illya V. Hicks,
  Joey Huchette
  24 April 2025 | Operations Research, Vol. 74, No. 1
- A data-driven approach for strategic inventory placement in multi-echelon supply networks
  European Journal of Operational Research, Vol. 328, No. 2
- A mixed-integer optimization formulation for buyer formation
  Computers & Operations Research, Vol. 183
- A profit maximization problem of equipment rental and scheduling with split services
  15 October 2024 | IISE Transactions, Vol. 57, No. 10
- Constructing Optimal Piecewise Quadratic Approximations for Enhancing Deterministic Global Optimization
  Yingkai Song,
  Christos T. Maravelias
  2 September 2025 | INFORMS Journal on Computing, Vol. 0, No. 0
- New and tractable formulations for the eco-driving and the eco-routing-and-driving problems
  European Journal of Operational Research, Vol. 321, No. 2
- 50 years of Operations Research for the tactical planning of consolidation-based freight transportation
  EURO Journal on Transportation and Logistics, Vol. 14
- A comparison of alternative models for solving a non-linear single plant Hydro Unit Commitment problem
  Computers & Operations Research, Vol. 165
- Pump scheduling optimization in water distribution system based on mixed integer linear programming
  European Journal of Operational Research, Vol. 313, No. 3
- Bernard Gendron and Operations Research
  28 June 2024
- Models for Network Flow and Network Design Problems with Piecewise Linear Costs
  28 June 2024
- A Robust Two-Stage Model for the Urban Air Mobility Flight Scheduling Problem
  22 May 2024
- Scheduling a set of jobs with convex piecewise linear cost functions on a single-batch-processing machine
  Omega, Vol. 122
- Exact algorithms for multi-module capacitated lot-sizing problem, and its generalizations with two-echelons and piecewise concave production costs
  23 January 2023 | IISE Transactions, Vol. 55, No. 12
- Green Data Analytics of Supercomputing from Massive Sensor Networks: Does Workload Distribution Matter?
  Zhiling Guo,
  Jin Li,
  Ram Ramesh
  7 March 2023 | Information Systems Research, Vol. 34, No. 4
- Comparing perspective reformulations for piecewise-convex optimization
  Operations Research Letters, Vol. 51, No. 6
- An optimization method to solve a fully intuitionistic fuzzy non-linear separable programming problem
  30 November 2023 | RAIRO - Operations Research, Vol. 57, No. 6
- Transportation strategies for dynamic lot sizing: single or multiple modes?
  13 December 2022 | International Journal of Production Research, Vol. 61, No. 20
- Nonconvex Piecewise Linear Functions: Advanced Formulations and Simple Modeling Tools
  Joey Huchette,
  Juan Pablo Vielma
  31 May 2022 | Operations Research, Vol. 71, No. 5
- Optimizing bilinear multi-source water supply systems using mixed-integer linear programming approximations: An analysis of the Israeli seawater desalination array
  Advances in Water Resources, Vol. 178
- Eco-routing problem for the delivery of perishable products
  Computers & Operations Research, Vol. 154
- New formulations for the Scheduled Service Network Design Problem
  Transportation Research Part B: Methodological, Vol. 172
- On piecewise linear approximations of bilinear terms: structural comparison of univariate and bivariate mixed-integer programming formulations
  3 November 2022 | Journal of Global Optimization, Vol. 85, No. 4
- Economic model predictive control based on lattice trajectory piecewise linear model for wastewater treatment plants
  Journal of Process Control, Vol. 124
- Mixed-Integer Programming Formulations for Piecewise Linear Functions
  23 September 2022
- Consolidation-Based Modeling for the Scheduled Service Network Design Problem
  21 July 2023
- Compact mixed-integer programming formulations in quadratic optimization
  13 June 2022 | Journal of Global Optimization, Vol. 84, No. 4
- Piecewise linear neural networks and deep learning
  9 June 2022 | Nature Reviews Methods Primers, Vol. 2, No. 1
- Optimal Design of Refinery Hydrogen Networks: Reduced Superstructure and Effective Algorithm
  9 November 2022 | Industrial & Engineering Chemistry Research, Vol. 61, No. 46
- The Bicycle Network Improvement Problem
  Journal of Transportation Engineering, Part A: Systems, Vol. 148, No. 11
- A Compensation Mechanism for EV Flexibility Services using Discrete Utility Functions
- An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs
  Zachary Steever,
  Chase Murray,
  Junsong Yuan,
  Mark Karwan,
  Marco Lübbecke
  16 March 2022 | INFORMS Journal on Computing, Vol. 34, No. 4
- Multi-market portfolio optimization with conditional value at risk
  European Journal of Operational Research, Vol. 300, No. 1
- Optimizing Camera Placements for Overlapped Coverage with 3D Camera Projections
- Single Allocation Hub Location with Heterogeneous Economies of Scale
  Borzou Rostami,
  Masoud Chitsaz,
  Okan Arslan,
  Gilbert Laporte,
  Andrea Lodi
  28 December 2021 | Operations Research, Vol. 70, No. 2
- Eco-Routing Problem for the Delivery of Perishable Products
  SSRN Electronic Journal, Vol. 13
- Strategic Inventory Placement in Large-Scale Multi-Echelon Networks: A Sampling-Based Approach
  SSRN Electronic Journal, Vol. 68
- New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear Approximation
  9 January 2022 | Mathematics, Vol. 10, No. 2
- Transformation and Linearization Techniques in Optimization: A State-of-the-Art Survey
  17 January 2022 | Mathematics, Vol. 10, No. 2
- Optimistic optimization for continuous nonconvex piecewise affine functions
  Automatica, Vol. 125
- Piecewise Linear Cost Network Design
  9 December 2020
- Automated Repair of Layout Bugs in Web Pages with Linear Programming
  11 May 2021
- A MIP Model for Freight Consolidation in Road Transportation Considering Outsourced Fleet
  14 August 2021
- Topology design of remote patient monitoring system concerning qualitative and quantitative issues
  Omega, Vol. 98
- Piecewise linear bounding functions in univariate global optimization
  19 August 2020 | Soft Computing, Vol. 24, No. 23
- Smart home design flexibility as an enabler of sustainability and the reception in Sulaiymaniah, Kurdistan Region-Iraq
  18 October 2020 | Journal of Building Pathology and Rehabilitation, Vol. 5, No. 1
- Improved Basic Block Reordering
  IEEE Transactions on Computers, Vol. 69, No. 12
- Decomposition‐based approximation algorithms for the one‐warehouse multi‐retailer problem with concave batch order costs
  31 July 2020 | Naval Research Logistics (NRL), Vol. 67, No. 7
- Surrogate-model based MILP for the optimal design of ethylene production from shale gas
  Computers & Chemical Engineering, Vol. 141
- Berth Allocation and Quay Crane Assignment for the Trade-off Between Service Efficiency and Operating Cost Considering Carbon Emission Taxation
  Tingsong Wang,
  Yuquan Du,
  Debin Fang,
  Zhi-Chun Li
  25 June 2020 | Transportation Science, Vol. 54, No. 5
- Optimizing production capacity and safety stocks in general acyclic supply chains
  Computers & Operations Research, Vol. 120
- On the Derivation of Continuous Piecewise Linear Approximating Functions
  Lingxun Kong,
  Christos T Maravelias
  5 May 2020 | INFORMS Journal on Computing, Vol. 32, No. 3
- Mixed-integer nonseparable piecewise linear models for the hydropower production function in the Unit Commitment problem
  Electric Power Systems Research, Vol. 182
- Piecewise Linear Function Fitting via Mixed-Integer Linear Programming
  Steffen Rebennack,
  Vitaliy Krasko
  23 December 2019 | INFORMS Journal on Computing, Vol. 32, No. 2
- A simulation-optimization approach for the stochastic discrete cost multicommodity flow problem
  1 May 2019 | Engineering Optimization, Vol. 52, No. 3
- Decision Support for Material Procurement
  25 September 2020
- Operations Research Model Formulation for Road Maintenance Case
  23 December 2019 | Information Technology and Management Science, Vol. 22
- A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function
  Journal of Cleaner Production, Vol. 236
- An exact approach for the multicommodity network optimization problem with a step cost function
  5 August 2019 | RAIRO - Operations Research, Vol. 53, No. 4
- Integer programming for urban design
  European Journal of Operational Research, Vol. 274, No. 3
- A modeling framework and local search solution methodology for a production-distribution problem with supplier selection and time-aggregated quantity discounts
  Applied Mathematical Modelling, Vol. 68
- Multiple criteria decision making for linguistic judgments with importance quantifier guided ordered weighted averaging operator
  Information Sciences, Vol. 474
- Linearization of Nonlinear Functions
  10 December 2019
- Mileage bands in freight transportation
  European Journal of Operational Research, Vol. 272, No. 2
- Optimal ordering and clearance strategies under demand uncertainty
  IFAC-PapersOnLine, Vol. 52, No. 13
- An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs
  SSRN Electronic Journal, Vol. 4
- Embedding Formulations and Complexity for Unions of Polyhedra
  Juan Pablo Vielma
  8 November 2017 | Management Science, Vol. 64, No. 10
- Sequential Global Linear Programming Algorithm for Continuous Piecewise Linear Programming
- A Solution Approach to the Nonconvex Piecewise Linear Network Flow Problems
- Objective Variation Network Simplex Algorithm for Concave Continuous Piecewise Linear Network Flow Problems
  24 February 2018
- A Combined Matheuristic for the Piecewise Linear Multicommodity Network Flow Problem
  18 December 2017 | Asia-Pacific Journal of Operational Research, Vol. 34, No. 06
- On modelling non-linear quantity discounts in a supplier selection problem by mixed linear integer optimization
  5 August 2015 | Annals of Operations Research, Vol. 258, No. 2
- MULTICOMMODITY NETWORK FLOWS WITH NONCONVEX ARC COSTS
  1 September 2017 | Pesquisa Operacional, Vol. 37, No. 3
- Models for the piecewise linear unsplittable multicommodity flow problems
  European Journal of Operational Research, Vol. 261, No. 1
- Discrete intermodal freight transportation network design with route choice behavior of intermodal operators
  Transportation Research Part B: Methodological, Vol. 95
- A parametric simplex algorithm for biobjective piecewise linear programming problems
  Journal of Industrial & Management Optimization, Vol. 13, No. 2
- Energy optimization of water supply system scheduling: Novel MINLP model and efficient global optimization algorithm
  8 June 2016 | AIChE Journal, Vol. 62, No. 12
- Sparse signal reconstruction via concave continuous piecewise linear programming
  Digital Signal Processing, Vol. 54
- A modified hill detouring algorithm for hinging hyperplanes minimization
- On the convex piecewise linear unsplittable multicommodity flow problem
- Performance Measurement of a Rotavirus Vaccine Supply Chain Design by the Integration of Production Capacity into the Guaranteed Service Approach
  SSRN Electronic Journal, Vol. 34
- GUB Flow Cover Inequalities and an Exact Algorithm for Transportation Service Procurement Problem with Total Quantity Discounts
  SSRN Electronic Journal, Vol. 154
- A novel adaptive surrogate modeling‐based algorithm for simultaneous optimization of sequential batch process scheduling and dynamic operations
  12 August 2015 | AIChE Journal, Vol. 61, No. 12
- On the hop-constrained survivable network design problem with reliable edges
  Computers & Operations Research, Vol. 64
- Flexible electricity tariffs: Power and energy price signals designed for a smarter grid
  Energy, Vol. 93
- Method of hill tunneling via simplex centroid for continuous piecewise linear programming
- An Efficient Decomposition Method for the Integrated Dispatch of Generation and Load
  IEEE Transactions on Power Systems, Vol. 30, No. 6
- A branch-cut-and-price algorithm for the piecewise linear transportation problem
  European Journal of Operational Research, Vol. 245, No. 3
- Stochastic lot sizing problem with controllable processing times
  Omega, Vol. 53
- Piecewise Linear Formulations for Downlink Wireless OFDMA Networks
  8 August 2015
- The two-dimensional vector packing problem with piecewise linear cost function
  Omega, Vol. 50
- Global Optimization for Transport Network Expansion and Signal Setting
  Mathematical Problems in Engineering, Vol. 2015
- A solution procedure for mixed-integer nonlinear programming formulation of supply chain planning with quantity discounts under demand uncertainty
  18 February 2013 | International Journal of Systems Science, Vol. 45, No. 11
- Lot Sizing with Piecewise Concave Production Costs
  Esra Koca,
  Hande Yaman,
  M. Selim Aktürk
  20 May 2014 | INFORMS Journal on Computing, Vol. 26, No. 4
- Global optimization for sustainable design and synthesis of algae processing network for CO 2 mitigation and biofuel production using life cycle optimization
  9 June 2014 | AIChE Journal, Vol. 60, No. 9
- Polynomial cases of the economic lot sizing problem with cost discounts
  European Journal of Operational Research, Vol. 237, No. 2
- Environmental and economic issues arising from the pooling of SMEs’ supply chains: case study of the food industry in western France
  13 September 2012 | Flexible Services and Manufacturing Journal, Vol. 26, No. 1-2
- Integrated Scheduling and Dynamic Optimization by Stackelberg Game: Bilevel Model Formulation and Efficient Solution Algorithm
  19 March 2014 | Industrial & Engineering Chemistry Research, Vol. 53, No. 13
- A computational analysis of multidimensional piecewise-linear models with applications to oil production optimization
  European Journal of Operational Research, Vol. 232, No. 3
- Optimal Design and Synthesis of Algal Biorefinery Processes for Biological Carbon Sequestration and Utilization with Zero Direct Greenhouse Gas Emissions: MINLP Model and Global Optimization Algorithm
  17 January 2014 | Industrial & Engineering Chemistry Research, Vol. 53, No. 4
- Supply Chain Planning Models
  21 October 2013
- Locally ideal formulations for piecewise linear functions with indicator variables
  Operations Research Letters, Vol. 41, No. 6
- The piecewise linear optimization polytope: new inequalities and intersection with semi-continuous constraints
  17 February 2012 | Mathematical Programming, Vol. 141, No. 1-2
- Solving the Single-Sink, Fixed-Charge, Multiple-Choice Transportation Problem by Dynamic Programming
  Tue R. L. Christensen,
  Kim Allan Andersen,
  Andreas Klose,
  2 August 2012 | Transportation Science, Vol. 47, No. 3
- A stabilized structured Dantzig–Wolfe decomposition method
  20 December 2012 | Mathematical Programming, Vol. 140, No. 1
- Integrated Scheduling and Dynamic Optimization of Sequential Batch Processes with Online Implementation
  7 February 2013 | AIChE Journal, Vol. 59, No. 7
- Planning and scheduling of flexible process networks under uncertainty with stochastic inventory: MINLP models and algorithm
  9 October 2012 | AIChE Journal, Vol. 59, No. 5
- The reduction of greenhouse gas emissions from freight transport by pooling supply chains
  International Journal of Production Economics, Vol. 143, No. 1
- Mixed-integer nonlinear optimization
  2 April 2013 | Acta Numerica, Vol. 22
- Frequency-regulating reserve constrained unit commitment for an isolated power system
  IEEE Transactions on Power Systems, Vol. 28, No. 2
- A Review of Piecewise Linearization Methods
  Mathematical Problems in Engineering, Vol. 2013
- Exact Penalty and Optimality Condition for Nonseparable Continuous Piecewise Linear Programming
  30 March 2012 | Journal of Optimization Theory and Applications, Vol. 155, No. 1
- Models and heuristics for the k ‐degree constrained minimum spanning tree problem with node‐degree costs
  1 August 2011 | Networks, Vol. 60, No. 1
- Piecewise Linear Multicriteria Programs: The Continuous Case and Its Discontinuous Generalization
  Ya Ping Fang,
  Kaiwen Meng,
  Xiao Qi Yang,
  1 April 2012 | Operations Research, Vol. 60, No. 2
- Enhancing discretized formulations: the knapsack reformulation and the star reformulation
  9 August 2011 | TOP, Vol. 20, No. 1
- Design of assembly lines with the concurrent consideration of productivity and upper extremity musculoskeletal disorders using linear models
  Computers & Industrial Engineering, Vol. 62, No. 2
- Linear programming relaxations of a network flow problem with applications in machinery industry
- Computing Near-Optimal Policies in Generalized Joint Replenishment
  Daniel Adelman,
  Diego Klabjan,
  2 February 2011 | INFORMS Journal on Computing, Vol. 24, No. 1
- Exact approaches to the single‐source network loading problem
  25 November 2011 | Networks, Vol. 59, No. 1
- Exact algorithms for integrated facility location and production planning problems
  31 May 2011 | Naval Research Logistics (NRL), Vol. 58, No. 5
- Modeling disjunctive constraints with a logarithmic number of binary variables and constraints
  2 July 2009 | Mathematical Programming, Vol. 128, No. 1-2
- Global optimization of mixed-integer nonlinear programming for engineering design problems
- Stochastic inventory management for tactical process planning under uncertainties: MINLP models and algorithms
  12 April 2011 | AIChE Journal, Vol. 57, No. 5
- Modeling and solving a multimodal transportation problem with flexible‐time and scheduled services
  7 December 2010 | Networks, Vol. 57, No. 1
- Spanning Trees with Node Degree Dependent Costs and Knapsack Reformulations
  Electronic Notes in Discrete Mathematics, Vol. 36
- Mixed-Integer Models for Nonseparable Piecewise-Linear Optimization: Unifying Framework and Extensions
  Juan Pablo Vielma,
  Shabbir Ahmed,
  George Nemhauser,
  28 October 2009 | Operations Research, Vol. 58, No. 2
- Integrated multi‐echelon supply chain design with inventories under uncertainty: MINLP models, computational strategies
  15 September 2009 | AIChE Journal, Vol. 56, No. 2
- An effective linear approximation method for separable programming problems
  Applied Mathematics and Computation, Vol. 215, No. 4
- Global optimization for first order Markov Random Fields with submodular priors
  Discrete Applied Mathematics, Vol. 157, No. 16
- A Superior Representation Method for Piecewise Linear Functions
  Han-Lin Li,
  Hao-Chun Lu,
  Chia-Hui Huang,
  Nian-Ze Hu,
  13 November 2008 | INFORMS Journal on Computing, Vol. 21, No. 2
- A continuous optimization model for a joint problem of pricing and resource allocation
  28 April 2009 | RAIRO - Operations Research, Vol. 43, No. 2
- 0–1 reformulations of the multicommodity capacitated network design problem
  Discrete Applied Mathematics, Vol. 157, No. 6
- Nested Partitions and Its Applications to the Intermodal Hub Location Problem
  25 May 2009
- Nonconvex piecewise linear knapsack problems
  European Journal of Operational Research, Vol. 192, No. 1
- Leveraging Enterprise-Wide Purchase Volumes: Optimal Supplier Assignment in Multi-Division Firms
  SSRN Electronic Journal, Vol. 42
- A multi-stage facility location problem with staircase costs and splitting of commodities: model, heuristic approach and application
  5 December 2007 | OR Spectrum, Vol. 30, No. 4
- Hybrid Nested Partitions and Mathematical Programming Approach and Its Applications
  IEEE Transactions on Automation Science and Engineering, Vol. 5, No. 4
- Network design and flow problems with cross-arc costs
  European Journal of Operational Research, Vol. 189, No. 3
- A simplified combined-cycle unit model for mixed integer linear programming-based unit commitment
- Solving the Capacitated Local Access Network Design Problem
  F. Sibel Salman,
  R. Ravi,
  John N. Hooker,
  25 January 2008 | INFORMS Journal on Computing, Vol. 20, No. 2
- Nonconvex, lower semicontinuous piecewise linear optimization
  Discrete Optimization, Vol. 5, No. 2
- A special ordered set approach for optimizing a discontinuous separable piecewise linear function
  Operations Research Letters, Vol. 36, No. 2
- Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints
- Model-based investment planning model for stepwise capacity expansions of chemical plants
- An Infinite-Dimensional Linear Programming Algorithm for Deterministic Semi-Markov Decision Processes on Borel Spaces
  Diego Klabjan,
  Daniel Adelman,
  1 August 2007 | Mathematics of Operations Research, Vol. 32, No. 3
- Joint optimization of pricing and resource allocation in competitive telecommunications networks
  16 April 2007 | Networks, Vol. 50, No. 1
- Multiattribute electronic procurement using goal programming
  European Journal of Operational Research, Vol. 179, No. 2
- Variable Disaggregation in Network Flow Problems with Piecewise Linear Costs
  Keely L. Croxton,
  Bernard Gendron,
  Thomas L. Magnanti,
  1 February 2007 | Operations Research, Vol. 55, No. 1
- Multicommodity network design with discrete node costs
  11 October 2006 | Networks, Vol. 49, No. 1
- On the capacitated concentrator location problem: a reformulation by discretization
  Computers & Operations Research, Vol. 33, No. 5
- Inventory placement in acyclic supply chain networks
  Operations Research Letters, Vol. 34, No. 2
- A Note on Search by Objective Relaxation
- Separable Concave Optimization Approximately Equals Piecewise Linear Optimization

Volume 49, Issue 9

September 2003

Pages 1121-1273

Article Information

Metrics

Information

Received:July 08, 2002
Published Online:September 01, 2003

Cite as

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 49(9):1268-1273.

https://doi.org/10.1287/mnsc.49.9.1268.16570

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Comparison of Mixed-Integer Programming Models for Nonconvex Piecewise Linear Cost Minimization Problems

Abstract

Volume 49, Issue 9

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News