Testing your installation with a simple application

Before proceeding with the other tutorials in the Getting Started with CP Optimizer manual, you should test your environment by compiling and running a simple application. The log produced by the application provides useful information about the model and the solution search.

This first lesson is designed to help you understand the basic concepts in constraint programming. In future lessons, you will work through problems by describing, modeling and solving problems using Concert Technology and CP Optimizer classes. In this lesson, you are provided with the completed example code so that you can test your installation of CP Optimizer.

In Modeling and solving a simple problem with integer variables: map coloring, you will learn about the classes and member functions used in this program.

The following code using the C++ API models and solves the problem introduced in this lesson:

#include <ilcp/cp.h>

int main(int argc, const char * argv[]){
  IloEnv env;
  try {
    IloModel model(env);
    IloIntVar x(env, 5, 12, "x");
    IloIntVar y(env, 2, 17, "y");
    model.add(x + y == 17);
    model.add(x - y == 5);
    IloCP cp(model);
    cp.propagate();
    cp.out() << std::endl << "Propagate:" << std::endl;
    cp.out() << "x in " << cp.domain(x) << std::endl;
    cp.out() << "y in " << cp.domain(y) << std::endl << std::endl;
    if (cp.solve()){
      cp.out() << std::endl << "Solution:" << std::endl;
      cp.out() << "x = " << cp.getValue(x) << std::endl;
      cp.out() << "y = " << cp.getValue(y) << std::endl;
    }
  }
  catch (IloException& ex) {
    env.out() << "Error: " << ex << std::endl;
  }
  env.end();
  return 0;
}

Open the example file <Install_dir>/cpoptimizer/examples/src/cpp/intro.cpp in your development environment. To test your installation of CP Optimizer, build and run the program. When you run the program, you should get results similar to this output:

Propagate:
x in x[10..12]
y in y[5..7]

 ! ----------------------------------------------------------------------------
 ! Satisfiability problem - 2 variables, 2 constraints
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 3.2 (before), 3.2 (after)
 !  . Memory usage      : 268.9 kB (before), 268.9 kB (after)
 ! Using parallel search with 8 workers.
 ! ----------------------------------------------------------------------------
 !               Branches  Non-fixed    W       Branch decision
 *                      2  0.00s        1        10 != x
 ! ----------------------------------------------------------------------------
 ! Search completed, 1 solution found.
 ! Number of branches     : 2
 ! Number of fails        : 1
 ! Total memory usage     : 735.8 kB (694.5 kB CP Optimizer + 41.3 kB Concert)
 ! Time spent in solve    : 0.00s (0.00s engine + 0.00s extraction)
 ! Search speed (br. / s) : 200.0
 ! ----------------------------------------------------------------------------

Solution:
x = 11
y = 6

The solution found by the CP Optimizer engine is x = 11 and y = 6. In addition to the solution, information regarding the progress of the optimizer is displayed; this information is called the search log, or the log.

The first line of the log indicates the type of problem, along with the number of decision variables and constraints in the model. In this case, there is no objective included in the model, so the problem is reported to be a “Satisfiability problem”. When the model includes an objective, the problem type is reported as a “Minimization problem” or a “Maximization problem” depending on the type of objective. The next three lines of the log provide information regarding the initial constraint propagation. The “Initial process time” is the time in seconds spent at the root node of the search tree where the initial propagation occurs. This time encompasses the time used by the optimizer to load the model, called extraction, and the time spent in initial propagation. The value for “Log search space” provides an estimate on the size of the depth-first search tree; this value is the log (base 2) of the products of the domains sizes of all the decision variables of the problem. Typically, the estimate of the size of the search tree should be smaller after the initial propagation, as choices will have been eliminated. However, this value is always an overestimate of the log of the number of remaining leaf nodes of the tree because it does not take into account the action of propagation of constraints at each node. The memory used by the optimizer during the initial propagation is reported.

In order to interpret the remainder of the log file, you may want to think about the search as a binary tree. The root of the tree is the starting point in the search for a solution; each branch descending from the root represents an alternative choice or decision in the search. Each of these branches leads to a node where constraint propagation during search will occur. If the branch does not lead to a failure and a solution is not found at a node, the node is called a choice point. The optimizer can make an additional decision and create two new alternative branches from the current node, or it can jump in the tree and search from another node.

The lines in the next section of the progress log, are displayed periodically during the search and describe the state of the search. The display frequency of the progress log can be controlled with parameters of the optimizer. Since the problem in the lesson is a simple one, only one update is displayed.

The progress information given in a progress log update includes:

• Branches: the number of branches explored in the binary search tree;

• Non-fixed: the number of uninstantiated (not fixed) model variables;

• Branch decision: the decision made at the branch currently under consideration by the optimizer.

The final lines of the log provide information about the entire search, after the search has terminated. This information about the search includes:

• Solution status: the conditions under which the search terminated;

• Number of branches: the number of branches explored in the binary search tree;

• Number of fails: the number of branches that did not lead to a solution;

• Total memory usage: the memory used by Concert Technology and the CP Optimizer engine;

• Time spent in solve: the elapsed time from start to the end of the search displayed in hh:mm:ss.ff format;

• Search speed: average time spent per branch.

In subsequent lessons in this manual, the log output is not included in the sections which report the results. You can view the log information when you build and run the completed programs.