Fixed-charge problems

Describes the problem and presents the model and data files.

Fixed-charge problems are another classic application of integer programs (see Applications and Algorithms by W. Winston in the Bibliography). They resemble some of the production problems seen previously but differ in two respects: the production is an integer value (e.g., a factory must produce bikes or toys), and the factories need to rent (or acquire) some tools to produce some of the products. Consider the following problem. A company manufactures shirts, shorts, and pants. Each product requires a number of hours of labor and a certain amount of cloth, and the company has a limited capacity of both. In addition, all of these products can be manufactured only by renting an appropriate machine. The profit on the products (excluding the cost of renting the equipment) are also known. The company would like to maximize its profit.

A fixed-charge model (fixed.mod) shows a model for fixed charge problems, while Data for the fixed-charge model (fixed.dat) gives some instance data.

{string} Machines = ...;
{string} Products = ...;
{string} Resources = ...;

int Capacity[Resources] = ...;
int MaxProduction = max(r in Resources) Capacity[r];
int RentingCost[Machines] = ...;
tuple productType {
   int profit;
   {string} machines;
   int use[Resources];
}
productType Product[Products] = ...;

dvar boolean Rent[Machines];
dvar int Produce[Products] in 0..MaxProduction;

constraint ctMaxProd[Products][Machines];

maximize 
  sum( p in Products ) 
    Product[p].profit * Produce[p] -
  sum( m in Machines ) 
    RentingCost[m] * Rent[m];
      
subject to {
  forall( r in Resources )
    ctCapacity:
      sum( p in Products ) 
        Product[p].use[r] * Produce[p] <= Capacity[r];
    forall( p in Products , m in Product[p].machines )
      ctMaxProd[p][m]:
        Produce[p] <= MaxProduction * Rent[m];
}

Machines = { shirtM shortM pantM };
Products = { shirt shorts pants };
Resources = { labor cloth };
Capacity = [ 150 160 ];
RentingCost = [ 200 150 100 ];
Product = [
      <6 {shirtM} [ 3 4 ] >
      <4 {shortM} [ 2 3 ] >
      <7 {pantM} [ 6 4 ] >
          ];

The integer program for this model uses two sets of variables: production variables and rental variables. A production variable produce[p] describes the production of product p; a rental variable rent[m] is a 0-1 variable representing whether machine m is rented. Most of the constraints are similar to traditional production problems and pose few difficulties. The most delicate aspect of the modeling is expressing that a product can be produced only if its equipment is rented.

It is not possible to use the same idea as in the warehouse-location problem: e.g., a constraint

produce[p] <= rent[m] 

is not correct, since produce[p] is not a Boolean variable in this model. One might be tempted to write

produce[p] <= produce[p] * rent[m] 

but this constraint is not linear. The solution adopted in the model is to use an integer representing the maximal production of any product:

int MaxProduction = max(r in Resources) Capacity[r];

and write

produce[p] <= MaxProduction * rent[m]

If machine m is rented, then the constraint is redundant, since MaxProduction is chosen to be larger than produce[p]. Otherwise, the right-hand side is zero and product p cannot be manufactured. Note the data representation in this model: the type

tuple productType {
   int profit;
   {string} machines;
   int use[Resources];
}

clusters all data related to a product: its profit, the set of machines it requires, and the way it uses the resources. Note also the constraint

    forall( p in Products , m in Product[p].machines )
      ctMaxProd[p][m]:
        Produce[p] <= MaxProduction * Rent[m];

which features a forall statement that quantifies over each product and over each machine used by the product.