Violated BCH-generated cuts

Problems with syntax of GAMS
Post Reply
Ilya
User
User
Posts: 8
Joined: 9 months ago

Violated BCH-generated cuts

Post by Ilya » 1 month ago

I'm using the BCH cutting planes call (userCutCall ...) in cplex.opt to implement a branch-and-cut algorithm (i.e., trying to reduce the number of variables, but some constraints should be generated on-the-fly).
I can also print the generated cuts into the solution log through GAMS Embedded Python. Only fully integer solutions are used to generate cuts (userCutNewInt 1).

What I'm currently observing is that the cuts generated by BCH during the solution process are neglected at the optimum returned by GAMS/CPLEX.
I can see this because the cuts are printed for small test instances, and sometimes even the cuts stored in the most recent version of bchin.gdx are violated at the final solution.
The BCH cuts are certainly not completely ignored, as changing the sense of the BCH cuts (i.e., the sense_c parameter) changes the final solution.

Can such behavior be expected? It looks as the BCH-generated cuts do not become permanent in CPLEX and their use is to guide/accelerate the solution process, but not to add mandatory/fixed constraints to the model.

Adding new cuts is possible by solving the model multiple times and iteratively constraining it, but this seems to be less favorable, as each new model solve will start its branch-and-bound tree from scratch.

The used version of GAMS is 26.1.0

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

Re: Violated BCH-generated cuts

Post by bussieck » 1 month ago

Yes this is possible behavior. The cuts are used to eliminate fractional solution, never integer solutions. So you don't provide "cuts" you provide constraints and the BCH facility is not designed to do this. I am not saying that Cplex does not allow an orchestration of callbacks to accomplish what you try to do, but with the Cplex callbacks used in BCH that is certainly not the case.

-Michael

Ilya
User
User
Posts: 8
Joined: 9 months ago

Re: Violated BCH-generated cuts

Post by Ilya » 1 month ago

Now I see that BCH supports user cuts, but not user-generated "lazy constraints".

However, the model BCHTSP does something similar by rejecting integer solutions that do not satisfy the "implicit" subtour elimination constraints and by passing the "correcting" cuts to the user cut call.
I suppose that forwarding such "correcting" cuts to the global MIP solver cut pool (or at least accumulating them in the "bcxin.gdx" file) could be a substitute solution with GAMS (although it can possibly neglect some advanced internal solver logic...).

I currently don't have access to CPLEX, moreover GAMS is a much more familiar environment for creating complex optimization models.

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

Re: Violated BCH-generated cuts

Post by bussieck » 1 month ago

Yes, in bchtsp we add the constraint as a cut but also do a check on the incumbent via userincbcall. Using a lazy constraint callback might be better, but that is currently not implemented in BCH/Cplex

-Michael

Post Reply