You are going to solve this problem in a different way than you solved other problems. In previous lessons, you created a model, declaring variables and adding constraints, and then solved the problem.The two stages of modeling and solving were clearly separated. In this problem, you solve in an incremental fashion. First you create one bin and fill it, making sure that all class constraints are satisfied. If all of the demand for each type of component has been met, then you have a solution. If not, Solver creates a second bin and fills it, making sure all class constraints are satisfied. When the problem is solved, you can be sure that the minimum number of bins has been used because of this incremental process. The objective, which is to minimize the number of bins used, is treated implicitly by the incremental solving method. It is never formally added to the model.

This example will show you how to add constraints to the model during the solving phase. In this problem, some of the constraints--the range constraints and the constraints to reduce symmetry--are defined with respect to the total number of bins used. For example, the constraint that the total capacity must exceed the demand depends on the number of bins. As a consequence, these constraints have to be redefined at each step since the total number of bins used so far changes at each step. This redefinition is carried out inside a "do-while" loop. Inside that loop, Solver detects whether a solution has been found yet. If there is no solution, Solver increments the number of bins used by one.

The following chart shows the process you will use to solve this problem:

solution = false
DO
     create a new bin
     add the bin to the range constraints
     IF there are at least 2 bins
          add the symmetry reduction constraints
     IF no solution is found
          the new bin becomes the previous bin
          increment the number of bins
     ELSE 
          solution = true
WHILE solution = false and the number of bins 
      is less than maxBin, continue DO
IF solution = true
      display the solution

First, you create pointers to the instances of the Bin class. The pointer newBin points to the instance of the class Bin just created inside the "do-while" loop. The pointer prevBin points to the instance of the class Bin created in the previous "do-while" loop and is initialized at 0. The pointer theBins points to an array of all the instances of class Bin created so far. The maximum number of possible instances of Bin is maxBin, or 19 in this example.

Add the following code after the comment //Create the pointers to the bins

    Bin* prevBin  =0;
    Bin* newBin;
    Bin** theBins = new Bin*[maxBin];
    IloInt nBins = 1;

A Boolean variable solution is created and initialized as false, which means that when you start there is no solution. This code is provided for you:

    IloBool solution = IloFalse;

Now you create an instance of the class IloSolver to solve the problem expressed in the model.

Add the following code after the comment //Create an instance of IloSolver

    IloSolver solver(model);

You now create the "do-while" loop in the solving phase. The first step in the loop is to create a new instance of the class Bin. Solver creates a new instance of class Bin and adds it to the array of bins theBins.

