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)