Sometimes you find yourself in the position that you have to write a new, custom, constraint in CP Optimizer. This is not a trivial thing to do, as CP Optimizer does not ship any examples of a custom constraint, and the documentation is very limited. I will post a complete example of a custom constraint to show you how to do this.

Note: Since constraints have to be implemented using CP Optimizer engine extentions, you have to implement them in C++. You cannot do this through the Java interface.

Information on the implementation can be found in the "IBM ILOG CPLEX Optimization Studio CP Optimizer Extensions User’s Manual". For Optimization studio 12.6.2, you can find it here:

This question is marked "community wiki".

asked 16 Jul '15, 19:11

Joris%20Kinable's gravatar image

Joris Kinable
3381213
accept rate: 16%

wikified 18 Jul '15, 15:45

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k413


Let's start of with 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)
link

answered 16 Jul '15, 19:14

Joris%20Kinable's gravatar image

Joris Kinable
3381213
accept rate: 16%

edited 16 Jul '15, 19:17

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×37
×3

Asked: 16 Jul '15, 19:11

Seen: 2,188 times

Last updated: 18 Jul '15, 15:45

OR-Exchange! Your site for questions, answers, and announcements about operations research.