GAMS BCH with SBB

Archiver · December 16, 2014, 12:34am

Is anybody having issues with using BCH heuristics with SBB? SBB is unable to recognize integer solution from heuristic.

I tried saving the solution into a gdx file inside my heuristic code, loaded this solution inside my main model and examined the initpoint. Primal constraints and P/D bounds were satisfied. But SBB still is unable to recognize this. I have no idea how to figure this - GMSbch.lst and main.lst are disconnected.

Is there a way I can use userincball or something to bypass SBB’s incumbent checking and use my own instead? How do I go about this?

It would be useful to have a flow chart of different calls to user routines in the BCH to understand what’s going on, I think.

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

Archiver · December 16, 2014, 3:20pm

Hmmm. I would try to load the solution into GAMS and load the solution before the solve. So first call the model and save away the solution from the heuristic (use an execute_unload ‘mysolution.gdx’; at the end of the heuristic). Run the model again and execute_loadpoint ‘mysolution.gdx’; option limrow=99999;. The listing file in the equation listing will have the infeasibilities. If there are no infeasibilities please contact support@gams.com. Find attached my slightly modified example from GAMS Model Library.

Hope this helps.
Michael

On Monday, December 15, 2014 6:34:59 PM UTC-5, Sreekanth Rajagopalan wrote:

Is anybody having issues with using BCH heuristics with SBB? SBB is unable to recognize integer solution from heuristic.

I tried saving the solution into a gdx file inside my heuristic code, loaded this solution inside my main model and examined the initpoint. Primal constraints and P/D bounds were satisfied. But SBB still is unable to recognize this. I have no idea how to figure this - GMSbch.lst and main.lst are disconnected.

Is there a way I can use userincball or something to bypass SBB’s incumbent checking and use my own instead? How do I go about this?

It would be useful to have a flow chart of different calls to user routines in the BCH to understand what’s going on, I think.

–
bchtlbas.gms (6.17 KB)

Archiver · December 16, 2014, 5:12pm

Thanks, Michael.

I tested this now. I find three INFES markers with E-13 to E-11 values for equations. When examiner checks for initpoint, it uses tol E-6 by default, I believe. So, is this for tolerances of equations as well?

I know that my model has poor scaling. So is this related to tolInfRep model attribute? It is 1E-6 by default and shouldn’t be a problem, right? Or is SBB checking solutions with a different tolerance?

On Tuesday, December 16, 2014 9:20:13 AM UTC-5, Michael Bussieck wrote:

Hmmm. I would try to load the solution into GAMS and load the solution before the solve. So first call the model and save away the solution from the heuristic (use an execute_unload ‘mysolution.gdx’; at the end of the heuristic). Run the model again and execute_loadpoint ‘mysolution.gdx’; option limrow=99999;. The listing file in the equation listing will have the infeasibilities. If there are no infeasibilities please contact sup...@gams.com. Find attached my slightly modified example from GAMS Model Library.

Hope this helps.
Michael

On Monday, December 15, 2014 6:34:59 PM UTC-5, Sreekanth Rajagopalan wrote:

Is anybody having issues with using BCH heuristics with SBB? SBB is unable to recognize integer solution from heuristic.

I tried saving the solution into a gdx file inside my heuristic code, loaded this solution inside my main model and examined the initpoint. Primal constraints and P/D bounds were satisfied. But SBB still is unable to recognize this. I have no idea how to figure this - GMSbch.lst and main.lst are disconnected.

Is there a way I can use userincball or something to bypass SBB’s incumbent checking and use my own instead? How do I go about this?

It would be useful to have a flow chart of different calls to user routines in the BCH to understand what’s going on, I think.

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

Archiver · December 16, 2014, 9:58pm

SBB checks also for integer feasibility (with its tolerances, SBB option epint (default is 1e-5)) and then passes this point to the solver (with fixed bounds for the discrete variables). If the solver comes back successfully, SBB accepts the solution. So a) the discrete variables was not within the tolerance or b) the solver does not like to be restarted from the “feasible” point. When you set SBB option loglevel 2 you will see what the NLP solver will do with the fixed run (in case the discrete variable feasibility check is ok).

Hope this helps,
Michael

On Tuesday, December 16, 2014 11:12:44 AM UTC-5, Sreekanth Rajagopalan wrote:

