In this lesson, you will learn how to control the search using node evaluators and search selectors. Goals are the mechanism by which Solver implements search strategies. Goals are a bit like building blocks--goals can be created by combining other goals and a function that returns a goal can take other goals as parameters. You will perform five steps to create a final goal:

First, you create combinedGoal using logical AND operators. You are already familiar with the predefined goal IloGenerate. The goal IloGenerate takes an array of decision variables as a parameter and calls the function IloInstantiate on each variable in the array. The function IloInstantiate takes a decision variable and binds a value to it.

The first goal binds each decision variable in the array of variables cost using the principle of least regret, or minimizing regret. The IloGenerate parameter IloChooseMaxRegretMin is explained after the following step. The second goal binds each decision variable in the array of variables supplier in the default way, choosing the first unbound variable. The third goal uses the function IloInstantiate to bind the decision variable totalCost.

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

    IloGoal combinedGoal = IloGenerate(env, cost, IloChooseMaxRegretMin) &&
                           IloGenerate(env, supplier) &&
                           IloInstantiate(env, totalCost);

The following table shows the relative supply costs for the stores. The best decision for each individual store is the warehouse with the lowest relative cost. The second best decision is the warehouse with the second lowest relative cost. The lowest and second lowest costs are in bold.

To illustrate the principle of least regret, examine one small decision. The supplier warehouse located in Bonn has a capacity of one store. Which store should be supplied by the warehouse in Bonn? Two likely candidates are store 3, with a relative cost of 2, and store 6, with a relative cost of 1. If you just looked at this information, you would likely make the decision to use the Bonn warehouse to supply store 6, since the relative cost is lower. However, choosing the Bonn warehouse to supply store 6 will force store 3 to be supplied by the Bordeaux warehouse, with the next lowest relative cost for store 3. You can also imagine what would happen if you choose the Bonn warehouse to supply store 3 and forced store 6 to be supplied by the Bordeaux warehouse, with the next lowest relative cost for store 6. Take a closer look at the two scenarios.

You can see that Scenario B is a much better choice for the total cost, even though the original choice to supply store 3 from the Bonn warehouse rather than store 6 is a slightly more costly decision than its inverse. You can use the principle of least regret to make just this kind of decision. If you had examined the difference between the lowest relative cost and the next lowest relative cost for store 3, you would see that it is 53. The difference for store 6 is only 4. In deciding which store to supply from Bonn, choose the store with the largest difference. This decision will give you the lowest total cost and cause the least regret.

A search tree is composed of nodes connected by branches. The root of the tree is the starting point in the search for a solution; each branch descending from the root represents a decision in the search. At the beginning of the search, all the nodes in the tree are unexplored nodes. Solver starts the search at the root node. At this point, the root node is called an open node, since no decision has yet been made. There are two possible decisions to make at this open node--these two possible decisions are called leaves. Solver selects a leaf. The root node is now a closed node, since a decision has been made. The selected leaf is now a branch and the node at the other end of this branch is now the open node. Two leaves come off this open node, representing two possible decisions. Tree traversal is the technique used to explore the search tree. As Solver traverses a search tree, it builds an active path. Each node, except for the terminal ones, has one or more child nodes and is called the parent of its child nodes. Removing branches from the search tree is pruning. Node evaluators guide how Solver traverses the search tree--which nodes are evaluated and in what order. Search selectors determine how Solver makes decisions at open nodes--a search selector guides the selection of a leaf.

Depth-First Search is a straightforward approach to searching for a solution. However, sometimes you may have some knowledge about the search tree--you may know that certain parts of the search tree are more likely to contain a solution. In this case, you may want to change the order of node evaluation, since you think that certain nodes are more likely to lead to a solution. To do this, you can use a different node evaluator. There are several predefined functions in Solver that create and return node evaluators. To learn more about them, see Chapter 12. In this lesson, you will use the predefined function IloSBSEvaluator to create and return a node evaluator based on the principle of Slice-Based Search (SBS).

Usually, you have some kind of strategy to solve your problem. Therefore, you hope that Solver will not make many mistakes as it searches for a solution. In search trees, right moves are considered mistakes and left moves are considered correct decisions. So, if you think you have a good search strategy, it would make sense to look for a solution first among the nodes in paths that have fewer right moves. By searching first among the paths with fewer right moves you are saying you believe in your search strategy and you are trying to stick to it.

Slice-Based Search (SBS) does this. It looks first in the paths of the tree with fewer right moves. A right move in the path from the root of the search tree to the current node is known as a discrepancy. By looking first in paths with fewer right moves, Slice-Based Search cuts the search tree in slices.

The function IloSBSEvaluator creates and returns an instance of IloNodeEvaluator that implements Slice-Based Search. The first parameter is the environment. The second parameter is step. Solver will look first at paths that have a number of discrepancies, or right moves, less than or equal to step. The third parameter is maxDiscrepancy. If this parameter is used, Solver will discard nodes with a number of discrepancies greater than maxDiscrepancy. The default value for maxDiscrepancy is IloIntMax, which means that Solver will not discard any nodes based on this parameter. Here is a constructor for IloSBSEvaluator

