Opened 4 years ago

Last modified 4 months ago

#22724 new enhancement

MixedIntegerLinearProgram backend using polymake (for LP over quadratic extensions)

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-9.4
Component: numerical Keywords: polymake, lp
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #22452 Stopgaps:

Status badges

Description (last modified by mkoeppe)

polymake has a simple implementation of the dual simplex method, which works with polymake's quadratic extensions.

It appears to be much faster than our InteractiveLPbackend. It is unknown (because no benchmarking has been done) how much of the speed differential is due to InteractiveLP latexing all intermediate tableaux.

We should make it available as a MixedIntegerLinearProgram backend. (Of course, there are no integer variables.)

This could be based directly on

  • #22452: Create a polymake pexpect interface

or use

  • #22683: backend_polymake for Polyhedron

See also: #22710: Meta-ticket: polymake

Change History (5)

comment:1 Changed 4 years ago by mkoeppe

  • Dependencies set to #22452
  • Description modified (diff)

comment:2 Changed 4 years ago by mkoeppe

  • Description modified (diff)

comment:3 Changed 14 months ago by mkoeppe

  • Milestone changed from sage-8.0 to sage-9.2

Moving some tickets to 9.2. This is not a promise that I will be working on them.

comment:4 Changed 10 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:5 Changed 4 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

Note: See TracTickets for help on using tickets.