Modifying the equations during the B&B or B&C algorithm

Solver related questions
Post Reply
qploussard
User
User
Posts: 2
Joined: 5 months ago

Modifying the equations during the B&B or B&C algorithm

Post by qploussard » 5 months ago

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

User avatar
bussieck
Moderator
Moderator
Posts: 208
Joined: 2 years ago

Re: Modifying the equations during the B&B or B&C algorithm

Post by bussieck » 5 months ago

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

qploussard
User
User
Posts: 2
Joined: 5 months ago

Re: Modifying the equations during the B&B or B&C algorithm

Post by qploussard » 5 months ago

I understand this.

The reason why I am asking this is because one of the constraint of my MILP problem contains a big-M parameter:
variable(i) <= bigM(i)*(1-x(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.

Post Reply