Difficulties trying to assist BARON by providing a good root node bound

GAMS
1

Reply-to: gamsworld@googlegroups.com

Hello GAMS worlders,

In my work I am trying to help BARON solve faster by providing an initial lower bound that I have found on my own. This lower bound comes from solving a relaxation, so it is less than or equal to (usually strictly less than) the true optimal value. To be clear, this bound wouldn’t change the feasible region of the problem, just hopefully allow BARON to fast-track its exploration by pruning a lot.

The name of the variable minimized by BARON is obj, and I have tried imposing this lower bound two different ways, either using the lower bound attribute of the variable
obj.lo = 32.9949233872;
or alternatively using a constraint
Equation lowerbound;
lowerbound … obj =g= -0.393321687479;

IMPORTANT: If I’m going about this the wrong way and you know another way to give a root node bound, PLEASE let me know!

However, when I try to provide a lower bound in either of these ways, the solver doesn’t behave the way I expect. Here’s the output from solving one of my problems normally, without trying to provide BARON with a lower bound. Let’s call it Solve 1:
Iteration Open nodes Total time Lower bound Upper bound
1 1 000:00:00 -38.0189 -32.8359
1 1 000:00:00 -36.5433 -32.8359
5 0 000:00:00 -32.8359 -32.8359

Solution = -32.835897053578 found at node 5
Best possible = -32.8358970864
Absolute gap = 3.28220011169833E-8 optca = 1E-9
Relative gap = 0.00000 optcr = 1E-9

And here’s the output when I solve the same problem but with a lower bound imposed in either of the above ways. Let’s call it Solve 2:
Iteration Open nodes Total time Lower bound Upper bound
1 1 000:00:00 -32.9949 -32.8359
1 1 000:00:00 -32.9949 -32.8359
45933 31811 000:00:30 -32.9949 -32.8359
(some rows omitted)
912547 638440 000:09:31 -32.9949 -32.8359
958920 670901 000:10:00 -32.9949 -32.8359

Solution = -32.8358971333376 found at node 7
Best possible = -32.9949233872
Absolute gap = 0.159026253862429 optca = 1E-9
Relative gap = 0.00482 optcr = 1E-9

Obviously BARON solves this problem well the normal way so my bound isn’t really needed here, but this is a small problem that demonstrates my issue well, namely that adding a ‘helpful’ bound to an ‘easy’ problem is making it impossible for BARON to terminate.

As you can see, the lower bound I provided to Solve 2 appears in the Lower Bound column of the output, so the bound I gave is having an effect. However, you’ll notice it’s never updated, ie. the solver does not replace this bound with a better (higher, tighter) one over time. This is the root of my problem. Because relative gap is calculated using the current upper and lower bound, and because I’ve given a lower bound which is pretty tight but not exact (ie, not actually achievable), the gap between my initial lower bound and any current upper bound will never close completely and so the algorithm will always run until the time limit (10 minutes in the above case).

I’ll note that the way BARON behaves would make sense if I were giving a bound that was actually achievable, since I would effectively be handing it the global optimal value and asking it to find something within 100optcr% of that target. In my case, though, I just want to communicate to BARON that the objective can’t go lower than x so it can save some time branching, and I still want it to pursue a tighter lower bound than the one I give it. Does anyone know a better way to go about this?

I’m attaching the GAMS model from the above solves. Note the blocks of code which can be commented/uncommented to toggle the bound on/off. I solved these problems on the NEOS server, where they were solved with GAMS version 24.3.3 and BARON version 14.0.3. This may be important for reproducing the behaviour since the recent updates seem to have involve the preprocessing and this phenomenon will not appear for problems which happen to be solved in preprocessing.

Sorry for the long message, and thanks in advance for considering my problem. I’ll really appreciate any insight you can give me.
-Trish

–
bound problem demo.gms (3.61 KB)

2

Reply-to: gamsworld@googlegroups.com

Hi,

I think the conclusion that BARON can do additional pruning due to the improved lower bound is not valid here.
Pruning is done if a new incumbent lowers the upper bound below some node’s lower bound.

However, your lower bound may improve on the gap, and if it were the optimal value, it would also help BARON once it has found a global optimal solution, but there is no other pruning possible.

On the other hand, the branching rules in BARON are probably based on trying to achive a good improvement in the lower bound. As you already provide a very good bound, any of the branching candidates in the early search do not improve the lower bound, which makes it difficult for BARON to choose a good candidate. Without your bound, however, BARON can probably figure out which are the “important” variables in the problem, i.e., which one to branch on to achieve a good improvement in the lower bound. Branching on these candidates will then also help to close the gap between the bound you provided and the optimal value.

Hope that helps,
Stefan



On Thursday, October 9, 2014 10:48:40 PM UTC+2, Trish Gillett wrote:

Hello GAMS worlders,

In my work I am trying to help BARON solve faster by providing an initial lower bound that I have found on my own. This lower bound comes from solving a relaxation, so it is less than or equal to (usually strictly less than) the true optimal value. To be clear, this bound wouldn’t change the feasible region of the problem, just hopefully allow BARON to fast-track its exploration by pruning a lot.

