MIP backend: return MIP relative gap #19090

dcoudert · 2015-08-26T08:22:57Z

Currently, when a timelimit is pass to a MIP solver, we can access the best integer solution found. However, we cannot access the best known bound value and the optimality gap. This patch enable access to these values (implemented for GLPK and CPLEX).

CC: @nathanncohen

Component: linear programming

Author: David Coudert

Branch/Commit: 8c38aa7

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/19090

The text was updated successfully, but these errors were encountered:

dcoudert · 2015-08-26T08:23:34Z

Branch: public/19090

sagetrac-git · 2015-08-26T09:55:27Z

Branch pushed to git repo; I updated commit sha1. New commits:

`964bbbb`	`trac #19090: enable access to bestobjval and mipgap with cplex`

sagetrac-git · 2015-08-26T09:55:27Z

Commit: 964bbbb

dcoudert · 2015-08-26T10:13:46Z

comment:4

Hello,

this is the first draft. I can now do the following:

sage: G = graphs.MycielskiGraph(6)
sage: from sage.numerical.mip import MixedIntegerLinearProgram
sage: p = MixedIntegerLinearProgram(maximization=False, solver="Cplex")
sage: x = p.new_variable(binary=True, nonnegative=True)
sage: obj = p.new_variable(integer=True, nonnegative=True)
sage: for u in G.vertices():
    p.add_constraint( p.sum( x[u,i] for i in range(G.order()) ) == 1 )
....:     
sage: for i in range(G.order()):
    p.add_constraint( p.sum( x[u,i] for u in G.vertices() ) == 1 )
....:     
sage: for u,v in G.edges(labels=None):
    p.add_constraint( p.sum( i*(x[u,i] - x[v,i]) for i in range(G.order()) ) <= obj['obj'] )
    p.add_constraint( p.sum( i*(x[v,i] - x[u,i]) for i in range(G.order()) ) <= obj['obj'] )
