Increasing piecewise-linear vs. linear

Provides more information about the piecewise-linear inventory example.

Considering the inventory example in the previous section, we now assume that the cost of extra boats decreases to $350, for instance (because of economies of scale). Optimal solutions with this cost would tend to use “extra” boats before all the “regular” boats have been built. This is not what is needed in real-life situations. Therefore, one must enforce a constraint stipulating that “extra” boats can only be used when all the “regular” boats have been manufactured. This is the model we discuss in this section.

A solution to sailcopwg.mod

For the instance data given in Data for the generalized piecewise-linear model (sailcopwg1.dat), OPL returns the optimal solution 


Final Solution with objective 72200.0000:
  boat = [90.0000 -0.0000 100.0000 0.0000];
  inv = [10.0000 60.0000 0.0000 25.0000 0.0000];

This solution is interesting since it uses “extra” boats as much as possible while trying to minimize the use of boats in inventory. As a result, there is no production in the second and fourth periods. A simple inventory model (sailco.mod) can be generalized further to include more pieces. A generalized piecewise-linear model for the simple inventory problem (sailcopwg.mod) depicts such a model.

A generalized piecewise-linear model for the simple inventory problem (sailcopwg.mod)

int NbPeriods = ...;
range Periods = 1..NbPeriods;
int NbPieces = ...;

float Cost[1..NbPieces] = ...;
float Breakpoint[1..NbPieces-1] = ...;
float Demand[Periods] = ...;
float Inventory = ...;
float InventoryCost = ...;

dvar float+ Boat[Periods];
dvar float+ Inv[0..NbPeriods];


minimize
  sum( t in Periods )
    piecewise(i in 1..NbPieces-1) { 
      Cost[i] -> Breakpoint[i]; 
      Cost[NbPieces] 
    } Boat[t] +
  InventoryCost  * ( sum( t in Periods ) Inv[t] );
   
subject to {
  ctInit:  
    Inv[0] == Inventory;
  forall( t in Periods ) 
    ctBoat: 
      Boat[t] + Inv[t-1] == Inv[t] + Demand[t];
           
}

The interesting feature is the objective function 

minimize
  sum( t in Periods )
    piecewise(i in 1..NbPieces-1) { 
      Cost[i] -> Breakpoint[i]; 
      Cost[NbPieces] 
    } Boat[t] +
  InventoryCost  * ( sum( t in Periods ) Inv[t] );

which is now generic in the number of pieces. Data for the generalized piecewise-linear model (sailcopwg1.dat) describes the same instance data for this model.

Data for the generalized piecewise-linear model (sailcopwg1.dat)

NbPeriods = 4;
Demand = [ 40, 60, 75, 25 ];
NbPieces = 2;
Cost = [ 400, 450 ];
Breakpoint = [ 40 ];
Inventory = 10;
InventoryCost = 20;

Consider now adding a constraint stipulating that the maximum number of boats produced in each period cannot exceed fifty on the instance data depicted in Another instance data item for the generalized piecewise-linear model (sailcopwg2.dat).

Another instance data item for the generalized piecewise-linear model (sailcopwg2.dat)

NbPeriods = 4;
Demand = [ 40, 60, 75, 25 ];
NbPieces = 3;
Cost = [ 300, 400, 450 ];
Breakpoint = [ 30, 40 ];
Inventory = 10;
InventoryCost = 20;

This new constraint has a dramatic effect on the model, which is now infeasible. Piecewise linear functions can be used here to understand where the infeasibility comes from. The key insight is to replace the capacity constraint by yet another piece in the piecewise linear function and to associate a huge cost with this new piece. Instance data to deal with infeasibility (sailcopwg3.dat) depicts the instance data needed to do this:

Instance data to deal with infeasibility (sailcopwg3.dat)

NbPeriods = 4;
Demand = [ 40, 60, 75, 25 ];
NbPieces = 4;
Cost = [ 300, 400, 450, 100000 ];
Breakpoint = [ 30, 40, 50 ];
Inventory = 10;
InventoryCost = 20;

OPL produces the following optimal solution: 


Final Solution with objective 1560600.0000:
  boat = [50.0000 50.0000 65.0000 25.0000];
  inv = [10.0000 20.0000 10.0000 0.0000 0.0000];

which indicates clearly where the bottlenecks (i.e., the third period) are located. The result may help Sailco to plan ahead and take appropriate measures.