Solution check: discontinuous objective function¶

Description: Pathological examples to illustrate MP solution checker and settings

Tags: MP library, solution check, non-continuous objective, strict comparison

Notebook author: Gleb Belov <gleb@ampl.com>

# Install dependencies
%pip install -q amplpy pandas

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["highs"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Non-continuous objectives¶

Current notebook continues discussing solution checking (started in the documentation.)

The goal of the below example is to illustrate an issue with handling reformulated expressions.

To introduce a (perceived) error into a solution, let’s tamper with the model reformulation (as it’s hard to introduce controllable numerical accuracy error in a small example.) We use a non-continuous function in the objective and trick the solver into approaching the jump point from a specific side.

%%ampl_eval         ## Use %%ampl_eval to parse AMPL code
reset;
var x >=0, <= 1;
var y >=0, <= 1;
var b: binary;

s.t. ConImpl:
    b ==> 2*x + 3*y <= 5;

minimize TotalIf:
    if 2*x+3*y>5 then 2*x+3*y-3*b-25 else 2*x+3*y-3*b;

Running with default settings¶

Running this example with default settings does not trigger any warnings:

%%ampl_eval
option solver highs;
solve;

HiGHS 1.5.3: HiGHS 1.5.3: optimal solution; objective -3
0 simplex iterations
0 branching nodes
 

Making the jump steeper¶

To stuff it up, note that currently no MP solver handles the if expression natively; the expression is reformulated into auxiliary variables and constraints. One auxiliary constraint is

2*x+3*y > 5  ==>  obj_var_ == 2*x+3*y-3*b-25;

Computing with finite precision, we need to specify the meaning of the strict comparison operator >. Expression 2*x+3*y > 5 is internally reformulated as 2*x+3*y >= 5+cmp:eps, where cmp:eps is a driver option. Let’s set it to 0.

ampl.option["highs_options"] = "cvt:cmp:eps=0"
ampl.solve()

HiGHS 1.5.3:   cvt:mip:eps = 0
HiGHS 1.5.3: optimal solution; objective -23
2 simplex iterations
1 branching nodes
 
------------ WARNINGS ------------
WARNING:  "Solution Check (Idealistic)"
     [ sol:chk:feastol=1e-06, :feastolrel=1e-06, :inttol=1e-05,
       solution_round='', solution_precision='' ]
Objective value violations:
  - 1 objective value(s) violated,
        up to 2E+01 (abs), up to 1E+01 (rel)
Idealistic check is an indicator only, see documentation.
 

Solution display¶

To see what happened, let’s print the solution:

%%ampl_eval
option display_precision 17;
display x,y,b, 2*x+3*y, TotalIf, if 2*x+3*y>5 then 1;

x = 1
y = 1
b = 1
2*x + 3*y = 5
TotalIf = 2
 if 2*x + 3*y > 5 then 1 = 0

While the solver “thinks” that 2*x+3*y > 5 (because we set cmp:eps=0), AMPL is unbiased.

A remedy¶

To access the solver’s objective value in AMPL, whenever non-continuous expressions are used, employ an extra variable:

%%ampl_eval         ## Use %%ampl_eval to parse AMPL code
reset;
var x >=0, <= 1;
var y >=0, <= 1;
var b: binary;
var obj_val;

s.t. ConImpl:
    b ==> 2*x + 3*y <= 5;

s.t. TotalIf_con:
    obj_val == if 2*x+3*y>5 then 2*x+3*y-3*b-25 else 2*x+3*y-3*b;
    
minimize TotalIf_var: obj_val;

%%ampl_eval
option highs_options 'cmp:eps=0';
solve; display _obj;

HiGHS 1.5.3:   cvt:mip:eps = 0
HiGHS 1.5.3: optimal solution; objective -23
2 simplex iterations
1 branching nodes
 
_obj [*] :=
1  -23
;

Uncover the issue¶

While no warnings are reported, the issue is still there. But now it is in the new constraint. The constraints are not checked in the “idealistic” check mode by default. To turn on all checks, set chk:mode=1023:

%%ampl_eval
option highs_options 'cmp:eps=0 chk:mode=1023';
solve; display _obj;

HiGHS 1.5.3:   cvt:mip:eps = 0
  sol:chk:mode = 1023
HiGHS 1.5.3: optimal solution; objective -23
0 simplex iterations
0 branching nodes
 
------------ WARNINGS ------------
WARNING:  "Solution Check (Idealistic)"
     [ sol:chk:feastol=1e-06, :feastolrel=1e-06, :inttol=1e-05,
       solution_round='', solution_precision='' ]
Algebraic expression violations:
  - 1 original expression(s) of type ':ifthen',
        up to 2E+01 (abs), up to 1E+01 (rel)
  - 1 original expression(s) of type ':linrange',
        up to 2E+01 (abs)
Idealistic check is an indicator only, see documentation.
 
_obj [*] :=
1  -23
;

Are we doomed?¶

As no “realistic” warnings are reported, we can trust the solution up to the tolerances used.

Conclusion¶

The “idealistic” checking mode recomputes expressions from scratch, emulating what AMPL does when checking objective value or constraint slacks. If you need the solver’s value of a discontinuous objective function (trust it if no “realistic” warnings appear), use an explicit objective variable. You might adjust reformulation tolerances to reduce the ambiguity of a discontinuity.

Note that strict comparisons can be introduced behind the scenes, for example we might use

if 2*x+3*y<=5 then 2*x+3*y-3*b else 2*x+3*y-3*b-25;

Simple sudoku solver using logical constraints (with GUI)

Solving a nonogram puzzle