IloNodeEvaluator IloSBSEvaluator(IloEnv env,
                                 IloInt step = 4,
                                 IloInt maxDiscrepancy = IloIntMax);

Now that you understand the concepts behind node evaluators, you can create one. The node evaluator SBSNodeEvaluator will first search paths in the search tree with 4 or less discrepancies.

Add the following code after the comment //Create the node evaluator

    IloNodeEvaluator SBSNodeEvaluator = IloSBSEvaluator(env, 4);

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

    IloGoal SBSNodeEvaluatorGoal = IloApply(env, combinedGoal,
                                            SBSNodeEvaluator);

Now that you have created and applied a node evaluator, you create a search selector. This search selector will guide the search at each open node. In this problem, you want to select the leaf at each open node that will minimize the total cost of the solution. To do this, you use the function IloMinimizeVar. This function returns an instance of the class IloSearchSelector. It takes three parameters: the environment, the variable to be minimized, and a step. Here is a constructor:

IloSearchSelector IloMinimizeVar(IloEnv env, 
                                 IloNumVar var, 
                                 IloNum step = 0);

The search selector IloMinimizeVar does several things:

Add the following code after the comment //Create the search selector

    IloSearchSelector minimizeSearchSelector = IloMinimizeVar(env,
                                                             totalCost,
                                                             0.1);

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

    IloGoal finalGoal = IloSelectSearch(env, SBSNodeEvaluatorGoal,
                                        minimizeSearchSelector);

Now, you create an instance of IloSolver to solve the problem expressed in the model. This code is provided for you:

    IloSolver solver(model);

You now use the member function IloSolver::solve to search for a solution. In this lesson, you use finalGoal as a parameter of IloSolver::solve.

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

    if (solver.solve(finalGoal))

The member functions and streams IloAlgorithm::out and IloSolver::getValue are used to display the solution. When you print the solution, you associate the value for the supplier warehouse variable supplier with the warehouse location using the array Suppliers[], which is provided for you in the exercise code. The following code is provided for you:

      {
      solver.out() << "------------------------------" << endl;
      solver.out() << "Solution:  " << endl;
      for (i = 0; i < nStores; i ++)
        solver.out() << "Store  " << i << " " << "Warehouse:  "
                     << Suppliers[(IloInt)solver.getValue(supplier[i])]
                     << " " << endl;
        solver.out() << endl;
        for (j = 0; j < nStores ; j ++)
          solver.out() << "Store  " << j << " " << "Cost:  "
                       << solver.getValue(cost[j]) << " " << endl;
          solver.out() << endl;
          solver.out() << "Total cost:  " << solver.getValue(totalCost)
                                          << endl;
          solver.out() << "------------------------------" << endl;

    } 
    else solver.out() << "No solution" << endl;
    solver.printInformation();

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

Using default file
Cost to build a warehouse:
30
Relative costs for stores:
[[20, 24, 11, 25, 30], [28, 27, 82, 83, 74], [74, 97, 71, 96, 70], [2, 55, 73, 
6
9, 61], [46, 96, 59, 83, 4], [42, 22, 29, 67, 59], [1, 5, 73, 59, 56], [10, 73,
13, 43, 96], [93, 35, 63, 85, 46], [47, 65, 55, 71, 95]]
Warehouse capacities:
[1, 4, 2, 1, 3]
------------------------------
Solution:
Store  0 Warehouse:  Rome
Store  1 Warehouse:  Bordeaux
Store  2 Warehouse:  Rome
Store  3 Warehouse:  Bonn
Store  4 Warehouse:  Rome
Store  5 Warehouse:  Bordeaux
Store  6 Warehouse:  Bordeaux
Store  7 Warehouse:  London
Store  8 Warehouse:  Bordeaux
Store  9 Warehouse:  London

Store  0 Cost:  30
Store  1 Cost:  27
Store  2 Cost:  70
Store  3 Cost:  2
Store  4 Cost:  4
Store  5 Cost:  22
Store  6 Cost:  5
Store  7 Cost:  13
Store  8 Cost:  35
Store  9 Cost:  55

Total cost:  383
------------------------------
Number of fails               : 25
Number of choice points       : 27
Number of variables           : 76
Number of constraints         : 76
Reversible stack (bytes)      : 12084
Solver heap (bytes)           : 52284
Solver global heap (bytes)    : 20124
And stack (bytes)             : 4044
Or stack (bytes)              : 4044
Search Stack (bytes)          : 4044
Constraint queue (bytes)      : 11160
Total memory used (bytes)     : 107784
Elapsed time since creation   : 0.02

As you can see, the solution uses four warehouse sites: Bonn, Bordeaux, London, and Rome. All stores are supplied by a supplier warehouse and the total cost is 383.