4
$\begingroup$

I have an MILP problem and use CPLEX (Python interface). I am working on user heuristics for branching in the branch-and-bound procedure. With HSCallback I managed to get the information about the current subproblem (all integer variables are binary), in particular, what the variables that have been previously fixed/branched on are and how they've been fixed.

Now, I would like to do something with the current subproblem. Is there a way to obtain it as a model? Do I have to construct it each time in the callback from the original model by adding the constraints corresponding to the fixed variables? Or is there a more efficient way of doing it?

Below is a working example for a problem encoding Boolean satisfiability of CNF with 5 variables that has exactly one assignment (corresponding to the commented out line, uncommenting it makes the problem infeasible). I disable all possible heauristics and cuts to make sure that branch and bound has to do some work. Here I construct the subproblem by creating a copy of the original model and adding the constraints corresponding to the current branch.

import datetime
import docplex.mp.model as cpx
import cplex.callbacks as CPX_CB
from docplex.mp.relax_linear import LinearRelaxer


class MyHSCallback(CPX_CB.HSCallback):
    def __call__(self, *args, **kwargs):
        print()
        print(datetime.datetime.now(), "MyHSCallback working.............")
        print("node ID", self.get_node_ID())

        fixed = [(ind, int(self.get_lower_bounds(ind)))
                 for ind in range(self.var_count) if self.get_lower_bounds(ind) == self.get_upper_bounds(ind)]
        print("Fixed variables", ", ".join([str(ind) + ":" + str(value) for ind, value in fixed]))
        print("Feasible subproblem", self.solve())

        # creating a copy of the subproblem
        model_copy = self.original_model.copy()
        for ind, value in fixed:
            model_copy.add_constraint(model_copy.get_var_by_index(ind) == value)

        # doing something with the current subproblem
        lp_model = LinearRelaxer().linear_relaxation(mdl=model_copy)
        sol = lp_model.solve()
        if sol is not None:
            print("Relaxation Values", sol.get_values([lp_model.get_var_by_index(ind) for ind in range(self.var_count)]))


model = cpx.Model(name="cnf")
vars = model.binary_var_list(5, name="var")
x = vars[0]
y = vars[1]
z = vars[2]
w = vars[3]
v = vars[4]

model.add_constraint(w + x + y >= 1)
model.add_constraint(v + w - y >= 0)
model.add_constraint(w - x + y + z >= 0)
model.add_constraint(v - x + y - z >= -1)
model.add_constraint(v - w + y + z >= 0)
model.add_constraint(v - w + x - z >= -1)
model.add_constraint(v - w + x - y + z >= -1)
model.add_constraint(- w - x - y >= -2)
model.add_constraint(-v + w - y + z >= -1)
# model.add_constraint(-v + w + x - y - z >= -2)
model.add_constraint(-v + w - x - z >= -2)
model.add_constraint(-v - w + x >= -1)
model.add_constraint(-v - w - x + y >= -2)

hs_cb = model.register_callback(MyHSCallback)
hs_cb.var_count = len(vars)
hs_cb.original_model = model

model.parameters.preprocessing.symmetry = 0
model.parameters.preprocessing.presolve = 0
model.parameters.preprocessing.boundstrength = 0
model.parameters.preprocessing.coeffreduce = 0
model.parameters.mip.strategy.search = 1 #traditional
model.parameters.mip.strategy.probe = -1
model.parameters.mip.strategy.heuristicfreq = -1
model.parameters.mip.strategy.fpheur = -1
model.parameters.mip.limits.cutpasses = -1
model.parameters.mip.cuts.bqp = -1
model.parameters.mip.cuts.cliques = -1
model.parameters.mip.cuts.covers = -1
model.parameters.mip.cuts.disjunctive = -1
model.parameters.mip.cuts.flowcovers = -1
model.parameters.mip.cuts.gomory = -1
model.parameters.mip.cuts.gubcovers = -1
model.parameters.mip.cuts.implied = -1
model.parameters.mip.cuts.liftproj = -1
model.parameters.mip.cuts.localimplied = -1
model.parameters.mip.cuts.mcfcut = -1
model.parameters.mip.cuts.mircut = -1
model.parameters.mip.cuts.pathcut = -1
model.parameters.mip.cuts.rlt = -1
model.parameters.mip.cuts.zerohalfcut = -1

sol = model.solve()
print()
if sol is None:
    print("Infeasible")
else:
    model.print_solution()
    values = sol.get_values(vars)
    print(values)

```
$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.