#19090: cplex backend: return MIP relative gap
-------------------------------------+-------------------------------------
Reporter: dcoudert | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: linear | Resolution:
programming | Merged in:
Keywords: | Reviewers:
Authors: David Coudert | Work issues:
Report Upstream: N/A | Commit:
Branch: public/19090 | 964bbbb14768c1ef7632b9321ad03170f8d11eea
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by dcoudert):
* status: new => needs_review
Comment:
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.
--
Ticket URL: <http://trac.sagemath.org/ticket/19090#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