Thanks, Michael.

I tested this now. I find three INFES markers with E-13 to E-11 values for equations. When examiner checks for initpoint, it uses tol E-6 by default, I believe. So, is this for tolerances of equations as well?

I know that my model has poor scaling. So is this related to tolInfRep model attribute? It is 1E-6 by default and shouldn’t be a problem, right? Or is SBB checking solutions with a different tolerance?

On Tuesday, December 16, 2014 9:20:13 AM UTC-5, Michael Bussieck wrote:

Hmmm. I would try to load the solution into GAMS and load the solution before the solve. So first call the model and save away the solution from the heuristic (use an execute_unload ‘mysolution.gdx’; at the end of the heuristic). Run the model again and execute_loadpoint ‘mysolution.gdx’; option limrow=99999;. The listing file in the equation listing will have the infeasibilities. If there are no infeasibilities please contact sup...@gams.com. Find attached my slightly modified example from GAMS Model Library.

Hope this helps.
Michael

On Monday, December 15, 2014 6:34:59 PM UTC-5, Sreekanth Rajagopalan wrote:

Is anybody having issues with using BCH heuristics with SBB? SBB is unable to recognize integer solution from heuristic.

I tried saving the solution into a gdx file inside my heuristic code, loaded this solution inside my main model and examined the initpoint. Primal constraints and P/D bounds were satisfied. But SBB still is unable to recognize this. I have no idea how to figure this - GMSbch.lst and main.lst are disconnected.

Is there a way I can use userincball or something to bypass SBB’s incumbent checking and use my own instead? How do I go about this?

It would be useful to have a flow chart of different calls to user routines in the BCH to understand what’s going on, I think.

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

Archiver · December 17, 2014, 12:49am

Hmm. The heuristic actually fixes binaries and solves NLP, so it should be integer feasible. If I fix the binaries to the values given by heuristic and solve it via SBB, it does declare “root optimal and relaxation gives integer solution.” Input point infeasibility reported by CONOPT is E-7 to E-9, in general.

Should heuristic solution always satisfy relaxed binary variable bounds at any node? Even so, SBB should recognize my solution at the root or even the initial integer feasible point, right?

On Tuesday, December 16, 2014 3:58:11 PM UTC-5, Michael Bussieck wrote:

SBB checks also for integer feasibility (with its tolerances, SBB option epint (default is 1e-5)) and then passes this point to the solver (with fixed bounds for the discrete variables). If the solver comes back successfully, SBB accepts the solution. So a) the discrete variables was not within the tolerance or b) the solver does not like to be restarted from the “feasible” point. When you set SBB option loglevel 2 you will see what the NLP solver will do with the fixed run (in case the discrete variable feasibility check is ok).

Hope this helps,
Michael

On Tuesday, December 16, 2014 11:12:44 AM UTC-5, Sreekanth Rajagopalan wrote:

Thanks, Michael.

I tested this now. I find three INFES markers with E-13 to E-11 values for equations. When examiner checks for initpoint, it uses tol E-6 by default, I believe. So, is this for tolerances of equations as well?

I know that my model has poor scaling. So is this related to tolInfRep model attribute? It is 1E-6 by default and shouldn’t be a problem, right? Or is SBB checking solutions with a different tolerance?

On Tuesday, December 16, 2014 9:20:13 AM UTC-5, Michael Bussieck wrote:

Hmmm. I would try to load the solution into GAMS and load the solution before the solve. So first call the model and save away the solution from the heuristic (use an execute_unload ‘mysolution.gdx’; at the end of the heuristic). Run the model again and execute_loadpoint ‘mysolution.gdx’; option limrow=99999;. The listing file in the equation listing will have the infeasibilities. If there are no infeasibilities please contact sup...@gams.com. Find attached my slightly modified example from GAMS Model Library.

Hope this helps.
Michael

On Monday, December 15, 2014 6:34:59 PM UTC-5, Sreekanth Rajagopalan wrote:

Is anybody having issues with using BCH heuristics with SBB? SBB is unable to recognize integer solution from heuristic.

I tried saving the solution into a gdx file inside my heuristic code, loaded this solution inside my main model and examined the initpoint. Primal constraints and P/D bounds were satisfied. But SBB still is unable to recognize this. I have no idea how to figure this - GMSbch.lst and main.lst are disconnected.