....:     
sage: p.set_objective(obj['obj'])
sage: p.solver_parameter("timelimit", 5)
sage: p.solve(log=1)
Tried aggregator 1 time.
Reduced MIP has 566 rows, 2210 columns, and 48314 nonzeros.
Reduced MIP has 2209 binaries, 1 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.01 sec. (15.25 ticks)
Found incumbent of value 1081.000000 after 0.05 sec. (41.34 ticks)
Probing time = 0.01 sec. (4.65 ticks)
Tried aggregator 1 time.
Reduced MIP has 566 rows, 2210 columns, and 48314 nonzeros.
Reduced MIP has 2209 binaries, 1 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (17.23 ticks)
Probing time = 0.01 sec. (4.65 ticks)
Clique table members: 94.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 0.03 sec. (26.66 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                         1081.0000        0.0000           100.00%
*     0+    0                         1068.0000        0.0000           100.00%
*     0+    0                         1055.0000        0.0000           100.00%
*     0+    0                         1042.0000        0.0000           100.00%
*     0+    0                         1029.0000        0.0000           100.00%
*     0+    0                         1016.0000        0.0000           100.00%
      0     0        0.0000   139     1016.0000        0.0000      326  100.00%
*     0+    0                           44.0000        0.0000           100.00%
*     0+    0                           32.0000        0.0000           100.00%
      0     0        0.0000   190       32.0000     Cuts: 210     1308  100.00%
      0     0        1.0000   129       32.0000     Cuts: 124     3312   96.87%
*     0+    0                           31.0000        1.0000            96.77%
      0     0        1.0000   213       31.0000     Cuts: 241     3976   96.77%
*     0+    0                           30.0000        1.0000            96.67%
*     0+    0                           29.0000        1.0000            96.55%

Root node processing (before b&c):
  Real time             =    5.01 sec. (4033.26 ticks)
Parallel b&c, 4 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    5.01 sec. (4033.26 ticks)
29.0
sage: bb = p.get_backend()
sage: bb.get_objective_value()
29.0
sage: bb.get_best_objective_value()
1.0
sage: bb.get_relative_objective_gap()
0.965517241375981

However, it's working only with cplex. For GLPK, I have to understand how to access

int glp_ios_best_node(glp_tree *tree);
/* find active subproblem with best local bound */

double glp_ios_mip_gap(glp_tree *tree);
/* compute relative MIP gap */

Also, I have enabled access to these methods only through the backends. I don't know if I should also add these methods to mip.pxd/pyx.

David.

nathanncohen · 2015-08-26T10:49:47Z

comment:5

this is the first draft. I can now do the following:

Cool!

However, it's working only with cplex. For GLPK, I have to understand how to access
int glp_ios_best_node(glp_tree *tree);
/* find active subproblem with best local bound */

double glp_ios_mip_gap(glp_tree *tree);
/* compute relative MIP gap */

Well, at least it seems possible.

Also, I have enabled access to these methods only through the backends. I don't know if I should also add these methods to mip.pxd/pyx.

If you figure out how to make it work for GPLK, then I'd say yes. I expect that we will find such a feature in all solvers, eventually.

Nathann

dcoudert · 2015-08-26T13:10:58Z

comment:6

I did multiple trials to use these methods with GLPK, but failed :(
I don't know how to access the tree. It should be inside glp_prob and so self.lp.tree should be of type glp_tree, but I'm not able to make it work.

nathanncohen · 2015-08-31T11:35:14Z

comment:7

Hellooooooo David !

At u/ncohen/19090, you will find a commit that lets you compute the relatve mip gap in GLPK. From there, more information cab easily be gathered, read and returned.

Even though it seems that this information is gathered at every node, and not only once at the end of the exploring. The good news is that:

It is probably cheap.
We will see the callback function if we run a profiler, as it cannot be inlined.

Nathann

sagetrac-git · 2015-08-31T12:21:01Z

Changed commit from 964bbbb to c35433d

sagetrac-git · 2015-08-31T12:21:01Z

Branch pushed to git repo; I updated commit sha1. New commits:

`808e793`	`trac #19090: Merged with 6.9.beta4`
`6d2bb32`	`trac #19090: Callback function in GLPK`
`5fd0166`	`trac #19090: enable access to bestobjval and mipgap with GLPK`
`c35433d`	`trac #19090: add methods to mip.pyx`

dcoudert · 2015-08-31T12:23:25Z

comment:9

Thanks Nathann.
I have completed your work with GLPK and added methods to enable access to these methods directly from the mip.
Best,
David.

nathanncohen · 2015-08-31T12:46:52Z

comment:10

Helloooooo David,

I find that the name of get_best_objective_value clashes heavily with what the method is supposed to do. When I read get_best_objective_value, all I can think of is that it returns the cost of the best solution found so far.

What would you think of something like best_known_objective_bound instead ?

Similarly, the description of the function is sometimes confusing. I am not sure that I understand what "the minimum objective function of all unexplored nodes" means.

What about something like that:

This method returns the current best upper (resp. lower) bound on the optimal value of the objective function in a maximization (resp. minimization) problem. It is equal to the output of :meth:`get_objective_value` if the MILP found an optimal solution, but it can differ if it was interrupted manually or after a time limit (cf :meth:`solver_parameter`).

Just a proposition of course, we can modify whatever you don't like in this text.

Nathann

sagetrac-git · 2015-08-31T14:02:46Z

Branch pushed to git repo; I updated commit sha1. New commits:

`305f29d`	`trac #19090: implement reviewers suggestions`

sagetrac-git · 2015-08-31T14:02:46Z

Changed commit from c35433d to 305f29d

dcoudert · 2015-08-31T14:03:17Z

comment:12

agreed.

sagetrac-git · 2015-08-31T16:36:23Z

Branch pushed to git repo; I updated commit sha1. New commits:

`1bba6cb`	`trac #19090: Fix doc (links + latex formatting)`

sagetrac-git · 2015-08-31T16:36:23Z

Changed commit from 305f29d to 1bba6cb

nathanncohen · 2015-08-31T16:37:02Z

comment:14

Hello again,

I fixed the doc a bit and added a commit on this public branch. If you agree with it, then let's get it merged.

Thanks for this ticket,

Nathann

nathanncohen · 2015-08-31T16:37:02Z

Reviewer: Nathann Cohen

sagetrac-git · 2015-09-01T08:52:45Z

Branch pushed to git repo; I updated commit sha1. New commits:

`8c38aa7`	`trac #19090: unify documentation`

sagetrac-git · 2015-09-01T08:52:45Z

Changed commit from 1bba6cb to 8c38aa7

nathanncohen · 2015-09-01T09:15:23Z

comment:16

Good to go?

Nathann

dcoudert · 2015-09-01T09:20:14Z

comment:17

For me yes.
Thanks,
David.

nathanncohen · 2015-09-01T09:27:29Z

comment:18

Okayyyyyyyyyy then!

vbraun · 2015-09-02T17:25:25Z

Changed branch from public/19090 to 8c38aa7

dcoudert added this to the sage-6.9 milestone Aug 26, 2015

dcoudert added c: linear programming labels Aug 26, 2015

dcoudert added the s: needs review label Aug 26, 2015

This comment has been minimized.

Sign in to view

dcoudert changed the title ~~cplex backend: return MIP relative gap~~ MIP backend: return MIP relative gap Sep 1, 2015

nathanncohen mannequin added s: positive review and removed s: needs review labels Sep 1, 2015

vbraun removed the s: positive review label Sep 2, 2015

vbraun closed this as completed in 7d7941d Sep 2, 2015

nathanncohen mannequin mentioned this issue Sep 3, 2015

Check CPLEXBackend.solver_parameter #19117

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

MIP backend: return MIP relative gap #19090

MIP backend: return MIP relative gap #19090

dcoudert commented Aug 26, 2015

dcoudert commented Aug 26, 2015

sagetrac-git mannequin commented Aug 26, 2015

sagetrac-git mannequin commented Aug 26, 2015

dcoudert commented Aug 26, 2015

nathanncohen mannequin commented Aug 26, 2015

dcoudert commented Aug 26, 2015

nathanncohen mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

dcoudert commented Aug 31, 2015

nathanncohen mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

dcoudert commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

nathanncohen mannequin commented Aug 31, 2015

nathanncohen mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Sep 1, 2015

sagetrac-git mannequin commented Sep 1, 2015

nathanncohen mannequin commented Sep 1, 2015

dcoudert commented Sep 1, 2015

This comment has been minimized.

nathanncohen mannequin commented Sep 1, 2015

vbraun commented Sep 2, 2015

MIP backend: return MIP relative gap #19090

MIP backend: return MIP relative gap #19090

Comments

dcoudert commented Aug 26, 2015

dcoudert commented Aug 26, 2015

sagetrac-git mannequin commented Aug 26, 2015

sagetrac-git mannequin commented Aug 26, 2015

dcoudert commented Aug 26, 2015

nathanncohen mannequin commented Aug 26, 2015

dcoudert commented Aug 26, 2015

nathanncohen mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

dcoudert commented Aug 31, 2015

nathanncohen mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

dcoudert commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Aug 31, 2015

nathanncohen mannequin commented Aug 31, 2015

nathanncohen mannequin commented Aug 31, 2015

sagetrac-git mannequin commented Sep 1, 2015

sagetrac-git mannequin commented Sep 1, 2015

nathanncohen mannequin commented Sep 1, 2015

dcoudert commented Sep 1, 2015

This comment has been minimized.

nathanncohen mannequin commented Sep 1, 2015

vbraun commented Sep 2, 2015