14
$\begingroup$

How do you implement a custom, global 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 this can be done.

Note: Since constraints have to be implemented using CP Optimizer engine extensions, 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.

$\endgroup$
13
$\begingroup$

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)
$\endgroup$
1
  • $\begingroup$ This is extremely helpful to me. Thanks! $\endgroup$
    – fbahr
    Jun 15 '19 at 8:22
1
$\begingroup$

The answer provided by Joris Kinable is correct for CP Optimizer versions up to 12.7.1 Starting from 12.8.0 they made changes in the API (more info here).

What this basically means is that you should change IloCP to IloCPEngine (in .hpp and .cpp files), and you are more or less set to go!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.