The purchasing model using piecewise linear expressions

The Xpress MIP solver supports a special construct for the formulation of piecewise linear expressions like the price curves of individual suppliers in the purchase problem that we have seen in the previous section. With this construct the modeler no longer needs to define the weight variables associated with the break points of piecewise linear expressions, these are handled internally by the solver.

With Mosel there are three different ways of specifying piecewise linear expressions, namely via

1. lists of points (the coordinates (B_sb,CB_sb) of cost breakpoints per supplier s in our example); the points must be given in increasing order of X-axis values, if all points are different they represent a continuous function; discontinuous functions can be modeled by duplicating a point;
2. slopes (in our case slopes are given by the unit cost values COST_sb); this form defines a continuous function with its starting point at the origin of the coordinate system, that is the point (0,0);
3. linear segments (a list of linear expressions, in our example a function of the cumulative cost CB_sb at the start of the segment and the slope COST_sb); this form can be used to represent discontinuous piecewise linear functions where there are 'jumps' at the breakpoints.

The supplier price functions in the purchase problem are continuous with start at 0, so all three forms can be used. The following Mosel implementation (file purch_pwl.mos) uses the first formulation variant for the pwlin construct. In place of the binary weight variables there now is a single variable pay_s per supplier for the cost incurred from this supplier that is used for the formulation of the objective function, all else remains as before. It should be noted that the solver is started via the Xpress NLP module (see Section Solvers ) that handles the transformation of the pwlin construct into matrix form, however, this problem will be solved as a MIP.

model "Purchase pwl"
 uses "mmxnlp"

 declarations
   NB = 3
   BREAK1 = 1..NB                     ! Price breaks
   BREAK0 = 0..NB                     ! Price breaks including 0
   SUPPL = 1..3                       ! Suppliers

   COST: array(SUPPL,BREAK1) of real  ! Unit cost
   B: array(SUPPL,BREAK0) of real     ! Breakpoints (quantities at which unit
                                      ! cost changes)
   CB: array(SUPPL,BREAK0) of real    ! Total cost at break points
   MAXPERC: array(SUPPL) of real      ! Maximum percentages for each supplier
   REQ: real                          ! Total quantity required

   buy: array(SUPPL) of mpvar         ! Quantity to purchase from supplier s
   pay: array(SUPPL) of mpvar         ! Cost incurred from supplier s
 end-declarations

 initializations from 'purchase.dat'
   COST B MAXPERC REQ
 end-initializations

! Calculate total cost at breakpoints
 forall(s in SUPPL) do
   CB(s,0):= 0
   forall(b in BREAK1) CB(s,b):= CB(s,b-1) + COST(s,b)*(B(s,b)-B(s,b-1))
 end-do

! Objective: sum of costs*weights
 MinCost:= sum(s in SUPPL) pay(s)

! Define relation between bought quantities and price paid per supplier
 forall(s in SUPPL)
 ! Formulation of pwlin via breakpoint coordinates
   pay(s) = pwlin(buy(s), union(b in BREAK0) [B(s,b),CB(s,b)])

! The minimum quantity that must be bought
 Demand:= sum(s in SUPPL) buy(s) >= REQ

! No more than the maximum percentage from each supplier
 forall(s in SUPPL) buy(s) <= MAXPERC(s)*REQ/100.0

 minimize(MinCost)              ! Solve the MIP-problem

 writeln("Minimum total cost: ", getobjval)
 forall(s in SUPPL) writeln(" buy(",s,"): ", getsol(buy(s)), " cost: ", pay(s).sol)

end-model

The alternative forms of the pwlin specification are

! Formulation of pwlin via slopes
  pay(s) = pwlin(buy(s), union(b in 1..(NB-1)) [B(s,b)], union(b in BREAK1) [COST(s,b)])

and

! Formulation of pwlin via segments
  pay(s) = pwlin(union(b in 0..(NB-1)) [pws(B(s,b),CB(s,b)+COST(s,b+1)*(buy(s)-B(s,b)))])

where pws states a segment of a piecewise linear function.