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: ↓ 2 Changed 7 years ago by
comment:2 in reply to: ↑ 1 Changed 7 years ago by
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
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
- Milestone changed from sage-5.11 to sage-5.12
comment:5 Changed 5 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:6 Changed 5 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:7 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:8 Changed 3 years ago by
- 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
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: ↓ 11 Changed 3 years ago by
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
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
- Reviewers set to Matthias Koeppe
- Status changed from needs_review to positive_review
comment:13 Changed 3 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
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.