A nonlinear function can be approximated by a series of linear segments that follow the gradient of the function.  This is called a piecewise-linear approximation of the function.

Solving with NLP Versus LP/MIP Methods

If your problem includes nonlinear functions of the decision variables, you'll normally have to use a Solver engine designed for smooth nonlinear optimization to find the optimal solution.  However, nonlinear optimization methods are usually slower, and may be less reliable than linear programming methods. 

If your problem involves just a few nonlinear functions that can be approximated by a small number of linear segments, you may be better off using piecewise-linear approximations of these functions. Piecewise-linear approximations do introduce binary integer variables into your model; hence mixed-integer linear programming methods must be used to find an optimal solution.  But with modern LP/MIP solvers that efficiently handle sets of binary integer variables, you can often find solutions very quickly to problems involving such approximations.

Example of Quantity Discounts

An example of a piecewise-linear approximation is shown on page 270 (approximately) of the Frontline Solvers User Guide, which involves purchasing parts from a vendor, or making shipments through a carrier who offers discounts at various quantity levels.  In that example, the function being approximated is convex, so the piecewise-linear approximation is simplified.

General (Non-Convex) Function Example

For an example of a piecewise-linear approximation of a function that is not convex, please click to open or download PiecewiseLinear.xls.  In this example, the function value is calculated in cell D6, and its graph is shown on the worksheet.  Binary integer variables at cells G9:G18 and I9:I17 are used in constraints to define the line segments that make up this function.  If you select Tools Solver... and click Solve, the function value will be minimized using mixed-integer linear programming methods.  (As you can see by inspected the graph, the function's minimum value is -10.)

General Algebraic Formulation

Here is a general algebraic formulation of a piecewise-linear approximation of a function F(x), where the "breakpoints" between line segments have x values of b1, b2, ..., bn, and the slopes of the line segments have values f(b1), f(b2), ..., f(bn):

  • Add n decision variables z1, z2, ..., zn, all non-negative.
  • Add n-1 decision variables y1, y2, ..., yn-1, all binary integer. 
  • Wherever F(x) occurs, replace it with z1*f(b1) + z2*f(b2) + ... + zn*f(bn). 
  • Add constraints
    z1 <= y1, z2 <= y1 + y2, z3 <= y2 + y3, ....zn-1 <= yn-2 + yn-1 , zn <= yn-1 
  • Add constraints
    y1 + y2 + .... + yn-1 = 1 and z1 + z2 + .... + zn = 1 
  • Define x = z1*b1 + z2*b2 + .... + zn*bn

For an example of this formulation, examine the formulas in PiecewiseLinear.xls.

< Back to Support Center for Frontline Systems Excel Solvers