BCH | Cplex | Branch and Cut

Problems with syntax of GAMS
Post Reply
jgrimm
User
User
Posts: 6
Joined: 3 months ago

BCH | Cplex | Branch and Cut

Post by jgrimm » 3 months ago

Hi all,

currently I am trying to implement an simple branch and cut algorithm using the GAMS Branch & Cut Facility and CPLEX. In a simple implementation a relaxed problem formulation is strengthened in branching process by providing some additional cuts (Problem VRP).

A relaxed MIP problem formulation is given and a subtour identification routine has been defined. The call of the cut routine works out as 2 additional cuts are added to the problem (Log file: *** Calling cut generator. Added 2 cuts). In contrast to the log file output, somehow these provided cuts are not getting effective as:
  • solving goes on ignoring the new cuts added directly providing the global solution and
  • changing values of sense_c does not have any effect on the solution process as well


No further branching / solution evaluation takes place. After stating the "proven optimal solution" following content (fourtimes, for each variable) is printed to the log file: Variable x_ij(Customer1,Customer2) does not exist in model which (most probably) seems to be an error but is not highlighted as one. Of course I have checked syntax, variables and parameters again and again and again to resolve this. Finally, a comparison of bchin.gdx and bchout.gdx shows no differences to me. Also numcuts, sense_c, rhs_c and x_ij_c are looking properly for me. It seems like the introduction of the created cuts into the model is not working as expected. Would be happy for any advice/ hint what might go wrong here.

I am using version 30.1.0 and have attached a sample implementation with sample data reproducing the problem.
GamsForum.zip
*.gdx (sample data) and *.gms file
(3.23 KiB) Downloaded 22 times

Fred
Posts: 201
Joined: 3 years ago

Re: BCH | Cplex | Branch and Cut

Post by Fred » 3 months ago

Hi,

The cut set (cc in your case) elements must be numbers. If you change / c1*c1000 / to / 1*1000 /, cuts will be considered properly. Obviously, the message you get is not very helpful. The documentation also does not mention this requirement. We will improv
VRPCut.gms
(7.11 KiB) Downloaded 26 times
e it.

