Opened 10 years ago

Closed 6 years ago

# implement constructing the dual of a linear program

Reported by: Owned by: dimpase ncohen major sage-duplicate/invalid/wontfix linear programming ncohen, ppurka Dima Pasechnik Matthias Koeppe N/A

### 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.

### comment:1 follow-up: ↓ 2 Changed 10 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 10 years ago by dimpase

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 10 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 9 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:5 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:6 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:7 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:8 Changed 6 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 6 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:11 in reply to: ↑ 10 Changed 6 years ago by dimpase

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

### comment:12 Changed 6 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 6 years ago by vbraun

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