The name of the variable minimized by BARON is obj, and I have tried imposing this lower bound two different ways, either using the lower bound attribute of the variable
obj.lo = 32.9949233872;
or alternatively using a constraint
Equation lowerbound;
lowerbound … obj =g= -0.393321687479;

IMPORTANT: If I’m going about this the wrong way and you know another way to give a root node bound, PLEASE let me know!

However, when I try to provide a lower bound in either of these ways, the solver doesn’t behave the way I expect. Here’s the output from solving one of my problems normally, without trying to provide BARON with a lower bound. Let’s call it Solve 1:
Iteration Open nodes Total time Lower bound Upper bound
1 1 000:00:00 -38.0189 -32.8359
1 1 000:00:00 -36.5433 -32.8359
5 0 000:00:00 -32.8359 -32.8359

Solution = -32.835897053578 found at node 5
Best possible = -32.8358970864
Absolute gap = 3.28220011169833E-8 optca = 1E-9
Relative gap = 0.00000 optcr = 1E-9

And here’s the output when I solve the same problem but with a lower bound imposed in either of the above ways. Let’s call it Solve 2:
Iteration Open nodes Total time Lower bound Upper bound
1 1 000:00:00 -32.9949 -32.8359
1 1 000:00:00 -32.9949 -32.8359
45933 31811 000:00:30 -32.9949 -32.8359
(some rows omitted)
912547 638440 000:09:31 -32.9949 -32.8359
958920 670901 000:10:00 -32.9949 -32.8359

Solution = -32.8358971333376 found at node 7
Best possible = -32.9949233872
Absolute gap = 0.159026253862429 optca = 1E-9
Relative gap = 0.00482 optcr = 1E-9

Obviously BARON solves this problem well the normal way so my bound isn’t really needed here, but this is a small problem that demonstrates my issue well, namely that adding a ‘helpful’ bound to an ‘easy’ problem is making it impossible for BARON to terminate.

As you can see, the lower bound I provided to Solve 2 appears in the Lower Bound column of the output, so the bound I gave is having an effect. However, you’ll notice it’s never updated, ie. the solver does not replace this bound with a better (higher, tighter) one over time. This is the root of my problem. Because relative gap is calculated using the current upper and lower bound, and because I’ve given a lower bound which is pretty tight but not exact (ie, not actually achievable), the gap between my initial lower bound and any current upper bound will never close completely and so the algorithm will always run until the time limit (10 minutes in the above case).

I’ll note that the way BARON behaves would make sense if I were giving a bound that was actually achievable, since I would effectively be handing it the global optimal value and asking it to find something within 100optcr% of that target. In my case, though, I just want to communicate to BARON that the objective can’t go lower than x so it can save some time branching, and I still want it to pursue a tighter lower bound than the one I give it. Does anyone know a better way to go about this?

I’m attaching the GAMS model from the above solves. Note the blocks of code which can be commented/uncommented to toggle the bound on/off. I solved these problems on the NEOS server, where they were solved with GAMS version 24.3.3 and BARON version 14.0.3. This may be important for reproducing the behaviour since the recent updates seem to have involve the preprocessing and this phenomenon will not appear for problems which happen to be solved in preprocessing.

Sorry for the long message, and thanks in advance for considering my problem. I’ll really appreciate any insight you can give me.
-Trish

–
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.

3

Reply-to: gamsworld@googlegroups.com

Hi Stefan, thanks so much for your thoughtful answer. I really appreciate your taking the time.

You’re right about the lower bound not having much to do with pruning. Giving BARON a feasible initial solution (and therefore upper bound) is also something we experiment with - we give BARON a lower bound or a feasible solution or both or neither and then we compare the different solve times. I was thinking of upper bounds when I mentioned pruning. The big picture for us is, we hope that we can give BARON a good lower bound and a feasible initial solution which nearly achieves it and have BARON ‘finish the job’ and get to global optimality very quickly. For example, for the demo problem above, the lower bound is -32.99492339 and we know of a feasible solution with value -32.83589709 (in fact it’s the global opt).

To make sure I understand correctly, your thinking is that the lower bound never improves because my bound clouds BARON’s ability to make good branching choices? Say, at a given iteration no single branching choice that BARON can make will improve the lower bound so it branches arbitrarily, and then at the next iteration this happens again, and so on. Then, instead of proving global optimality in 0.04 seconds, giving an initial lower bound makes BARON spend 102 minutes presumably branching unhelpfully before crashing with a solver error. In my last post I had a 10 minute time limit, but I tried giving it lots of time and that’s what happened. It does not reach max time or max iterations, and I can’t figure out what went wrong from the logs. Memory usage limits, maybe? I’ll attach the solver message and log file in case anyone can make sense of them.

It seems plausible that my bound might negatively impact BARON’s branching, but it’s still hard for me to accept that it should cripple it so completely. Do you really think this can account for such an extreme difference in behaviour? After all, at the end of the day it’s imposed as just a constraint on the objective variable which happens to be redundant (never tight). I can imagine a user ending up in this situation organically and not being able to figure out why their problem won’t solve.

