After you have declared the decision variables and added the constraints to the model, you are ready to search for a solution. In this lesson, you use the predefined goal IloGenerate to search for a solution instead of using a default goal. The predefined goal IloGenerate allows you to control a choice in the solution search: you choose which constrained variable Solver tries first.

The predefined goal IloGenerate takes an environment as the first parameter and an array of constrained variables as the second parameter. When Solver executes IloGenerate, this goal gives a value to each variable in that array. The third parameter IloChooseIntIndex determines the order in which variables are chosen. The default is IloChooseFirstUnboundInt, which will choose the first variable that is not yet bound. Here is a constructor:

IloGoal IloGenerate(IloEnv env, 
                    IloNumVarArray vars,
                    IloChooseIntIndex = IloChooseFirstUnboundInt);

The goal IloGenerate uses the following algorithm:

As long as there exist any unknown variables:

After this search move, Solver performs constraint propagation during search.

The most critical parameter of IloGenerate is, without doubt, the choice of variable because that choice affects performance so directly. If you start your search with the "wrong" variable, you will effectively lose a great deal of computation time. Of course, the "right" order for choosing the variables depends very much on the nature of the problem.

You can use the following parameters to choose the order in which variables are bound in the goal IloGenerate:

Given the variety of problems in the real world, there are no definitive rules for choosing the best strategy. However, propagation in Solver rests on eliminating branches in the search tree. The sooner Solver can remove or prune branches of the search tree, the more efficiently it works. The predefined goal IloGenerate controls which branches of that tree are examined and in which order.

A good strategy--as good as a strategy can be and still be general--is to choose first the variable with the smallest domain using the parameter IloChooseMinSizeInt. This choice usually develops a search tree where pruning a branch will eliminate a great many possibilities, known as the first-fail principle. First-fail is so named because it is a good idea to make the search fail as soon as possible, thereby eliminating a whole branch of the search tree without having spent too much time searching it; to that end, first-fail usually chooses the "most difficult" variable first.

You start the solution search by creating 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);

Next you create an instance of the predefined goal IloGenerate. The first parameter is the environment and the second parameter is the array of variables square. Since you do not know whether any particular strategy makes sense in this case, use IloChooseMinSizeInt as the third parameter.

Add the following code after the comment //Create the goal

    IloGoal goal = IloGenerate(env, square, IloChooseMinSizeInt);

You now use the member function IloSolver::solve. In this lesson, you use goal as a parameter of IloSolver::solve. As you have used the parameter IloChooseMinSizeInt, Solver would normally first choose the unbound variable with the smallest domain and select a value for this variable. However, all the variables have the same initial domain in this problem. Therefore, Solver chooses the first variable that is not yet bound and selects a value (by default the minimum value in the domain). Solver then propagates the changes resulting from this decision. Solver next chooses the unbound variable with the smallest domain and propagates the effects of this decision, and so on. If a decision leads to a situation where a constraint is not satisfied, it is undone and Solver backtracks to the last decision.

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

    if (solver.solve(goal))

The member function IloSolver::solve returns a Boolean value of type IloBool. If a solution is found, an IloTrue value is returned and the program displays the solution. The member functions and streams IloAlgorithm::out and IloSolver::getValue display the solution. The member function IloSolver::printInformation displays information about the solution search, including number of variables, number of constraints, elapsed time since creation of search, number of fails, and number of choice points. The number of choice points is linked to the number of explored alternatives in the search tree. The number of fails is the number of incorrect decisions at choice points. IloSolver::printInformation also provides information about the size of the goal stack, memory usage, and so on.

A matrix created by two "for" loops is again used to display the elements of the array square in the format of a square.

The following code is provided for you:

      {
      for (i = 0; i < n; i++){
        for (j = 0; j < n; j++)
          solver.out() << " " << solver.getValue(square[n*i+j]);
        solver.out() << endl;
      }
      solver.out() << endl;
    }
    else
      solver.out() << "No solution " << endl;
      solver.printInformation();

Compile and run the program. The program finds a solution for a magic square of size n = 5. You can use command line arguments to try to find magic squares of other sizes. You should get the following results for a magic square of size n = 5, though the information displayed by IloSolver::printInformation will vary depending on platform, machine, configuration, and so on.

 1 2 13 24 25
 3 23 17 6 16
 20 21 11 8 5
 22 4 14 18 7
 19 15 10 9 12

Number of fails               : 791
Number of choice points       : 799
Number of variables           : 25
Number of constraints         : 13
Reversible stack (bytes)      : 8064
Solver heap (bytes)           : 20124
Solver global heap (bytes)    : 4044
And stack (bytes)             : 4044
Or stack (bytes)              : 4044
Search Stack (bytes)          : 4044
Constraint queue (bytes)      : 11152
Total memory used (bytes)     : 55516
Elapsed time since creation   : 0.11