Opened 6 years ago

Closed 6 years ago

#19090 closed enhancement (fixed)

MIP backend: return MIP relative gap

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-6.9
Component: linear programming Keywords:
Cc: ncohen Merged in:
Authors: David Coudert Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 8c38aa7 (Commits, GitHub, GitLab) Commit: 8c38aa709360a430fbbb53e66fde96463f408a20
Dependencies: Stopgaps:

Status badges

Description (last modified by dcoudert)

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).

Change History (19)

comment:1 Changed 6 years ago by dcoudert

  • Branch set to public/19090

comment:2 Changed 6 years ago by ncohen

  • Cc ncohen added

comment:3 Changed 6 years ago by git

  • Commit set to 964bbbb14768c1ef7632b9321ad03170f8d11eea

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

964bbbbtrac #19090: enable access to bestobjval and mipgap with cplex

comment:4 follow-up: Changed 6 years ago by dcoudert

  • Status changed from new to needs_review

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.

comment:5 in reply to: ↑ 4 Changed 6 years ago by ncohen

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

comment:6 Changed 6 years ago by dcoudert

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.

comment:7 Changed 6 years ago by ncohen

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

comment:8 Changed 6 years ago by git

  • Commit changed from 964bbbb14768c1ef7632b9321ad03170f8d11eea to c35433d9121996accada9a9cbc44635df48789cb

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

808e793trac #19090: Merged with 6.9.beta4
6d2bb32trac #19090: Callback function in GLPK
5fd0166trac #19090: enable access to bestobjval and mipgap with GLPK
c35433dtrac #19090: add methods to mip.pyx

comment:9 Changed 6 years ago by dcoudert

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

comment:10 Changed 6 years ago by ncohen

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

Last edited 6 years ago by ncohen (previous) (diff)

comment:11 Changed 6 years ago by git

  • Commit changed from c35433d9121996accada9a9cbc44635df48789cb to 305f29d78bf0d8b6f9314139829a46f5c2e1a97b

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

305f29dtrac #19090: implement reviewers suggestions

comment:12 Changed 6 years ago by dcoudert

agreed.

comment:13 Changed 6 years ago by git

  • Commit changed from 305f29d78bf0d8b6f9314139829a46f5c2e1a97b to 1bba6cb5b9193752f4d7accbbde04f8602205bf2

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

1bba6cbtrac #19090: Fix doc (links + latex formatting)

comment:14 Changed 6 years ago by ncohen

  • Reviewers set to Nathann Cohen

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

comment:15 Changed 6 years ago by git

  • Commit changed from 1bba6cb5b9193752f4d7accbbde04f8602205bf2 to 8c38aa709360a430fbbb53e66fde96463f408a20

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

8c38aa7trac #19090: unify documentation

comment:16 Changed 6 years ago by ncohen

Good to go?

Nathann

comment:17 Changed 6 years ago by dcoudert

  • Description modified (diff)
  • Summary changed from cplex backend: return MIP relative gap to MIP backend: return MIP relative gap

For me yes. Thanks, David.

comment:18 Changed 6 years ago by ncohen

  • Status changed from needs_review to positive_review

Okayyyyyyyyyy then!

comment:19 Changed 6 years ago by vbraun

  • Branch changed from public/19090 to 8c38aa709360a430fbbb53e66fde96463f408a20
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.