Is there a way I can use userincball or something to bypass SBB’s incumbent checking and use my own instead? How do I go about this?

It would be useful to have a flow chart of different calls to user routines in the BCH to understand what’s going on, I think.

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

Archiver · December 17, 2014, 8:14pm

Some more questions:

Should my heuristic solution lie in the feasible region of current node’s relaxation? It doesn’t make sense to me though.
Does SBB make use model status returned in accepting/rejecting solutions. Because my model is nonconvex even when integrality is dropped/fixed. Let’s say I am not worried about global optimum or know that SBB will end up in global optimum. Even this check doesn’t make sense because any local solution is also a valid upper bound.

To me all SBB should be doing is check for primal feasibility within tolerances and accept integer solutions. Am I getting something wrong here?

Thanks,
Sreekanth

\

Archiver · December 18, 2014, 9:37am

Sreekanth, See my comments below. Michael

On Wednesday, December 17, 2014 2:14:43 PM UTC-5, Sreekanth Rajagopalan wrote:

Some more questions:

Should my heuristic solution lie in the feasible region of current node’s relaxation? It doesn’t make sense to me though.

No SBB does not care if the solution you provide with your heuristic is feasible with respect to branching decisions made so far.

2. Does SBB make use model status returned in accepting/rejecting solutions. Because my model is nonconvex even when integrality is dropped/fixed. Let’s say I am not worried about global optimum or know that SBB will end up in global optimum. Even this check doesn’t make sense because any local solution is also a valid upper bound.

The way SBB checks for feasibility of the solution provided by the heuristic is to ask an NLP solver to verify the solution after fixing the discrete variables and starting the NLP solver from the exact primal solution given by the heuristic. So the NLP starts out with a feasible solution (if the solution provided by the heuristic is indeed feasible) and usually (unless the numerics are really terrible) stops with a feasible solution. SBB then checks the status code from the NLP solver to determine if the solution from the heuristic was feasible (very similar to solving a regular node in the B&B tree). The advantage using the NLP is two fold. First, we use the same tolerances for feasibility throughout the optimization and second, we get the dual solution from the NLP solver in case this solution turns out to be the one we eventually will report back to the user.

To me all SBB should be doing is check for primal feasibility within tolerances and accept integer solutions. Am I getting something wrong here?

I suggest, you turn on the ‘loglevel 2’ and send the log file, so we can together inspect why SBB rejects your heuristic solution.

Thanks,
Sreekanth

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

Archiver · December 18, 2014, 2:25pm

Thanks, Michael.

I notice that when I run bchtlbas.gms (available at GAMS/BCH/docs) with loglevel=2, I see two runs of CONOPT for every node - one for lower bounding and one where input point has 0 infeasibility. Whereas I see only one CONOPT run for everynode. However, I do see the dot (.) in the first line of log - indicating a call to userheur was made (and the same is recorded in GMSbch.lst as well.) So is this some issue of SBB not reading back solution from my model?

My model is a nonconvex MINLP (let’s say I am not worried if the solution is globally optimal for now.) So the solution from heuristic is returned with model status ‘locally optimal’. Same would be the case when SBB gives it to NLP solver with binaries fixed.

I would have to make quite a few changes before I can send the log. Also, I will have to take care of a few things before I can do that.

I really appreciate your help. Let me know if you understand why the second CONOPT run is not working in my case.

Thanks.

On Thursday, December 18, 2014 3:37:24 AM UTC-5, Michael Bussieck wrote:

Sreekanth, See my comments below. Michael

On Wednesday, December 17, 2014 2:14:43 PM UTC-5, Sreekanth Rajagopalan wrote:

Some more questions:

Should my heuristic solution lie in the feasible region of current node’s relaxation? It doesn’t make sense to me though.

No SBB does not care if the solution you provide with your heuristic is feasible with respect to branching decisions made so far.

2. Does SBB make use model status returned in accepting/rejecting solutions. Because my model is nonconvex even when integrality is dropped/fixed. Let’s say I am not worried about global optimum or know that SBB will end up in global optimum. Even this check doesn’t make sense because any local solution is also a valid upper bound.

