Opened 7 years ago

Closed 3 years ago

#13141 closed enhancement (fixed)

implement constructing the dual of a linear program

Reported by: dimpase Owned by: ncohen
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: linear programming Keywords:
Cc: ncohen, ppurka Merged in:
Authors: Dima Pasechnik Reviewers: Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

There is currently no support for constructing the classic LP dual of a linear program (LP). It would be very useful for various reasons, last but not the least constructing certificates of optimality and of infeasibility of an LP.

Change History (13)

comment:1 follow-up: Changed 7 years ago by novoselt

I've actually have a module that does construct duals, but it is a "from scratch" implementation of linear programs and simplex method steps for educational reasons. It is not yet ready for inclusion in Sage, but I am likely to teach linear optimization this fall and plan to post it for review by the end of the term or earlier.

comment:2 in reply to: ↑ 1 Changed 7 years ago by dimpase

Replying to novoselt:

I've actually have a module that does construct duals, but it is a "from scratch" implementation of linear programs and simplex method steps for educational reasons. It is not yet ready for inclusion in Sage, but I am likely to teach linear optimization this fall and plan to post it for review by the end of the term or earlier.

I hope it will be a solver backend rather than feature a yet another way to enter linear equations and inequalities into Sage.

IMHO we need to initiate a major cleanup of these, as PPL backend, MILP backends, CVXOPT, and perhaps other places I am not aware of or don't recall each have its own way of accomplishing this task. And this certainly sucks from the userland point of view.

comment:3 Changed 7 years ago by novoselt

It cannot be a solver back-end: the point is not to have another algorithm of solving LPs, but to allow students using simplex method step-by-step without worrying about arithmetic. I also made the output match the lecture notes which we were using, and input is done by matrices/vectors. The standard way of constructing linear programs in Sage is, IMHO, extremely confusing for beginners.

One of the first versions of the module was published here: http://www.sagenb.org/home/pub/3318/ most of the math is now screwed up, which is quite unfortunate and annoying, but it is still more or less clear what it does. Later versions also support "revised dictionaries" and plots for graphical solving in 2D, e.g. this exam solutions were generated by it via SageTeX: http://www.math.ualberta.ca/~novoseltsev/2011Fall373A1/final_solutions.pdf

comment:4 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 3 years ago by mkoeppe

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

I think this is a dup of #7290. And I think explicitly constructing dual LPs from a given LP is something that one wouldn't do with a solver. Rather set solver parameters that explicit request the primal or dual simplex method, when available. #7290, #18733, #18804 give access to dual information in various form. Explicitly dualizing is already available for the textbook implementation of the simplex method, InteractiveLPProblem.

That's why I'm marking this as "duplicate"

comment:9 Changed 3 years ago by dimpase

when I opened this I needed to construct Farkas certs of infeasibility, and that was (still is?) something that Sage could not do.

(I have had a collection of small LP's that only PPL could solve properly, without scaling problems).

comment:10 follow-up: Changed 3 years ago by vdelecroix

Please add your name to the author field (otherwise the patchbot will not check this ticket)

comment:11 in reply to: ↑ 10 Changed 3 years ago by dimpase

Replying to vdelecroix:

Please add your name to the author field (otherwise the patchbot will not check this ticket)

I better not, otherwise the patchbot might get confused by the absence of a branch on the ticket :-)

comment:12 Changed 3 years ago by dimpase

  • Authors set to Dima Pasechnik
  • Reviewers set to Matthias Koeppe
  • Status changed from needs_review to positive_review

comment:13 Changed 3 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.