The Graph Coloring example shipped with CP optimizer (file: color.cpp in the examples directory):
#include <ilcp/cp.h>
const char* Names[] = {"blue", "white", "yellow", "green"};
int main(int , const char * []){
IloEnv env;
try {
IloModel model(env);
IloIntVar Belgium(env, 0, 3, "B"), Denmark(env, 0, 3, "DK"),
France(env, 0, 3, "F"), Germany(env, 0, 3, "D"),
Luxembourg(env, 0, 3, "L"), Netherlands(env, 0, 3, "NE");
model.add(Belgium != France);
model.add(Belgium != Germany);
model.add(Belgium != Netherlands);
model.add(Belgium != Luxembourg);
model.add(Denmark != Germany );
model.add(France != Germany);
model.add(France != Luxembourg);
model.add(Germany != Luxembourg);
model.add(Germany != Netherlands);
IloCP cp(model);
if (cp.solve())
{
cp.out() << std::endl << cp.getStatus() << " Solution" << std::endl;
cp.out() << "Belgium: " << Names[cp.getValue(Belgium)] << std::endl;
cp.out() << "Denmark: " << Names[cp.getValue(Denmark)] << std::endl;
cp.out() << "France: " << Names[cp.getValue(France)] << std::endl;
cp.out() << "Germany: " << Names[cp.getValue(Germany)] << std::endl;
cp.out() << "Luxembourg: " << Names[cp.getValue(Luxembourg)] << std::endl;
cp.out() << "Netherlands: " << Names[cp.getValue(Netherlands)] << std::endl;
}
}
catch (IloException& ex) {
env.out() << "Error: " << ex << std::endl;
}
env.end();
return 0;
}
In the above model, we add constraints stating that 2 IloIntVars have to be different in value, e.g. Belgium != France. Let's write a custom constraint "IloDiffConstraint" which replicates this behavior. A discription of this constraint and its implementation is provided in the "IBM ILOG CPLEX Optimization Studio CP Optimizer Extensions User’s Manual". The manual only provides code snippets. Here I'll post the complete implementation.
diffconstraint_handler.hpp:
#ifndef DIFFCONSTRAINT_HANDLER_HPP
#define DIFFCONSTRAINT_HANDLER_HPP
#define IL_STD
#include <cstdlib>
#include<iostream>
#include <ilcp/cpext.h>
IloConstraint IloDiffConstraint(
IloEnv env,
IloIntVar x,
IloIntVar y,
const char* name
);
class IlcDiffConstraintHandler : public IlcConstraintI {
public:
/** Constructors */
IlcDiffConstraintHandler(IloCP cp,
IlcIntVar _x_var, IlcIntVar _y_var);
/** Empty destructor */
~IlcDiffConstraintHandler(){ };
/** ILOG search control */
virtual void propagate(); /**< Propagation method */
virtual void post(); /**< Daemon setting */
virtual IlcBool isViolated() const; /**< Violation checking */
private:
IlcIntVar x_var;
IlcIntVar y_var;
};
inline IlcConstraint IlcDiffConstraint(
IloCP cp,
IlcIntVar x_var,
IlcIntVar y_var)
{
return new(cp.getHeap()) IlcDiffConstraintHandler(cp, x_var, y_var);
}
inline IlcBool IlcDiffConstraintHandler::isViolated() const {
return IlcFalse; //This is handled in the propagator itself
}
#endif /* DIFFCONSTRAINT_HANDLER_HPP */
And here is the implementation class diffconstraint_handler.cpp:
#include "diffconstraint_handler.hpp"
/**
* Wrapper for ILO object
*/
ILOCPCONSTRAINTWRAPPER2(IloDiffConstraint,
cp,
IloIntVar, _x,
IloIntVar, _y){
use(cp,_x);
use(cp,_y);
return IlcDiffConstraint(cp, cp.getIntVar(_x), cp.getIntVar(_y));
}
IlcDiffConstraintHandler::IlcDiffConstraintHandler(IloCP cp, IlcIntVar _x_var, IlcIntVar _y_var):
IlcConstraintI(cp), x_var(_x_var), y_var(_y_var){
}
void IlcDiffConstraintHandler::propagate(){
if (x_var.isFixed()) y_var.removeValue(x_var.getValue());
if (y_var.isFixed()) x_var.removeValue(y_var.getValue());
}
void IlcDiffConstraintHandler::post(){
x_var.whenValue(this);
y_var.whenValue(this);
}
Finally we can now write a new main file (main.cpp) which utilizes the new constraint:
#define IL_STD
#include <cstdlib>
#include <ilcp/cp.h>
#include "diffconstraint_handler.hpp"
const char* Names[] = {"blue", "white", "yellow", "green"};
int main(int argc, char** argv) {
IloEnv env;
try {
IloModel model(env);
IloIntVar Belgium(env, 0, 3, "B"), Denmark(env, 0, 3, "DK"),
France(env, 0, 3, "F"), Germany(env, 0, 3, "D"),
Luxembourg(env, 0, 3, "L"), Netherlands(env, 0, 3, "NE");
model.add(IloDiffConstraint(env, Belgium, France, "test"));
model.add(IloDiffConstraint(env, Belgium, Germany, "test"));
model.add(IloDiffConstraint(env, Belgium, Netherlands, "test"));
model.add(IloDiffConstraint(env, Belgium, Luxembourg, "test"));
model.add(IloDiffConstraint(env, Denmark, Germany, "test"));
model.add(IloDiffConstraint(env, France, Germany, "test"));
model.add(IloDiffConstraint(env, France, Luxembourg, "test"));
model.add(IloDiffConstraint(env, Germany, Luxembourg, "test"));
model.add(IloDiffConstraint(env, Germany, Netherlands, "test"));
IloCP cp(model);
if (cp.solve())
{
cp.out() << std::endl << cp.getStatus() << " Solution" << std::endl;
cp.out() << "Belgium: " << Names[cp.getValue(Belgium)] << std::endl;
cp.out() << "Denmark: " << Names[cp.getValue(Denmark)] << std::endl;
cp.out() << "France: " << Names[cp.getValue(France)] << std::endl;
cp.out() << "Germany: " << Names[cp.getValue(Germany)] << std::endl;
cp.out() << "Luxembourg: " << Names[cp.getValue(Luxembourg)] << std::endl;
cp.out() << "Netherlands: " << Names[cp.getValue(Netherlands)] << std::endl;
}
}
catch (IloException& ex) {
env.out() << "Error: " << ex << std::endl;
}
env.end();
return 0;
}
Note: when running this example on linux, you need to specify "define IL_STD". If you want to compile this example on windows/mac, a makefile is included in the cpoptimizer example directory which should help you determine which definition you should use.
The makefile I'm using on my linux machine to compile this example:
# --- SYSTEM ---
SYSTEM = x86-64_linux
LIBFORMAT = static_pic
# --- DIRECTORIES ---
CCC = g++
BASISILOG = /opt/ILOG/CPLEX_Studio1262
CPOPTDIR = $(BASISILOG)/cpoptimizer
CONCERTDIR = $(BASISILOG)/concert
CPLEXDIR = $(BASISILOG)/cplex
# --- FLAGS ---
CCOPT = -m64 -fPIC -fexceptions -DIL_STD
CPLEXLIBDIR = $(CPLEXDIR)/lib/$(SYSTEM)/$(LIBFORMAT)
CONCERTLIBDIR = $(CONCERTDIR)/lib/$(SYSTEM)/$(LIBFORMAT)
CPOPTLIBDIR = $(CPOPTDIR)/lib/$(SYSTEM)/$(LIBFORMAT)
CONCERTINCDIR = $(CONCERTDIR)/include
CPLEXINCDIR = $(CPLEXDIR)/include
CPOPTINCDIR = $(CPOPTDIR)/include
# --- OPTIMIZATION FLAGS ---
DEBUG_OPT = -DNDEBUG -O3# No debug, optimized for performance.
#DEBUG_OPT = -g3 -O0 #Produces additional debug information. Add -pg to enable profiling with gprof
CFLAGS = -ansi -DIL_STD -fPIC -fstrict-aliasing -pedantic -Wall -std=gnu++0x -fexceptions -ffloat-store \
-DILOUSEMT -D_REENTRANT -DILM_REENTRANT -I./include $(DEBUG_OPT)
CFLAGS += $(CCOPT) -I$(CPLEXINCDIR) -I$(CONCERTINCDIR) -I$(CPOPTINCDIR)
LDFLAGS = -L$(CPOPTLIBDIR) -lcp -L$(CPLEXLIBDIR) -lilocplex -lcplex -L$(CONCERTLIBDIR) -lconcert -lm -pthread
# ---- COMPILE ----
SRC_DIR := src
OBJ_DIR := obj
SRC_DIRS := $(shell find $(SRC_DIR) -type d)
OBJ_DIRS := $(addprefix $(OBJ_DIR)/,$(SRC_DIRS))
SOURCES := $(shell find $(SRC_DIR) -name '*.cpp')
OBJ_FILES := $(addprefix $(OBJ_DIR)/, $(SOURCES:.cpp=.o))
vpath %.cpp $(SRC_DIRS)
# ---- TARGETS ----
EXECUTABLE=diffConstrExample
all: $(EXECUTABLE)
$(EXECUTABLE): makedir $(SOURCES) $(OBJ_FILES)
$(CCC) $(CFLAGS) $(OBJ_FILES) $(LDFLAGS) -o $@
$(OBJ_DIR)/%.o: %.cpp
$(CCC) $(CFLAGS) $< -o $@ -c
makedir: $(OBJ_DIRS)
$(OBJ_DIRS):
@mkdir -p $@
clean:
@rm -rf obj
@rm -rf $(EXECUTABLE)
