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

Strengthen linear lifting and some fixes on expression parsing #75

Closed jac0320 closed 6 years ago

jac0320 commented 6 years ago

This PR is meant to address a corner case in the expression parsing with some improvements schemes. As of this PR, POD supports parsing sin/cos terms but has not support in convexifying the these terms.

Function updates:

Tests updates:

---------------- OLD Comments -------------- This PR meant to address the expression sin((-x[1])+x[2]), where \hat{x}==-(x[1])+x[2] shoule be linearly lifted to create a nonlinear operation of sin(\hat{x}).

In this meanwhile, a new test instance is used for validation. Small fixes are made to store the parsed information (not fully utilized in the algorithm) correct. These fixes will not affect the algorithm.

Also cleaned some the unused test instance. Some of them are unable to be used with the support of open-source solvers.

This PR branch off #74.

codecov[bot] commented 6 years ago

Codecov Report

Merging #75 into delta-algorithm will increase coverage by 9.45%. The diff coverage is 100%.

Impacted file tree graph

@@                 Coverage Diff                 @@
##           delta-algorithm      #75      +/-   ##
===================================================
+ Coverage             79.5%   88.96%   +9.45%     
===================================================
  Files                   28       27       -1     
  Lines                 5988     5528     -460     
===================================================
+ Hits                  4761     4918     +157     
+ Misses                1227      610     -617
Impacted Files Coverage Δ
test/examples/circle.jl 100% <ø> (+58.33%) :arrow_up:
src/operators.jl 93.94% <100%> (+4.22%) :arrow_up:
test/solver.jl 100% <100%> (ø) :arrow_up:
test/examples/convex.jl 100% <100%> (+100%) :arrow_up:
test/examples/exprstest.jl 38.92% <100%> (+30.25%) :arrow_up:
src/nlexpr.jl 72.05% <100%> (+0.67%) :arrow_up:
test/algorithm.jl 100% <100%> (ø) :arrow_up:
test/expression.jl 100% <100%> (ø) :arrow_up:
src/utility.jl 80% <0%> (+1.53%) :arrow_up:
... and 3 more

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 576c583...f807519. Read the comment docs.

harshangrjn commented 6 years ago

Why is this PR supporting trigonometric functions? Or is this just an example? I assume POD throws an error now if it scans a trigonometric function in the problem as we don't have valid relaxations built-in yet.

jac0320 commented 6 years ago

Operator supports for sin/cos is there. But, no relaxation scheme is specified for that as of now. So, POD will give you an error when it realizes the bounding model cannot be constructed except all nonlinear terms are convexified.

kaarthiksundar commented 6 years ago

Can you add one more feature to this PR? Here is what I need

Include a solver option called is_convex::Bool (default set to false).

If is_convex is true - then do to the following

  1. Allow for BT iff bound tightening option is set to true and then do one local solve to get the optimal solution.
  2. If BT is set to false then just do one local solve to get the optimal solution.

In this way our solver can handle convex problems if the user can let us know the problem is convex.