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:  sage6.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: 
Description (last modified by )
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
 Branch set to public/19090
comment:2 Changed 6 years ago by
 Cc ncohen added
comment:3 Changed 6 years ago by
 Commit set to 964bbbb14768c1ef7632b9321ad03170f8d11eea
comment:4 followup: ↓ 5 Changed 6 years ago by
 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
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
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
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
 Commit changed from 964bbbb14768c1ef7632b9321ad03170f8d11eea to c35433d9121996accada9a9cbc44635df48789cb
comment:9 Changed 6 years ago by
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
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
comment:11 Changed 6 years ago by
 Commit changed from c35433d9121996accada9a9cbc44635df48789cb to 305f29d78bf0d8b6f9314139829a46f5c2e1a97b
Branch pushed to git repo; I updated commit sha1. New commits:
305f29d  trac #19090: implement reviewers suggestions

comment:12 Changed 6 years ago by
agreed.
comment:13 Changed 6 years ago by
 Commit changed from 305f29d78bf0d8b6f9314139829a46f5c2e1a97b to 1bba6cb5b9193752f4d7accbbde04f8602205bf2
Branch pushed to git repo; I updated commit sha1. New commits:
1bba6cb  trac #19090: Fix doc (links + latex formatting)

comment:14 Changed 6 years ago by
 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
 Commit changed from 1bba6cb5b9193752f4d7accbbde04f8602205bf2 to 8c38aa709360a430fbbb53e66fde96463f408a20
Branch pushed to git repo; I updated commit sha1. New commits:
8c38aa7  trac #19090: unify documentation

comment:16 Changed 6 years ago by
Good to go?
Nathann
comment:17 Changed 6 years ago by
 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
 Status changed from needs_review to positive_review
Okayyyyyyyyyy then!
comment:19 Changed 6 years ago by
 Branch changed from public/19090 to 8c38aa709360a430fbbb53e66fde96463f408a20
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #19090: enable access to bestobjval and mipgap with cplex