Testing with a known solution

Using an instance of the problem with a known solution is a useful method for debugging.

Designing models explains how to design good models for various problems. However, if errors slip in when you implement the constraints of the problem, it can be very difficult to understand why the application finds wrong answers, even though the model is very good.

There is a simple way to address such cases: use an instance of the problem with a known solution to test the constraints. For testing a solution, you assign the values corresponding to a solution before adding the constraints to the model. Then no failure should happen within this function. If a failure occurs with the known solution, you know there is a problem among the constraints.

To see how to test with a known solution, consider a map-coloring problem in which there are four available colors (blue, white, red, green) and six contiguous countries (Belgium, Denmark, France, Germany, Luxembourg, Netherlands). One known solution is to color Belgium red; Denmark, France and the Netherlands blue; Germany green; and Luxembourg white.

This C++ sample tests a known solution of the map-coloring problem.

#include <ilcp/cp.h>
const char* Names[] = {"blue", "white", "red", "green"};
int main(){
  IloEnv env;
  try {
    IloModel model(env);
    IloIntVar Belgium(env, 0, 3), Denmark(env, 0, 3),
      France(env, 0, 3), Germany(env, 0, 3), 
      Netherlands(env, 0, 3), Luxembourg(env, 0, 3);
    // Test a known solution
   model.add(Belgium == 2);
   model.add(Denmark == 0);
   model.add(France == 0);
   model.add(Germany == 3);
   model.add(Netherlands == 0);
   model.add(Luxembourg == 1);
    // Constraints
    model.add(Belgium != France); 
    model.add(Denmark != Germany ); 
    model.add(France != Germany); 
    model.add(Belgium != Netherlands); 
    model.add(Germany != Netherlands); 
    model.add(France != Luxembourg);  
    model.add(Luxembourg != Germany);
    model.add(Luxembourg != Belgium);
    model.add(Belgium != Germany);
    IloCP cp(model);
    // Search for a solution
    if (cp.solve()) {    
      cp.out() << cp.getStatus() << " Solution" << std::endl;
      cp.out() << "Belgium:" << Names[(IloInt)cp.getValue(Belgium)] << std::endl;
      cp.out() << "Denmark:" << Names[(IloInt)cp.getValue(Denmark)] << std::endl;
      cp.out()  <<  "France:" << Names[(IloInt)cp.getValue(France)] << std::endl;
      cp.out() << "Germany:" << Names[(IloInt)cp.getValue(Germany)] << std::endl;
      cp.out() << "Netherlands:" << Names[(IloInt)cp.getValue(Netherlands)] << std::endl;
      cp.out() << "Luxembourg:" << Names[(IloInt)cp.getValue(Luxembourg)]  << std::endl;
                   }
  }
  catch (IloException& ex) { 
    env.error() << "Error: " << ex << std::endl;
  }
  env.end();
  return 0;
}

If the solution turns out not to be feasible for the constraints of the model, you can use the conflict refiner to identify which constraints are violated in the solution as described in Using the conflict refiner.