Solve ILP with Branch and Bound and CPLEX C++

Question

I want to solve an ILP using a branch and bound algorithm for a graph labelling problem. My ILP has an objective function and constraints for every possible pair of nodes from the graph. So I have n^2 / 2 possible constraints, and the constraints have following shape:

for two vertices i, j \in V(G) add the constraints: |X_i - X_j| >= k + 1 - d(i,j)

its obvious that this isn't linear. So i want to implement my algorithm that uses binary branch and bound:

• start with empty LP only with the objective function
• start with empty branch tree with start node
• then at every node in the branch tree, create two child nodes.
  • in the first child node
    • add the constraints X_i - X_j >= k + 1 - d(i,j)
    • and constraint X_i >= X_j
  • for the second child node
    • add the constraint -(X_i - X_j) >= k + 1 - d(i,j)
    • and the constraint X_j >= X_i
• repeat this step and possibly bound, until we find best solution

If I do this branch and bound algorithm, and search for the best solution, I would get the best occupancy of which variable should be greater than which. Then I would get a LP, with constant constraints and I would get the optimal integer solution.

My question now is, what is the best way of doing that in c++ and cplex? Should I always create a new IloModel in CPLEX? Or can I do it all in the same IloEnv? I know that there are built in options, to specify the branch and bound in CPLEX, but I would like to do it "manually", so I can also implement functions that selects the "best" next constraint to add.

Thank you very much in advance!

Answer 1

Within CPLEX you also have Constraint Programmming and with OPL for example you can directly write

forall( ordered c1, c2 in Cells: distance[c1,c2] > 0) {
      forall(t1 in 1..nbTrans[c1]) {
         forall(t2 in 1..nbTrans[c2] ) 
           abs(freq[<c1,t1>] - freq[<c2,t2>]) >= distance[c1,c2];
      }
   }

which is part of a frequency allocation model

The same can be done in C++