search

lanl-ansi / Alpine.jl

A Julia/JuMP-based Global Optimization Solver for Non-convex Programs
https://lanl-ansi.github.io/Alpine.jl/latest/
Other
244 stars 39 forks source link

Relative gap evaluation #103

Closed krishpat closed 4 years ago

krishpat commented 5 years ago

Consider this NLP: 

m = Model(solver=AlpineSolver(nlp_solver = IpoptSolver(print_level=0), mip_solver = CplexSolver(CPX_PARAM_SCRIND=0)))
@variable(m, -1 <= x[1:2] <= 1)
@NLobjective(m, Min, 0.26*(x[1]^2 + x[2]^2) - 0.48*x[1]*x[2])
solve(m)

Here is Alpine's log of the output : 

 | NLP           | MIP           || Objective     | Bound         | GAP (%)       | CLOCK         | | Iter   
 | 0.0           | -0.0539       || 0.0           | -0.0539       | LARGE         | 0.36s         | | 1
 | 0.0           | -0.0135       || 0.0           | -0.0135       | LARGE         | 0.4s          | | 2
 | 0.0           | -0.0041       || 0.0           | -0.0041       | LARGE         | 0.44s         | | 3
 | 0.0045        | -0.0041       || 0.0           | -0.0041       | LARGE         | 0.51s         | | 4
 | 0.0045        | -0.0034       || 0.0           | -0.0034       | LARGE         | 0.58s         | | 5
 | 0.0           | -0.001        || 0.0           | -0.001        | LARGE         | 0.66s         | | 6
 | 0.0011        | -0.001        || 0.0           | -0.001        | LARGE         | 0.74s         | | 7
 | 0.0014        | -0.001        || 0.0           | -0.001        | LARGE         | 0.83s         | | 8
 | 0.0018        | -0.001        || 0.0           | -0.001        | LARGE         | 0.92s         | | 9
 | 0.002         | -0.001        || 0.0           | -0.001        | LARGE         | 1.03s         | | 10
 | 0.0021        | -0.001        || 0.0           | -0.001        | LARGE         | 1.16s         | | 11
 | 0.0021        | -0.001        || 0.0           | -0.001        | LARGE         | 1.3s          | | 12
 | 0.0021        | -0.001        || 0.0           | -0.001        | LARGE         | 1.49s         | | 13
 | 0.0021        | -0.001        || 0.0           | -0.001        | LARGE         | 1.67s         | | 14
 | 0.0021        | -0.001        || 0.0           | -0.001        | LARGE         | 1.87s         | | 15
 | 0.0022        | -0.0008       || 0.0           | -0.0008       | LARGE         | 2.14s         | | 16
 | 0.0           | -0.0003       || 0.0           | -0.0003       | LARGE         | 2.43s         | | 17
 | 0.0003        | -0.0003       || 0.0           | -0.0003       | LARGE         | 2.84s         | | 18
 | 0.0003        | -0.0002       || 0.0           | -0.0002       | LARGE         | 3.27s         | | 19
 | 0.0           | -0.0001       || 0.0           | -0.0001       | LARGE         | 3.69s         | | 20
 | 0.0001        | -0.0001       || 0.0           | -0.0001       | LARGE         | 4.25s         | | 21
 | 0.0001        | -0.0001       || 0.0           | -0.0001       | LARGE         | 4.88s         | | 22
 | 0.0           | -0.0          || 0.0           | -0.0          | 0.0           | 5.53s         | | finish
  1. Why does Alpine go upto 23 Iterations when Iter 6 was global minimum within the optimality tolerance?
  2. Why are the gaps displayed as LARGE when the gaps are actually small? Is it because the upper bound (0) value is in the denominator of the gap?
  3. Wonder how did Alpine converge when both LB and UB reached 0 in the last iteration based on the optimality gap criterion.

There may be some issue in the way relative gaps are evaluated.

harshangrjn commented 5 years ago

@krishpat Firstly, your objective is convex and you wouldn't need Alpine for this. :) That said, we are currently working on including convexity detection for objectives of this type.

Regarding your issues, currently the way we are evaluating the relative gap when upper bound is 0 is not fully right, which will be fixed soon.

harshangrjn commented 4 years ago

Updated output: 

====================================================================================================
| Iter   | Incumbent       | Best Incumbent      | Lower Bound        | Gap (%)         | Time      
| 1      | 0.0             | 0.0                 | -0.0539            | 5.39029         | 0.55s            
| 2      | 0.0             | 0.0                 | -0.0135            | 1.34765         | 0.61s            
| 3      | 0.0             | 0.0                 | -0.0041            | 0.41449         | 0.67s            
| 4      | 0.0045          | 0.0                 | -0.0041            | 0.41449         | 0.79s            
| 5      | 0.0045          | 0.0                 | -0.0034            | 0.33699         | 0.89s            
| 6      | 0.0             | 0.0                 | -0.001             | 0.1037          | 0.99s            
| 7      | 0.0011          | 0.0                 | -0.001             | 0.1037          | 1.08s            
| 8      | 0.0014          | 0.0                 | -0.001             | 0.1037          | 1.23s            
| 9      | 0.0018          | 0.0                 | -0.001             | 0.1037          | 1.36s            
| 10     | 0.002           | 0.0                 | -0.001             | 0.1037          | 1.5s             
| 11     | 0.0021          | 0.0                 | -0.001             | 0.1037          | 1.64s            
| 12     | 0.0021          | 0.0                 | -0.001             | 0.1037          | 1.86s            
| 13     | 0.0021          | 0.0                 | -0.001             | 0.1037          | 2.04s            
| 14     | 0.0021          | 0.0                 | -0.001             | 0.1037          | 2.26s            
| 15     | 0.0021          | 0.0                 | -0.001             | 0.1037          | 2.49s            
| 16     | 0.0022          | 0.0                 | -0.001             | 0.1037          | 2.82s            
| 17     | 0.0022          | 0.0                 | -0.0008            | 0.08432         | 3.37s            
| 18     | 0.0             | 0.0                 | -0.0003            | 0.026           | 4.0s             
| 19     | 0.0003          | 0.0                 | -0.0003            | 0.026           | 4.5s             
| 20     | 0.0003          | 0.0                 | -0.0002            | 0.02116         | 5.14s            
| finish | 0.0             | 0.0                 | -0.0001            | 0.00657         | 5.77s            
====================================================================================================