Opened 6 years ago

Last modified 6 years ago

#20296 closed enhancement

MixedIntegerLinearProgram: New backend using InteractiveLPProblem — at Version 2

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.2
Component: numerical Keywords: lp
Cc: dimpase, novoselt, ncohen, vdelecroix, chapoton Merged in:
Authors: Matthias Koeppe Reviewers:
Report Upstream: N/A Work issues:
Branch: u/mkoeppe/mixedintegerlinearprogram__new_backend_using_interactivelpproblem (Commits, GitHub, GitLab) Commit: 08d454882ce0a95b13f7d25c659c5cdde3b57090
Dependencies: Stopgaps:

Status badges

Description (last modified by mkoeppe)

If one has to solve a small LP with irrational (say, AA) data (and needs access to the exact solution), the only available tool is the didactical implementation of the simplex method in InteractiveLPProblem (but see #18735). This ticket implements a MixedIntegerLinearProgram backend using InteractiveLPProblem.

Example:

            sage: poly = polytopes.dodecahedron(base_ring=AA)
            sage: lp = poly.to_linear_program(solver='InteractiveLP')
            sage: b = lp.get_backend()
            sage: b.set_objective([1, 1, 1])
            sage: lp.solve()
            2.291796067500631?

(This example uses backend functions because of #20301 .)

Change History (2)

comment:1 Changed 6 years ago by mkoeppe

  • Branch set to u/mkoeppe/mixedintegerlinearprogram__new_backend_using_interactivelpproblem

comment:2 Changed 6 years ago by mkoeppe

  • Authors set to Matthias Koeppe
  • Cc dimpase novoselt ncohen vdelecroix chapoton added
  • Commit set to 08d454882ce0a95b13f7d25c659c5cdde3b57090
  • Description modified (diff)
  • Status changed from new to needs_review

Needs review.

Some remarks:

  • I'm using some _internals of InteractiveLPProblem (_constraint_types, _variable_types, _problem_type, _is_negative) because some accessor methods are missing. Should I be adding them?
  • There's should be a way to choose the base ring for the solver (right now I'm using AA -- but ultimately I'd like to use an embedded number field), but I'm not sure about the interface... perhaps MixedIntegerLinearProgram(solver=('InteractiveLP', AA)) or MixedIntegerLinearProgram(solver='InteractiveLP', base_ring=AA

New commits:

c39dd7dFix typo in documentation
4596534New MIP backend: InteractiveLPBackend
78039beFix doctests (which never run)
08d4548Fix typo in docstring
Note: See TracTickets for help on using tickets.