Once you have written a description of your problem, you can use Concert Technology classes to model it. You are going to model the bin packing problem in a different way from the way that you have modeled problems in previous lessons. In this lesson, you use classes to represent some of the model. You would normally want to create most industrial applications in this way, using object orientation.

You are going to create a class Bin. Instances of the class Bin represent the different bins used. Each instance of the class Bin will be described by three properties: type, capacity, and an array representing the number of each type of component in the bin. Each instance of the class Bin also adds the constraints to the model that affect each bin: constraints on bin capacity, bin contents, and the mixing of types of components in bins.

Open the example file YourSolverHome/examples/src/tutorial/binpacking_partial.cpp in your development environment.

First, you create an environment and a model. This code is provided for you:

int main(){
  IloEnv env;
  try {
    IloModel model(env);
    IloInt i;

In this lesson, you first define the class Bin with data members, a constructor, and a method to display the solution. The data members are the decision variables of the problem: the type of bin, the capacity of the bin, and an array representing the number of each type of component in the bin. This code is provided for you:

class Bin {
public:
  IloIntVar       _type;
  IloIntVar       _capacity;
  IloIntVarArray  _contents;
  Bin (IloModel    mod,
       IloIntArray Capacity,
       IloInt      nTypes,
       IloInt      nComponents);
  void display(const IloSolver sol);
};

Add the following code after the comment //Declare the constructor

Bin::Bin (IloModel model,
          IloIntArray Capacity,
          IloInt nTypes,
          IloInt nComponents) {

The constructor for an instance of Bin takes four parameters. The first parameter is the model. The second parameter is an array Capacity that contains the capacities of the different types of bins. The third parameter is nTypes, the number of types of bins. The fourth parameter is nComponents, the number of types of components.

In the constructor, you also declare the decision variables for each instance of Bin.

Add the following code after the comment
//Declare the decision variables in the constructor

  IloEnv env = model.getEnv();
  _type = IloIntVar(env, 0, nTypes-1);
  _capacity = IloIntVar(env, 0, IloMax(Capacity));
  _contents = IloIntVarArray(env, nComponents, 0, 4);

The first variable _type is an IloIntVar with a lower bound of 0 and an upper bound of nTypes-1. The second variable _capacity is an IloIntVar with a lower bound of 0. The upper bound is the maximum value in the array Capacity. The array of variables _contents is an IloIntVarArray representing the number of components of each type in the bin. The size of the array is nComponents, the lower bound is 0, and the upper bound is 4.

The decision variables _type and _contents will contain the solution to the problem, once it is solved. Declaring a decision variable for _capacity may seem redundant to you, since the capacity of a bin can be easily determined from its type. However, the decision variable _capacity is used in creating constraints and finding a solution. Since constraints are placed on this variable, it needs to be a decision variable.

Next, you create the constraints that affect each bin: constraints on bin capacity, bin contents, and the mixing of types of components in bins. All of these constraints have to be true for each bin and are created in the constructor of the class. These constraints are called class constraints since they will be true for all the instances of Bin. Each constraint must also be added to the model using the member function IloModel::add.

Add the following code after the comment
//Create the capacity constraints in the constructor

  model.add(_capacity == Capacity(_type));
  model.add(_capacity >= IloSum(_contents));
  model.add(0. < IloSum(_contents));

The first constraint states that the variable _capacity must be equal to the value in the array Capacity corresponding to the type of bin, which is given by the variable _type. The second constraint states that the variable _capacity must be greater than or equal to the sum of the values in the array _contents, which is the sum of the number of components of each type in the bin. The third constraint states that bin must not be empty; 0 must be less than the sum of the values in the array _contents.

Next, you create the constraints that state what type of components can go in what type of bin. To do this, you use metaconstraints and the predefined constraint IloIfThen. The constructor for IloIfThen creates a condition constraint. The first parameter is the environment. The parameter left indicates the IF clause. The parameter right indicates the THEN clause. The fourth optional parameter is a name used for debug and trace purposes. Here is a constructor for IloIfThen:

     IloIfThen (const IloEnv env,
                const IloConstraint left,
                const IloConstraint right,
                const char* name = 0);

For example, to create the constraints relating specifically to red bins you use IloIfThen. This is a metaconstraint because the constraint IloIfThen is a constraint placed on other constraints--the constraints representing the IF and THEN clauses. The IF part of the condition is represented by a constraint that uses the logical operator == to evaluate if the variable _type is equal to red. The THEN clause then performs an action based on this evaluation. The THEN part of the constraint is a metaconstraint itself consisting of three constraints joined by the logical AND operator &&. The first constraint uses the logical operator == to set the number of components of type plastic equal to 0. The second constraint uses the logical operator == to set the number of components of type steel equal to 0. The third constraint uses the logical operator <= to set the number of components of type wood to less than or equal to 1. In other words, IF the type of bin is equal to red, THEN the bin is constrained to have no plastic components, no steel components, and no more than 1 wood component.

Add the following code after the comment
//Create the constraints on bin type red in the constructor

  model.add(IloIfThen(env, _type == red,
                      ((_contents[plastic] == 0)
                       && (_contents[steel] == 0)
                       && (_contents[wood] <= 1))));

You use the same technique to create the constraints on bins of type blue and green in the constructor. This code is provided for you:

  model.add(IloIfThen(env, _type == blue,
                      ((_contents[plastic] == 0) && (_contents[wood] == 0))));
  model.add(IloIfThen(env, _type == green,
                      ((_contents[glass] == 0)
                       && (_contents[steel] == 0)
                       && (_contents[wood] <= 2))));

You also use metaconstraints, logical operators, and the constraint IloIfThen to state the constraints relating to the mixing of different types of components in the bins. This code is provided for you:

  model.add(IloIfThen(env, _contents[wood] != 0, _contents[plastic] != 0));
  model.add(((_contents[glass] == 0)  || (_contents[copper]  == 0)));
  model.add(((_contents[copper] == 0) || (_contents[plastic] == 0)));
}

You create the function display to display the solution, including bin type, capacity, and the number of each type of component contained in the bin. This code is provided for you:

void Bin::display(const IloSolver solver) {
  _type.getEnv().out() << "Type :\t"
                       << Types[(IloInt)solver.getValue(_type)] << endl;
  _type.getEnv().out() << "Capacity:\t"
                       << solver.getValue(_capacity) << endl;
  IloInt nComponents = _contents.getSize();
  for (IloInt i = 0; i < nComponents; i++)
    if (solver.getValue(_contents[i]) > 0)
      _type.getEnv().out() << Components[i] << " :  \t"
                           << solver.getValue(_contents[i]) << endl;
  _type.getEnv().out() << endl;
}

After you have completed the declaration of the Bin class and its constructor and member function, the next step is to create an environment and a model in the main function. The variable i will be used in a "for" loop. Since you already know how to do this, it is provided for you in the exercise code:

int main(){
  IloEnv env;
  try {
    IloModel model(env);
    IloInt i;

You create and initialize nComponents, representing the number of types of components, and nTypes, representing the number of types of bins. This code is provided for you:

    const IloInt nComponents = 5;
    const IloInt nTypes = 3;

You create an array Demand, with nComponents members. This array contains the demand for each type of component. There is the following demand for each type of component: 2 glass components, 4 plastic components, 3 steel components, 6 wood components, and 4 copper components. This code is provided for you:

    IloIntArray Demand(env, nComponents, 2, 4, 3, 6, 4);

You create an array Capacity, with nTypes members. This array contains the capacity of each type of bin: red bins have a capacity of 3, blue bins have a capacity of 1, and green bins have a capacity of 4. This code is provided for you:

    IloIntArray Capacity(env, nTypes, 3, 1, 4);

You create two variables, totalDemand and maxBin. The variable totalDemand is equal to the sum of the demands for each type of component. In this example, totalDemand equals 19. This is the sum of the demand for each type of component (2 + 4 + 3 + 6 + 4). You then set maxBin equal to totalDemand. This means that, at the most, you would need one bin for each component. This code is provided for you:

    IloInt totalDemand = (IloInt)IloSum(Demand);
    const IloInt maxBin = (IloInt)totalDemand;

Next, you use range constraints to implement the following constraints:

You use the predefined constraints IloRange and IloRangeArray. The constructor for IloRange creates an empty range. The first parameter is the environment. The second and third parameters are the lower and upper bounds of the range. The fourth optional parameter is a name used for debug and trace purposes. Here is a constructor:

     IloRange(const IloEnv env,
              IloNum lb,
              IloNum ub,
              const char* name = 0);

The constructor for IloRangeArray creates an array of empty ranges. The first parameter is the environment. The second and third parameters are arrays. The number of elements in the range array will equal the number of elements in the arrays lbs or ubs (which must both contain the same number of elements). The lower bound of each element in the range array will be equal to the corresponding element in the array lbs. The upper bound of each element in the range array will be equal to the corresponding element in the array ubs. Here is a constructor:

IloRangeArray(const IloEnv env,
              const IloNumArray lbs,
              const IloNumArray ubs);

Add the following code after the comment //Create the range constraints

    IloRange totalCapacityCon(env, totalDemand, IloIntMax);
    model.add(totalCapacityCon);
    IloRangeArray componentsDemandCon(env, Demand, Demand);
    model.add(componentsDemandCon);

The constraint totalCapacityCon creates an empty range with a lower bound equal to totalDemand (or 19 in this example) and an upper bound of IloIntMax. This constraint states that the total capacity of all the bins must be at least equal to the total demand for components. The constraint componentsDemandCon creates an empty array of ranges. Each range in the array has the same lower and upper bound: the values of the array Demand. This constraint states that the amount of each type of component in all the bins must equal the demand for each type of component. For example, the demand for glass is 2 components. Therefore, for this constraint to be satisfied the contents of all the bins must sum to exactly 2 components of type glass, and likewise for the other types of components.