An inventory application with piecewise linear functions

Describes the problem, with its solution, and presents the model and data files.

This section introduces piecewise linear programs using an inventory application. This piecewise linear application is adapted from Applications and Algorithms by W. Winston (see the Bibliography).

The company Sailco must determine how many sailboats to produce over four time periods. The demand for the four periods is known (40, 60, 75, 25) and, in addition, an inventory of ten boats is available initially. In each period, Sailco can produce 40 boats at a cost of $400 per boat. Additional boats can be produced at a cost of $450 per boat. The inventory cost is $20 per boat and per period. A simple inventory model (sailco.mod) describes a linear program for this application and Data for the simple inventory model (sailco.dat)describes the instance data.

A simple inventory model (`sailco.mod`)

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

float Demand[Periods] = ...;
float RegularCost = ...;
float ExtraCost = ...;
float Capacity = ...;
float Inventory = ...;
float InventoryCost = ...;

dvar float+ RegulBoat[Periods];
dvar float+ ExtraBoat[Periods];
dvar float+ Inv[0..NbPeriods];


minimize
   RegularCost * 
   ( sum( t in Periods ) RegulBoat[t] ) +
   ExtraCost * 
   ( sum( t in Periods ) ExtraBoat[t] ) +
   InventoryCost * 
   ( sum(t in Periods ) Inv[t] );
   
subject to {
  ctInit:  
    Inv[0] == Inventory;
  forall( t in Periods ) 
    ctCapacity:
      RegulBoat[t] <= Capacity;
  forall( t in Periods )
    ctBoat: 
      RegulBoat[t] + ExtraBoat[t] + Inv[t-1] == Inv[t] + Demand[t];
}

Data for the simple inventory model (`sailco.dat`)

NbPeriods = 4;
Demand = [ 40, 60, 75, 25 ];
RegularCost = 400;
ExtraCost = 450;
Capacity = 40;
Inventory = 10;
InventoryCost = 20;

The key idea underlying this model is to use two sets of variables for describing the production: variables regulBoat[t] represent the number of boats built at the regular price ($400 in the instance data) for period t, while extraBoat[t] represents the number of extra boats, i.e., boats built at the higher price. The model also contains inventory variables. Most of the constraints are typical for inventory problems.

In addition, the constraint

  forall( t in Periods ) 
    ctCapacity:
      RegulBoat[t] <= Capacity;

states that there is a capacity constraint on the regular boats. This constraint could be expressed directly as a bound but this is not of concern since it will disappear in the next model. Note also that all the variables will be given integral values for this application, although they are of type float. This is due to the problem structure, not to chance.

The constraint matrix of this problem is totally unimodular, which guarantees that the optimum has only integer values for integer data. See for instance Combinatorial Optimization: Algorithms and Complexity by C.H. Papadimitriou and K. Steiglitz for a discussion of total unimodularity (see the Bibliography).

A solution to sailco.mod

For the instance data given in Data for the simple inventory model (sailco.dat), OPL returns the optimal solution


Final Solution with objective 78450.0000:
  regulBoat = [40.0000 40.0000 40.0000 25.0000];
  extraBoat = [0.0000 10.0000 35.0000 0.0000];
  inv = [10.0000 10.0000 0.0000 0.0000 0.0000];

Note:

It is interesting to observe that the model does not preclude producing extra boats even if the production of regular boats does not reach its full capacity. This is not an issue in this model, since the extra boats are more expensive and thus are not produced in an optimal solution. It would become an issue, of course, if the cost of the extra boats is less than the regular price (because of, say, economies of scale). This case is discussed in Increasing piecewise-linear vs. linear.

A piecewise linear model for this application is given in A piecewise linear model for the simple inventory problem (sailcopw.mod).

A piecewise linear model for the simple inventory problem (sailcopw.mod)

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

float Demand[Periods] = ...;
float RegularCost = ...;
float ExtraCost = ...;
float Capacity = ...;
float Inventory = ...;
float InventoryCost = ...;

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


minimize
   sum(t in Periods)
       piecewise{ RegularCost -> Capacity ; ExtraCost } Boat[t] +
                  InventoryCost  * (sum(t in Periods) Inv[t]);
              
subject to  {
  ctInventory:
    Inv[0] == Inventory;
  forall(t in Periods)
    ctDemand:
      Boat[t] + Inv[t-1] == Inv[t] + Demand[t];
}

The data description is similar in this model. What differs from the previous model presented in A simple inventory model (sailco.mod) is the choice of variables, the objective function, and the constraints. There is only one type of production variable in this model and hence there is no distinction between regular boats and extra boats. In this model, boat[t] represents the total production of boats during period t. Even more interesting is how the objective function is described: it makes it explicit that the cost of building the boats is in fact a piecewise linear function of the production

       piecewise{ RegularCost -> Capacity ; ExtraCost } Boat[t] +

OPL/CPLEX applies a transformation to obtain a linear formulation of the piecewise linear expressions and obtains a model equivalent to A simple inventory model (sailco.mod). It thus gives the same optimal solution.