Linear programming: a product mix problem

Describes the problem and presents the model and data files.

As a first example, let’s consider a simple mathematical programming (MP) problem to determine an optimal production mix.

To meet the demands of its customers, a company manufactures its products in its own factories (inside production) or buys them from other companies (outside production). Inside production is subject to some resource constraints: each product consumes a certain amount of each resource. In contrast, outside production is theoretically unlimited. The problem is to determine how much of each product should be produced inside the company and how much outside, while minimizing the overall production cost, meeting the demand, and not exceeding the resource constraints.

The statement of the problem must specify the set of products and the set of resources. For each product, we need to know the inside and outside production costs, and for each resource we need to know the available capacity of that resource. Finally, we need to know the consumption of resources by the different products.

This is a general outline of an optimization problem. The production example illustrates a specific pasta manufacturing problem. The project contains a model, product.mod, shown in the example below, which states the problem to be solved. The data to be used by the model is also shown below, in the fileproduct.dat.

{string} Products = ...;
{string} Resources = ...;
tuple productData {
   float demand;
   float insideCost;
   float outsideCost;
   float consumption[Resources];
}
productData Product[Products] = ...;
float Capacity[Resources] = ...;

dvar float+ Inside[Products];
dvar float+ Outside[Products];

execute CPX_PARAM {
  cplex.preind = 0;   
  cplex.simdisplay = 2;   
}


minimize
  sum( p in Products ) 
    (Product[p].insideCost * Inside[p] + 
    Product[p].outsideCost * Outside[p] );
subject to {
  forall( r in Resources )
    ctInside: 
      sum( p in Products ) 
        Product[p].consumption[r] * Inside[p] <= Capacity[r];
  forall( p in Products )
    ctDemand: 
      Inside[p] + Outside[p] >= Product[p].demand;
}

Products =  { "kluski", "capellini", "fettuccine" };
Resources = { "flour", "eggs" };
Product = #[
      kluski : < 100, 0.6, 0.8, [ 0.5, 0.2 ] >,
      capellini : < 200, 0.8, 0.9, [ 0.4, 0.4 ] >,
      fettuccine : < 300, 0.3, 0.4, [ 0.3, 0.6 ] >
          ]#;
Capacity = [ 20, 40 ];

In the model, the instruction

tuple productData {
   float demand;
   float insideCost;
   float outsideCost;
   float consumption[Resources];
}

declares a tuple type with four fields. The first three fields, of type float, are used to represent the demand and costs of a product; the last field is an array representing the resource consumptions of the product. These fields are intended to hold all the data related to a given product.

The instruction

ProductData product[Products] = ...; 

declares an array of these tuples, one for each product.

The model also contains two arrays of decision variables to represent the inside and outside production, respectively. There is an objective function to minimize the total production cost, and there are two types of constraints: a set of constraints to avoid exceeding the capacity limitation, and another set of constraints to satisfy the demand requirements.

Initialization of the data given in product.dat for one instance of this problem specifies these various data items: to initialize the tuples, values are given for each of their fields.

Product = #[
      kluski : < 100, 0.6, 0.8, [ 0.5, 0.2 ] >,
      capellini : < 200, 0.8, 0.9, [ 0.4, 0.4 ] >,
      fettuccine : < 300, 0.3, 0.4, [ 0.3, 0.6 ] >
           ]#;

In the data file we use a set of strings called Products to represent the varieties of pasta and another set of strings called Resources to represent the raw ingredients of flour and eggs.