BCH | Cplex | Branch and Cut

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

BCH | Cplex | Branch and Cut

Post by jgrimm » 3 weeks 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 12 times

Fred
Posts: 192
Joined: 3 years ago

Re: BCH | Cplex | Branch and Cut

Post by Fred » 2 weeks 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 12 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: 3
Joined: 3 weeks ago

Re: BCH | Cplex | Branch and Cut

Post by jgrimm » 2 weeks 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: 192
Joined: 3 years ago

Re: BCH | Cplex | Branch and Cut

Post by Fred » 2 weeks 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: 3
Joined: 3 weeks ago

Re: BCH | Cplex | Branch and Cut

Post by jgrimm » 3 days 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 2 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

Post Reply