Bug in bound tightening with symmetric bounds

[krishpat]

I am running this NLP and Alpine seems to have a bug in bound tightening:

m = Model(solver=AlpineSolver(nlp_solver = IpoptSolver(print_level=0), mip_solver = CplexSolver(CPX_PARAM_SCRIND=0)))
@variable(m, LB <= x[1:2] <= UB)
@objective(m, Min, 6*x[1]^2 + 4*x[2]^2 - 2.5*x[1]*x[2])
@NLconstraint(m, x[1]*x[2] >= 8)
solve(m)

When LB = -1000 and UB = 1000, after bound tightening it displays

finished bound tightening in 1 iterations, applying tighten bounds

Gap in Iter 1 is "LARGE" and converges to Global optimum in 45s.

But, when LB = -1000 and UB = 1000.1, after bound tightening it displays

finished bound tightening in 10 iterations, applying tighten bounds
[DEBUG] VAR 1 BOUND contracted 100.0% |-1000.0 --> | -3.3644 - 3.3644 | <-- 1000.1 |
[DEBUG] VAR 2 BOUND contracted 100.0% |-1000.0 --> | -3.976 - 3.976 | <-- 1000.1 |

Gap in Iter 1 is 89.34% and converges to Global optimum in 3.6s.

I tested this for various values of LB & UB and the issue of not updating the tightened bounds exists whenever the bounds are symmetric about the origin. Either the tightened bounds are not getting applied or the bounds are not getting tightened in this case.

[harshangrjn]

@krishpat Good catch! Will get back to you once we look at it.

[kaarthiksundar]

@krishpat First thing, your first run time is huge with symmetric bounds because of precompiling. When everything is precompiled, for the case with LB = -1000 and UB = 1000, the run time on my machine is 2 seconds.

