Lower bound exceeds upper bound in separable MINLP

[claud10cv]

The attached MINLP makes Alpine behave erratically, as it computes a lower (dual) bound that exceeds the upper (primal) bound since the first iteration. The underlying solvers are: mip solver CPLEX 20.1, nlp local solver Juniper (Ipopt + CPLEX), using default settings except for the number of threads set to 1 in all cases. It raises multiple warnings during presolve (see below). Here is the output of solving this minimization problem using Alpine:

PROBLEM STATISTICS
  Objective sense = Min
  # Variables = 8
  # Bin-Int Variables = 4
  # Constraints = 8
  # NL Constraints = 0
  # Linear Constraints = 8
  # Detected convex constraints = 0
  # Detected nonlinear terms = 8
  # Variables involved in nonlinear terms = 4
  # Potential variables for partitioning = 4
SUB-SOLVERS USED BY ALPINE
  MINLP local solver = Juniper
  MIP solver = Cplex
ALPINE CONFIGURATION
  Maximum iterations (lower-bounding MIPs) =  99
  Relative global optimality gap = 9.999999999999999e-5%
  Discretization ratio = 4
  Bound-tightening (OBBT) presolve = true
  Maximum iterations (OBBT) = 10
PRESOLVE 
  Doing local search
  Local solver returns a feasible point with value 358.063
  Starting bound-tightening
!!!!!!!!!!!!!!!!!!!!!!!!!!!!┌ Warning:   Warning: VAR1 SOL=786.99999 out of discretization [769.43114,776.594]. Hence, taking middle point.
└ @ Alpine ~/.julia/packages/Alpine/0w1zg/src/amp.jl:267
┌ Warning:   Warning: VAR2 SOL=0.0 out of discretization [10.4252,17.55648]. Hence, taking middle point.
└ @ Alpine ~/.julia/packages/Alpine/0w1zg/src/amp.jl:267
┌ Warning:   Warning: VAR3 SOL=165.00002 out of discretization [171.42854000000003,184.22337000000002]. Hence, taking middle point.
└ @ Alpine ~/.julia/packages/Alpine/0w1zg/src/amp.jl:267
┌ Warning:   Warning: VAR4 SOL=47.99998 out of discretization [28.863410000000002,41.427640000000004]. Hence, taking middle point.
└ @ Alpine ~/.julia/packages/Alpine/0w1zg/src/amp.jl:267
  Completed presolve in 2.06s
LOWER-BOUNDING ITERATIONS
====================================================================================================
| Iter   | Incumbent       | Best Incumbent      | Lower Bound        | Gap (%)         | Time      
| 1      | 358.063         | 358.063             | 375.3419           | 4.826           | 2.09s            
| 2      | 375.8716        | 358.063             | 375.7392           | 4.937           | 2.15s            

model.zip

[harshangrjn]

Yes - this is a bug which needs to be fixed. Can you plz share the JuMP model with the Alpine's settings, instead of the lp file?

[claud10cv]

Thank you. I am attaching a minimal example to reproduce the error. The relevant files are:

1. bug_alpine.jl containing the declaration of the JuMP model
2. optimizers.jl with the settings of each solver

The compressed file contains a brief README of how to use this code to reproduce the bug. Hope it helps bug181.zip

[harshangrjn]

@claud10cv One simple fix which converges to a global optimal solution (358.0631) is to turn off the presolve in Alpine, using the following setting:

    model = JuMP.Model(optimizer_with_attributes(Alpine.Optimizer, 
                    "nlp_solver" => get_ipopt(),
                    "mip_solver" => get_cplex(),
                    "minlp_solver" => get_juniper(),
                    "time_limit" => 3600,
                    "presolve_bt" => false))

[claud10cv]

Thank you, I will try that. Can you confirm that you can reproduce the issue with the code provided? If there is anything else on my end that I can do to help you narrow the search, please let me know

[harshangrjn]

Thanks @claud10cv! I am able to reproduce the issue, using both CPLEX and Gurobi as the underlying MILP solver. From a quick look, the issue is clearly in the presolve step where the bound tightening is performed. For example, the following settings for Alpine also seems to converge to global optimality:

model = JuMP.Model(optimizer_with_attributes(Alpine.Optimizer, 
                    "nlp_solver" => get_ipopt(),
                    "mip_solver" => get_cplex(),
                    "minlp_solver" => get_juniper(),
                    "time_limit" => 3600,
                    "presolve_bt" => true,
                    "presolve_bt_max_iter" => 5)
                    )

However, increasing the presolve_bt_max_iter from 5 to 7 is causing the convergence issue. Some variables are incorrectly getting bounded in this function.

[harshangrjn]

Though Alpine's issues are fixed here, the upper bounding incumbent found by Juniper is numerically incorrect. While the global optimum for this (min obj.) instance is 358.063127426 (which was verified in BARON), Juniper reports 358.0630085311286 as a local solution, which is numerically close but not a valid bound within Alpine's tolerance (1E-6). Hence Alpine terminates with the issue as titled here.