piecewise linearisation

Psme Stijns

January 27, 2012 10:45

do you have an school example of doing piecewise linearisation by adding binary variables and linear equations

0

• 

  Daniel Fylstra

  February 03, 2012 03:36

  Using Piecewise-Linear Functions

  Many problems involve “stepped” price schedules or quantity discounts, where you might at first expect that a non-smooth function such as CHOOSE or LOOKUP is required to express the relationship.  You might be surprised to learn that you can instead use linear functions and binary integer variables to express the relationship.

  For example, you might be purchasing parts from a vendor who offers discounts at various quantity levels.  The graph below represents such a discount schedule, with three prices and three “breakpoints.”  You have a decision variable x representing the quantity to order.

  

  The three prices (slopes of the line segments) are c₁, c₂ and c₃.  V₁ represents a fixed initial cost; V₂ and V₃ are also constant in the problem and can be computed from:

  V₂  = V₁  +  c₁*B₁ - c₂*B₁
  V₃  = V₂  +  c₂*B₂ - c₃*B₂

  In the model, the variable x is replaced by three variables x₁, x₂ and x₃, representing the quantity ordered or shipped at each possible price.  Also included are three 0-1 or binary integer variables y₁, y₂ and y₃.  Since you want to minimize costs, the objective and constraints are:

  Minimize  V₁*y₁  +  V₂*y₂  +  V₃*y₃  +  c₁*x₁  +   c₂*x₂  +   c₃*x₃
  Subject to  x₁  <=  B₁*y₁,   x₂  <=  B₂*y₂,   x₃  <=  B₃*y₃

  If the cost curve is concave as shown above, this is sufficient; but if the function is non-concave (it may vary up and down), additional “fill constraints” are needed:

  y₁  + y₂  + y₃  <=  1
  x₁  <=  B₁*y₂
  x₂  <=  B₂*y₃

  This approach is called a “piecewise-linear” function.  It can be used in place of a CHOOSE or LOOKUP function, and it results in a linear integer model instead of a difficult-to-solve non-smooth model.  Piecewise-linear functions can also be used to approximate a smooth nonlinear function, by using line segments with slopes matching the gradient of the nonlinear function at various intermediate points.

  0

Please sign in to leave a comment.