The way SBB checks for feasibility of the solution provided by the heuristic is to ask an NLP solver to verify the solution after fixing the discrete variables and starting the NLP solver from the exact primal solution given by the heuristic. So the NLP starts out with a feasible solution (if the solution provided by the heuristic is indeed feasible) and usually (unless the numerics are really terrible) stops with a feasible solution. SBB then checks the status code from the NLP solver to determine if the solution from the heuristic was feasible (very similar to solving a regular node in the B&B tree). The advantage using the NLP is two fold. First, we use the same tolerances for feasibility throughout the optimization and second, we get the dual solution from the NLP solver in case this solution turns out to be the one we eventually will report back to the user.

To me all SBB should be doing is check for primal feasibility within tolerances and accept integer solutions. Am I getting something wrong here?

I suggest, you turn on the ‘loglevel 2’ and send the log file, so we can together inspect why SBB rejects your heuristic solution.

Thanks,
Sreekanth

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

Archiver · December 18, 2014, 4:27pm

Hi,

SBB solves the root NLP (first NLP) than it solves node 0 restarting from the primal/dual solution of the root node. This for well behaved models should return immediately (second NLP). Now SBB starts calling the heurstic and/or does branching and calls the NLP to solve the nodes. The nodes are only solved once (not as the root node). Again, with the detailed log we can probably explain why SBB does not accept your solution but without that we just keep on speculating. All the issues you describe are independent of convex or non-convex problems. If your heuristic holds a solution you should see a + and the heuristic objective value in the SBB log. More when we get the ‘loglevel 2’ log.

Michael

On Thursday, December 18, 2014 8:25:04 AM UTC-5, Sreekanth Rajagopalan wrote:

Thanks, Michael.

I notice that when I run bchtlbas.gms (available at GAMS/BCH/docs) with loglevel=2, I see two runs of CONOPT for every node - one for lower bounding and one where input point has 0 infeasibility. Whereas I see only one CONOPT run for everynode. However, I do see the dot (.) in the first line of log - indicating a call to userheur was made (and the same is recorded in GMSbch.lst as well.) So is this some issue of SBB not reading back solution from my model?

My model is a nonconvex MINLP (let’s say I am not worried if the solution is globally optimal for now.) So the solution from heuristic is returned with model status ‘locally optimal’. Same would be the case when SBB gives it to NLP solver with binaries fixed.

I would have to make quite a few changes before I can send the log. Also, I will have to take care of a few things before I can do that.

I really appreciate your help. Let me know if you understand why the second CONOPT run is not working in my case.

Thanks.

On Thursday, December 18, 2014 3:37:24 AM UTC-5, Michael Bussieck wrote:

Sreekanth, See my comments below. Michael

On Wednesday, December 17, 2014 2:14:43 PM UTC-5, Sreekanth Rajagopalan wrote:

Some more questions:

Should my heuristic solution lie in the feasible region of current node’s relaxation? It doesn’t make sense to me though.

No SBB does not care if the solution you provide with your heuristic is feasible with respect to branching decisions made so far.

2. Does SBB make use model status returned in accepting/rejecting solutions. Because my model is nonconvex even when integrality is dropped/fixed. Let’s say I am not worried about global optimum or know that SBB will end up in global optimum. Even this check doesn’t make sense because any local solution is also a valid upper bound.

The way SBB checks for feasibility of the solution provided by the heuristic is to ask an NLP solver to verify the solution after fixing the discrete variables and starting the NLP solver from the exact primal solution given by the heuristic. So the NLP starts out with a feasible solution (if the solution provided by the heuristic is indeed feasible) and usually (unless the numerics are really terrible) stops with a feasible solution. SBB then checks the status code from the NLP solver to determine if the solution from the heuristic was feasible (very similar to solving a regular node in the B&B tree). The advantage using the NLP is two fold. First, we use the same tolerances for feasibility throughout the optimization and second, we get the dual solution from the NLP solver in case this solution turns out to be the one we eventually will report back to the user.

To me all SBB should be doing is check for primal feasibility within tolerances and accept integer solutions. Am I getting something wrong here?

I suggest, you turn on the ‘loglevel 2’ and send the log file, so we can together inspect why SBB rejects your heuristic solution.

Thanks,
Sreekanth

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.