Some more comments to your approach:
You add constraints using the Cplex cut callback that cut off integer feasible solutions. In that case, you need to make sure to also reject incumbents that violate any of your potential cuts, because otherwise you could have an incumbent that is not feasible due to a cut, but Cplex does not recognize this and keeps the incumbent.
The bchtsp (https://www.gams.com/latest/gamslib_ml/ ... chtsp.html) example from the model library implements such an approach:
- The incumbent checking callback is used to detect subtours. If there are any, the cuts are stored in a gdx file and the solution is rejected.
- The cut callback reads the cut information from the gdx created from the incumbent checking callback. That way it is ensured, that solutions that are cut off are also rejected.

I modified your example accordingly.

I hope this helps!

Best,
Fred

jgrimm
User
User
Posts: 6
Joined: 3 months ago

Re: BCH | Cplex | Branch and Cut

Post by jgrimm » 3 months ago

Hi Fred,

I have been checking the bchtsp.gms before and took some code samples from it. My rework of the code fragments led to the unresolvable issue. It looks much better now. Thank you! In the meantime I have been working on the code and made some more improvements (and fixes). It is running and global optimal solution can be determined and proven. So far so good.

Unfortunately, I am wondering about the following. Check of the log files led to an surprising insight. Several incumbent check (rejection) calls in series without calls of the cut GAMS program are given. Am I not losing (important) cuts with the current coding because the nextcut.gdx is overwritten everytime when subtour identification (GAMS Program) is executed? As far as I know execute_unload is overwriting the old *.gdx file.

And is there a chance to export the (CPLEX) cut pool and make it (more) visible?

Kind regards,
Jonathan

Fred
Posts: 201
Joined: 3 years ago

Re: BCH | Cplex | Branch and Cut

Post by Fred » 3 months ago

Jonathan,

It is up to cplex to decide when to use the user cut callback. So it is not surprising that it may not be called between several incumbent checking callbacks. So you are right, with the approach in bchtsp, some cuts may be overwritten before CPLEX adds them to the cut pool. This may not be ideal with regard to performance. But that should not be too difficult to change. Instead of overwriting the GDX file that stores the cuts computed by the incumbent checking callback, you could for example write them to different gdx files and then make sure that the cut callback loads all the relevant cuts.

If you are struggling with this, the most efficient way to help might be to post another example that illustrates the behavior you described. Then I could try to adjust it.

Best,
Fred

jgrimm
User
User
Posts: 6
Joined: 3 months ago

Re: BCH | Cplex | Branch and Cut

Post by jgrimm » 3 months ago

Hi Fred,

I was able to implement it on my own.

I have done two implementations and seems like both are working properly. First implementation is using BCH facility (usercutcall and userincb). Second implementation is looping over branch & bound solution process several times (and adding cuts after solution has been found which might be violating relaxed constraints). I have seen this in another example (I do not remember which one :|).

Second solution doesn't look that nice as I have to add three equations. Is there a way of using sense_c(cc) information automatically in one equation as BCH facility is doing? Currently I am using this kind of workaround.

Code: Select all

cuts_1(allcuts)$(sense_c(allcuts) = 1) .. sum((i,j), x_ij_c(allcuts,i,j)*x_ij(i,j)) =l= rhs_c(allcuts);
cuts_2(allcuts)$(sense_c(allcuts) = 2) .. sum((i,j), x_ij_c(allcuts,i,j)*x_ij(i,j)) =e= rhs_c(allcuts);
cuts_3(allcuts)$(sense_c(allcuts) = 3) .. sum((i,j), x_ij_c(allcuts,i,j)*x_ij(i,j)) =g= rhs_c(allcuts);
Maybe this is the same what BCH facility is doing. Of course I would prefer something like that:

Code: Select all

cuts(allcuts) .. sum((i,j), x_ij_c(allcuts,i,j)*x_ij(i,j)) =*sense_c(allcuts)* = rhs_c(allcuts);
Is there a way to achieve the simpler implementation? I have added my implementation below.
Gams Forum.zip
(4.32 KiB) Downloaded 10 times
And secondly, is there a global parameter to enable/disable debugging via "Display"? Or do I have to work with Conditionals / If Statements? I am currently not sure if "Display" might be a time consuming operation.

Regards,
Jonathan

Fred
Posts: 201
Joined: 3 years ago

Re: BCH | Cplex | Branch and Cut

Post by Fred » 2 months ago

Hi Jonathan,

To avoid confusion, let's call your first approach "BCH approach" and the second approach "loop approach".

I get your idea but there is no such syntax that allows you to do something like

Code: Select all

=*sense_c(allcuts)*=
with the loop approach. The sense_c and rhs_c stuff is designed for the BCH user cut callback and when implementing cuts in a loop approach, it would be more common to write cuts just like normal constraints. For example, you know that your subtour elimination constraints are always =l= constraints, so you could write them as.

Code: Select all

subtourElim(t)$subtours(t).. sum(tour(i,j,t), x_ij(i,j)) =l= sum(tour(ix,ix2,t),1) - 1;
Of course, there is nothing wrong with how you define the cuts in your current loop approach. It just appears a bit uncommon to me. Maybe because implementing BCH first and then converting this to a loop approach seems a bit unusual. While the general idea between both approaches is the same, the main difference is that with BCH you generate the model only once and then add cuts through CPLEX' user cut callback.
With the loop approach you have to generate the model, let CPLEX solve, read the solution, generate the model, let CPLEX solve, etc... So the BCH approach is to some extent more efficient but also a bit more challenging to implement. Hence, I think it is common to implement a loop approach first and then (if necessary) see if performance can be improved via BCH.


Display statements for large symbols can be time consuming and also result in a huge lst file. There is no option to suppress them automatically. When you write code, you could prepare it for some debug displays, for example by doing sth like.

Code: Select all

$if not set $set DEBUG 0
*...
display$%DEBUG 'some debug output';
Now if you run your code (let's assume its in myFile.gms) with

gams myfile --DEBUG=1

you will get the debug display, otherwise not.

I hope this helps!

Fred

jgrimm
User
User
Posts: 6
Joined: 3 months ago

Re: BCH | Cplex | Branch and Cut

Post by jgrimm » 2 months ago

Hi Fred,

perfectly answered. Thank you for your help ! :D

Kind regards,
Jonathan

Post Reply