CODEWITHSUNDEEP
c++optimizationlinear-programmingcplexinteger-programming
Namal
Namal

Reputation: 293

How to generate cuts and find an integer solution

I have an integer programming problem that looks for example like this, but with much more variables and constraints

enter image description here

It is equal to the 3SAT problem. There is no object function, so any integer solution will be optimal.

Now I can find a non integer solution with cplex and I want to manually add cutting planes. My problem is now that I don't know exactly how to generate cuts after the first relaxation. I found many papers about clique cuts and alike but all of them are theoretical and don't show an algorithm how to do it. I hope someone can give me a hint how to generate those cuts and to solve this.

Upvotes: 1

Views: 575

Answers (1)

Jacko
Jacko

Reputation: 88

Well I see two main choices. Either using User Cuts or Lazy Constraints.

In both cases you can recreate the LHS of the cuts with IloExpr where the variables on the cut could be added using the += operator, the cuts being added to your IloModel a priori or a posteriori, in other words, you could decide adding your User Cuts before the .solve() instruction or right after it if you detect any violated cut. A generic row construction allow you to add one or even multiple cuts at once using one of the following two options:

cplex.addCut(IloConstraint cut)
cplex.addCuts(IloConstraintArray cuts)

Supposing the variables to be added on the cut are stored in an IloIntArray VarInCut(env); and that you are using IloNumVarArray x(env); or IloIntVarArray x(env); variables in your model, you can construct the IloConstraint cut as any customary constraint in cplex-C++ per row construction:

IloIntArray VarInCut(env);
IloExpr LHS;
for (int i=0; i<VarInCut.getSize(); i++) { LHS += x[VarInCut[i]]; }

Hence, passing cut as LHS <= RHS or LHS == RHS in case of inequality/equality cut expression where RHS can either refer to another IloExpr or Numeric/Integer value.

The Lazy Constraints, on the other side, are usually implemented as CallBacks which are more tricky and can result into higher risk of incorrect behavior in your application, hence more difficult to debug. Take a look at CPLEX documentation on UserCuts, LazyConstraints and a couple of blogs, here and here.

One is glad to be of service!

Upvotes: 0

Related Questions