Exercise 4

IBM ILOG Solver User's Manual > More on Modeling > Using the Distribute Constraint: Car Sequencing > Suggested answers > Exercise 4

Exercise 4

INDEX

PREVIOUS NEXT

Use the IloDistribute constraint to solve for a magic sequence. A magic sequence is a sequence of n + 1 values (x0, x1, ..., xn) such that 0 appears in the sequence x0 times, 1 appears x1 times, ..., and n appears in the sequence xn times. The numbers in the magic sequence have a sum equal to n + 1.

For example, for n = 3, the following sequence is a solution: (1, 2, 1, 0). That is, 0 is present once, 1 is present twice, 2 is present once, and 3 is not present (present zero times, as it were).

Describe, model, and solve this problem. Write the code so that you can solve magic sequences of different sizes, but find a solution for a magic sequence of size n = 10. This is a problem with a high level of modeling difficulty.

Suggested Answer

Describe

The known information is the size of the magic sequence. The unknown information is the sequence of numbers. The first constraint is that the numbers in the magic sequence have a sum equal to n + 1. The second constraint is that the number 0 appears in the sequence x0 times, 1 appears x1 times, and so on.

Model

To represent the numbers in the sequence, you use an array of integer variables vars. You also create an array of coefficients coeffs. This array contains the numbers 0, 1, 2, 3, and so on.

To model the first constraint that the numbers in the magic sequence have a sum equal to n + 1, you use IloScalProd to constrain that the sum of each variable times its coefficient is equal to n + 1. For example, using the magic sequence given in the exercise for n = 3, which is (1, 2, 1, 0), this equation is:

(x0)(0) + (x1)(1) + (x2)(2) + (x3)(3) = n + 1, which is equivalent to

(1)(0) + (2)(1) + (1)(2) + (0)(3) = 4

To model the second constraint that the number 0 appears in the sequence x0 times, 1 appears x1 times, and so on, you use the IloDistribute constraint. As you remember, IloDistribute takes three arrays as parameters: an array of variables used to count, an array of values, and an array of variables. In this exercise, the array of values is coeffs and the array of variables is vars, the sequence of numbers. You need to use an array to count how many times each value in coeffs can be used as a value in the array of variables vars. In this problem, the array of variables vars is also used as the counting array. This contributes to the difficulty level of modeling this problem. For example, using the magic sequence given in the exercise for n = 3, which is (1, 2, 1, 0), the IloDistribute constraint would work as follows:

counting array vars: [1, 2, 1, 0]

array of values coeffs: [0, 1, 2, 3]

array of variables vars: [1, 2, 1, 0]

As you can see, the first element in the array of values coeffs, 0, appears in the array of variables vars 1 time. This is because the first element in the counting array, which is also vars, is 1.

Solve

You solve the problem in the same way as you solved the car sequencing example, using the predefined goal IloGenerate.

The complete program follows. You can also view it online in the file YourSolverHome/examples/src/carseq_basic_ex4.cpp.

# include <ilsolver/ilosolverint.h>
 
ILOSTLBEGIN
 
int main(int argc, char** argv){
  IloEnv env;
  try {
    IloModel model(env);
    IloInt n = (argc > 1) ? atoi(argv[1]) : 10;
    IloInt i;
    IloIntVarArray vars(env, n + 1, 0, n + 1);
    IloIntArray coeffs(env, n + 1);
    for (i = 0; i < n + 1; i++)
      coeffs[i] = i;
    model.add(IloDistribute(env, vars, coeffs, vars));
    // redundant constraint
    model.add(IloScalProd(vars,coeffs) == n + 1);
    IloSolver solver(model);
    if (solver.solve(IloGenerate(env, vars, IloChooseMinSizeInt))) {
      for (i = 0; i < n + 1; i++)
        solver.out() << solver.getValue(vars[i]) << " ";
      solver.out() << endl;
    } 
    else
      solver.out() << "No solution" << endl;
    solver.printInformation();
  }
  catch (IloException& ex) {
    cerr << "Error: " << ex << endl;
  }
  env.end();
  return 0;
}

Results

You should get the following results, though the information displayed by IloSolver::printInformation will vary depending on platform, machine, configuration, and so on.

7 2 1 0 0 0 0 1 0 0 0 
Number of fails               : 5
Number of choice points       : 6
Number of variables           : 23
Number of constraints         : 14
Reversible stack (bytes)      : 4044
Solver heap (bytes)           : 12084
Solver global heap (bytes)    : 8088
And stack (bytes)             : 4044
Or stack (bytes)              : 4044
Search Stack (bytes)          : 4044
Constraint queue (bytes)      : 11144
Total memory used (bytes)     : 47492
Running time since creation   : 0.01

PREVIOUS NEXT