Opened 6 years ago

Last modified 3 months ago

#18735 needs_review enhancement

MixedIntegerLinearProgram: Reconstruct exact rational basic solution — at Version 4

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

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.

This would be particularly interesting in conjunction with #18764. (But see #18765 for a different approach.)

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

Change History (4)

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.

comment:4 Changed 6 years ago by mkoeppe

  • Description modified (diff)
Note: See TracTickets for help on using tickets.