Opened 6 years ago

Last modified 3 days ago

#18735 needs_work enhancement

MixedIntegerLinearProgram: Reconstruct exact rational basic solution — at Version 3

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-9.5
Component: numerical Keywords: lp
Cc: yzh, ncohen, dimpase Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #18685, #18688 Stopgaps:

Status badges

Description (last modified by dimpase)

Sometimes one can use a fast numerical LP solver to solve a problem to "optimality", then reconstruct the primal and dual solution in rational arithmetic (or over whatever base_ring was used...) and in this way prove that this basis is indeed optimal. MixedIntegerLinearProgram should support this mode of operation.

#18685 provides the necessary basis-status functions (for the GLPK backend). #18688 provides a solver-independent interface to these functions.

Change History (3)

comment:1 Changed 6 years ago by mkoeppe

  • Cc dimpase added

comment:2 Changed 6 years ago by dimpase

Is ppl (pplLP backend, which works with exact arithmetic) too slow for you?

comment:3 Changed 6 years ago by dimpase

  • Description modified (diff)

On the other hand, a solver-independent way to get an optimal dual solution is very much welcome, as this is lacking currently, and often needed.

Note: See TracTickets for help on using tickets.