Add the following code after the comment //Create an instance of Bin

    do{
      newBin = new Bin(model, Capacity, nTypes, nComponents);
      theBins[nBins-1] = newBin;

Add the following code after the comment //Add the bin to the range constraints

      totalCapacityCon.setCoef(newBin->_capacity, 1.);
      for (i = 0; i < nComponents; i++)
        componentsDemandCon[i].setCoef(newBin->_contents[i], 1.);

The capacity of the bin is added to the range totalCapacityCon. The capacity of the first bin will not equal totalDemand, 19 in this example, so the constraint is not satisfied. In the next "do-while" loop, the capacity of the second bin is added to the capacity of the first bin, and the sum is tested to see if it is equal to totalDemand. When the sum of the capacities of all the bins equals totalDemand, the constraint totalCapacityCon is satisfied.

A "for" loop is used to populate the range array componentsDemandCon. The contents of the first bin are added to the range array by component type. For example, if the first bin contained 2 components of type glass, the range array componentsDemandCon would be [2,0,0,0,0]. In order for this constraint to be satisfied, the range array componentsDemandCon needs to equal the array Demand [2,4,3,6,4]. So in this case, the constraint would not be satisfied. In the next "do-while" loop, the contents of the second bin is added to contents of the first bin, and the sums of each type of component is tested to see if they are equal to the elements of the array Demand. When the sums are equal to the elements of the array Demand, the constraint componentsDemandCon is satisfied.

After adding the range constraints to the "do-while" solving loop, you now add constraints to reduce symmetry if there are at least 2 bins. One way to reduce symmetry is to group variables by type. Another way to reduce symmetry is to introduce order among variables, which is what you will do in this lesson.

You add constraints that state that the bins must be added in increasing order by type. This constraint removes only symmetric solutions; it does not eliminate any "real" solutions.

For example, if your solution in this problem requires 3 bins, one of each color, all of the following solutions are correct:

These are six different solutions. However, in a physical sense, all of these solutions are identical; they all consist of 1 red bin, 1 blue bin, and 1 green bin.

You introduce order by creating two more constraints, which are added to the model during the solving phase. The first constraint states that the type of each new bin should be greater than or equal to the type of the previous bin. This constraint orders the variables, first selecting bins of type red, then bins of type blue, and then bins of type green. After adding the constraint to reduce symmetry based on type of bin, you also need a second constraint that deals with the fact that there may be more than one bin of any given type in your solution. For example, if your solution includes one bin of type red with 1 component of type glass, 1 bin of type blue with 1 component of type glass, and 1 bin of type blue with 1 component of type steel, both of the following results are correct:

Then you use IloScalProd to assign a different coefficient to each type of component. For example, components of type glass have a coefficient of 625. Components of type steel have a coefficient of 25. You add a constraint that states that, if the new bin and the previous bin are both the same type of bin, then the IloScalProd of the new bin must be greater than or equal to the IloScalProd of the previous bin. In the example just described, the two blue bins are the same type. However, they do not have the same IloScalProd. The blue bin with 1 component of type glass has a scalar product of 1 * 625 = 625. The blue bin with 1 component of type steel has a scalar product of 1 * 25 = 25. Therefore, after removing symmetric solutions, only this solution will be found:

Add the following code after the comments //Add the constraints to reduce symmetry

      if (prevBin != 0){
        model.add(newBin->_type >= prevBin->_type);
        model.add(IloIfThen(env, prevBin->_type == newBin->_type,
                            IloScalProd(newBin->_contents, coef)
                            >= IloScalProd(prevBin->_contents, coef)  ));
      }

You now search for a solution with the member function IloSolver::solve. The search is placed in an "if-else" statement. If the search does not find a solution, the current bin becomes the previous bin and the number of bins increments by 1. While there is no solution and while the number of bins is less than or equal to maxBin, which is 19 in this example, the program returns to the "do" portion of the loop. This loop creates a new bin, adds the new bin to the range and symmetry constraints, and searches for a solution. If search finds a solution, the variable solution becomes true. The "do-while" loop is broken and Solver displays the solution.

Add the following code after the comment //Search for a solution

      solver.out() << "Search with " << nBins << endl;
      if (!solver.solve()){
        prevBin = newBin;
        nBins++;
      }
      else
        solution = IloTrue;
    }
    while (!solution && nBins <= maxBin);

You use the display function to display the solution: each bin is listed with its type, capacity, and contents. This code is provided for you:

    if (solution) {
      for(i = 0; i < nBins; i++){
        theBins[i]->display(solver);
      }
    }

Finally, you clean up the memory. This code is provided for you:

    for  (i = 0; i < nBins; ++i)
      delete theBins[i];
    delete [] theBins;

Compile and run the program. You should get the following results:

Search with 1
Search with 2
Search with 3
Search with 4
Search with 5
Search with 6
Search with 7
Search with 8
Type :  Red
Capacity:       3
Glass :         2

Type :  Blue
Capacity:       1
Steel :         1

Type :  Blue
Capacity:       1
Steel :         1

Type :  Blue
Capacity:       1
Steel :         1

Type :  Green
Capacity:       4
Copper :        4

Type :  Green
Capacity:       4
Plastic :       1
Wood :          2

Type :  Green
Capacity:       4
Plastic :       1
Wood :          2

Type :  Green
Capacity:       4
Plastic :       2
Wood :          2