By the way, the results for the normal solve and the lower bounded solve are basicallythe same as above even if I give the global optimal solution as the initial solution in each case. The case with no lower bound proves global optimality in 0.04 seconds again. The case with a lower bound has the global optimal solution as the upper bound but still runs for 109 minutes without improving the lower bound, eventually crashing with a solver error.

-Trish



On Friday, October 10, 2014 9:37:57 AM UTC-4, Stefan Vigerske wrote:

Hi,

I think the conclusion that BARON can do additional pruning due to the improved lower bound is not valid here.
Pruning is done if a new incumbent lowers the upper bound below some node’s lower bound.

However, your lower bound may improve on the gap, and if it were the optimal value, it would also help BARON once it has found a global optimal solution, but there is no other pruning possible.

On the other hand, the branching rules in BARON are probably based on trying to achive a good improvement in the lower bound. As you already provide a very good bound, any of the branching candidates in the early search do not improve the lower bound, which makes it difficult for BARON to choose a good candidate. Without your bound, however, BARON can probably figure out which are the “important” variables in the problem, i.e., which one to branch on to achieve a good improvement in the lower bound. Branching on these candidates will then also help to close the gap between the bound you provided and the optimal value.

Hope that helps,
Stefan



On Thursday, October 9, 2014 10:48:40 PM UTC+2, Trish Gillett wrote:

Hello GAMS worlders,

In my work I am trying to help BARON solve faster by providing an initial lower bound that I have found on my own. This lower bound comes from solving a relaxation, so it is less than or equal to (usually strictly less than) the true optimal value. To be clear, this bound wouldn’t change the feasible region of the problem, just hopefully allow BARON to fast-track its exploration by pruning a lot.

The name of the variable minimized by BARON is obj, and I have tried imposing this lower bound two different ways, either using the lower bound attribute of the variable
obj.lo = 32.9949233872;
or alternatively using a constraint
Equation lowerbound;
lowerbound … obj =g= -0.393321687479;

IMPORTANT: If I’m going about this the wrong way and you know another way to give a root node bound, PLEASE let me know!

However, when I try to provide a lower bound in either of these ways, the solver doesn’t behave the way I expect. Here’s the output from solving one of my problems normally, without trying to provide BARON with a lower bound. Let’s call it Solve 1:
Iteration Open nodes Total time Lower bound Upper bound
1 1 000:00:00 -38.0189 -32.8359
1 1 000:00:00 -36.5433 -32.8359
5 0 000:00:00 -32.8359 -32.8359

Solution = -32.835897053578 found at node 5
Best possible = -32.8358970864
Absolute gap = 3.28220011169833E-8 optca = 1E-9
Relative gap = 0.00000 optcr = 1E-9

And here’s the output when I solve the same problem but with a lower bound imposed in either of the above ways. Let’s call it Solve 2:
Iteration Open nodes Total time Lower bound Upper bound
1 1 000:00:00 -32.9949 -32.8359
1 1 000:00:00 -32.9949 -32.8359
45933 31811 000:00:30 -32.9949 -32.8359
(some rows omitted)
912547 638440 000:09:31 -32.9949 -32.8359
958920 670901 000:10:00 -32.9949 -32.8359

Solution = -32.8358971333376 found at node 7
Best possible = -32.9949233872
Absolute gap = 0.159026253862429 optca = 1E-9
Relative gap = 0.00482 optcr = 1E-9

Obviously BARON solves this problem well the normal way so my bound isn’t really needed here, but this is a small problem that demonstrates my issue well, namely that adding a ‘helpful’ bound to an ‘easy’ problem is making it impossible for BARON to terminate.

As you can see, the lower bound I provided to Solve 2 appears in the Lower Bound column of the output, so the bound I gave is having an effect. However, you’ll notice it’s never updated, ie. the solver does not replace this bound with a better (higher, tighter) one over time. This is the root of my problem. Because relative gap is calculated using the current upper and lower bound, and because I’ve given a lower bound which is pretty tight but not exact (ie, not actually achievable), the gap between my initial lower bound and any current upper bound will never close completely and so the algorithm will always run until the time limit (10 minutes in the above case).

I’ll note that the way BARON behaves would make sense if I were giving a bound that was actually achievable, since I would effectively be handing it the global optimal value and asking it to find something within 100optcr% of that target. In my case, though, I just want to communicate to BARON that the objective can’t go lower than x so it can save some time branching, and I still want it to pursue a tighter lower bound than the one I give it. Does anyone know a better way to go about this?

I’m attaching the GAMS model from the above solves. Note the blocks of code which can be commented/uncommented to toggle the bound on/off. I solved these problems on the NEOS server, where they were solved with GAMS version 24.3.3 and BARON version 14.0.3. This may be important for reproducing the behaviour since the recent updates seem to have involve the preprocessing and this phenomenon will not appear for problems which happen to be solved in preprocessing.

Sorry for the long message, and thanks in advance for considering my problem. I’ll really appreciate any insight you can give me.
-Trish

–
bound demo lbctr-msg.html (25.5 KB)
bound demo lbctr-gams.logfile (18.3 KB)