Hello,
I would like to know whether it is possible to modify the constraints of a MILP problem at each node of the search tree.
When going through the search tree of a MILP problem, at each node, we introduce some bounds on the integer variables.
These bounds should allow me to refine the parameters of the problem to make the problem tighter.
The problem is that, for common MILP solvers, I cannot find any options that would allow me to update the constraints at each node.
Does someone know how I could do this?
Thank you,
Quentin
Modifying the equations during the B&B or B&C algorithm

 User
 Posts: 4
 Joined: 8 months ago
Re: Modifying the equations during the B&B or B&C algorithm
Quentin,
I don't know of any code that allows you to arbitrarily change the model at a node. For a good reason: B&B is an enumeration scheme that let's you find the solution to a given problem. If you can just arbitrarily change the model at any node, what problem are you eventually solving? A feasible solution or a bound established in some part of the tree means nothing to the rest of the tree.
The tightening of bounds and rhs (based on branching done so far) is done by modern B&C solvers by performing a node presolve and is usally on by default (see e.g. https://www.gams.com/latest/docs/S_CPLE ... EXpreslvnd).
Michael
I don't know of any code that allows you to arbitrarily change the model at a node. For a good reason: B&B is an enumeration scheme that let's you find the solution to a given problem. If you can just arbitrarily change the model at any node, what problem are you eventually solving? A feasible solution or a bound established in some part of the tree means nothing to the rest of the tree.
The tightening of bounds and rhs (based on branching done so far) is done by modern B&C solvers by performing a node presolve and is usally on by default (see e.g. https://www.gams.com/latest/docs/S_CPLE ... EXpreslvnd).
Michael

 User
 Posts: 4
 Joined: 8 months ago
Re: Modifying the equations during the B&B or B&C algorithm
I understand this.
The reason why I am asking this is because one of the constraint of my MILP problem contains a bigM parameter:
variable(i) <= bigM(i)*(1x(i))
where x is a binary variable.
It turns out that, depending on how x(i) is bounded in the search tree, bigM(k) for k =/= i can be refined, i.e. reduced, making the MILP problem tighter as we travel through the search tree.
This refinement of bigM(k) can then be used for all the nodes that are the descendants of the first node where we can apply this refinement.
Refining this bigM parameter should not change the model, neither change the optimal solution.
But this can help tightening the problem and decrease the integrality gap faster during the search of the MILP solution.
The reason why I am asking this is because one of the constraint of my MILP problem contains a bigM parameter:
variable(i) <= bigM(i)*(1x(i))
where x is a binary variable.
It turns out that, depending on how x(i) is bounded in the search tree, bigM(k) for k =/= i can be refined, i.e. reduced, making the MILP problem tighter as we travel through the search tree.
This refinement of bigM(k) can then be used for all the nodes that are the descendants of the first node where we can apply this refinement.
Refining this bigM parameter should not change the model, neither change the optimal solution.
But this can help tightening the problem and decrease the integrality gap faster during the search of the MILP solution.