Secondly, for the problem you have, with symmetric bounds, the initial local solve is infeasible. When we do bound-tightening (with the local solve being feasible and say the local objective value is y), we add an additional constraint to the bound-tightening (see equation 8(b) in https://arxiv.org/pdf/1707.02514.pdf). This actually makes the OBBT more effective. In your symmetric bound case, this constraint was not added, and the OBBT was not able to tighten the bounds at all (after the first iteration the bounds were still [-1000, 1000] on both the variables and this terminated the bound-tightening). In the second case with 1000.1, Ipopt gave a local feasible solution and hence OBBT was able to close the variable bounds (after 10 iterations) to the value displayed in the log.

Infact, I tried your experiment - will symmetric bounds, Ipopt seems to have an issue with computing a local optimal solution (it always reports infeasible, for all the tests that I conducted). With asymmetric bounds, Ipopt always gives a feasible solution. Let me know if this answers the question. If so, I will close this issue.

[krishpat]

@kaarthiksundar Thanks. The run time I mentioned for the symmetric bounds case was excluding the precompiling, that is, running the same problem for second time in the Julia console. I am still seeing large run times. Here is the last iteration: | 58.3837 | 58.3801 || 58.3837 | 58.3801 | 0.00613 | 44.31s | | finish

Changing the LB and UB to -10^4 to 10^4, Alpine claims to have done 10 iterations of bound tightening. Does that mean that the bounds on the variables were not tightened but Alpine ran 10 iterations of bound tightening?

[harshangrjn]

@kaarthiksundar I also see that the run time for symmetric case is quite high, like around 42.3 s excluding the precompiling time.

[harshangrjn]

@krishpat Here is a workaround to make Ipopt converge to a feasible point in case of symmetric bounds also. Warm-start Ipopt with a trivial feasible solution for your constraint by adding these lines to your formulation.

setvalue(x[1], 1)
setvalue(x[2], 8)

[kaarthiksundar]

@krishpat I still get some discrepancy with the time and I do not know why. But the last iteration matches.

Presolve ended.
Presolve time = 0.09s
 | NLP           | MIP           || Objective     | Bound         | GAP (%)       | CLOCK         | | Iter   
 | -             | -2.499993576e6|| Inf           | -2.499993576e6| LARGE         | 0.13s         | | 1
 | 58.3837       | -624999.8393  || 58.3837       | -624999.8393  | LARGE         | 0.41s         | | 2
 | 58.3837       | -156249.9411  || 58.3837       | -156249.9411  | LARGE         | 0.49s         | | 3
 | 58.3837       | -39062.4838   || 58.3837       | -39062.4838   | LARGE         | 0.56s         | | 4
 | 58.3837       | -9765.6189    || 58.3837       | -9765.6189    | LARGE         | 0.78s         | | 5
 | 58.3837       | -2441.4051    || 58.3837       | -2441.4051    | LARGE         | 1.29s         | | 6
 | 58.3837       | -610.3513     || 58.3837       | -610.3513     | LARGE         | 1.43s         | | 7
 | 58.3837       | -152.5878     || 58.3837       | -152.5878     | 361.35355     | 1.58s         | | 8
 | 58.3837       | -38.147       || 58.3837       | -38.147       | 165.33839     | 1.75s         | | 9
 | 58.3837       | 51.1472       || 58.3837       | 51.1472       | 12.39469      | 1.95s         | | 10
 | 58.3837       | 51.1551       || 58.3837       | 51.1551       | 12.3812       | 2.41s         | | 11
 | 58.3837       | 57.7373       || 58.3837       | 57.7373       | 1.10714       | 2.63s         | | 12
 | 58.3837       | 57.7416       || 58.3837       | 57.7416       | 1.09982       | 2.88s         | | 13
 | 58.3837       | 58.3277       || 58.3837       | 58.3277       | 0.0959        | 3.15s         | | 14
 | 58.3939       | 58.3287       || 58.3837       | 58.3287       | 0.09411       | 3.41s         | | 15
 | 58.3942       | 58.3641       || 58.3837       | 58.3641       | 0.03345       | 3.72s         | | 16
 | 58.3837       | 58.3644       || 58.3837       | 58.3644       | 0.03305       | 4.4s          | | 17
 | 58.3837       | 58.38         || 58.3837       | 58.38         | 0.00621       | 5.18s         | | finish
 Alpine ended with status Optimal
:Optimal

As for your question on LB and UB being -10^4 and 10^4, I am not able to replicate the 10 iteration BT procedure. In my local system, it ends in 1 iteration and bounds are not tightened because of no feasible local optimal solution produced by Ipopt. Can you recheck?

[harshangrjn]

Like @krishpat, I am also observing 10 iterations in bound tightening when the bounds are -10^4 and 10^4.

[harshangrjn]

@krishpat As a matter of fact, the point with which you warm start does not have to be feasible too. You can choose any random point in the domain of variables except the origin to make the Ipopt converge to a feasible solution as Ipopt doesn't seem to like the (0,0) point.

@krishpat Here is a workaround to make Ipopt converge to a feasible point in case of symmetric bounds also. Warm-start Ipopt with a trivial feasible solution for your constraint by adding these lines to your formulation.

setvalue(x[1], 1)
setvalue(x[2], 8)

[kaarthiksundar]

Like @krishpat, I am also observing 10 iterations in bound tightening when the bounds are -10^4 and 10^4.

@harshangrjn I would recommend you to take a look at the internal logs to figure out of there is a bug and if there is one, fix it. I am not able to replicate it in both my systems.

[kaarthiksundar]

@krishpat This is due to a solver issue. I was using CPLEX 12.7 and you and @harshangrjn were using CPLEX 12.8. I was able to replicate the issue with CPLEX 12.8. And after 10 iterations, the bounds are indeed getting contracted slightly. So to answer your question - the bounds do get contracted after 10 iterations. But as Harsha suggested, a warm start will help to improve the performance of the solver.