implement constructing the dual of a linear program

[dimpase]

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.

CC: @nathanncohen @ppurka

Component: linear programming

Author: Dima Pasechnik

Reviewer: Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/13141

[novoselt]

comment:1

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.

[dimpase]

comment:2

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.

[novoselt]

comment:3

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

[mkoeppe]

comment:8

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"

[dimpase]

comment:9

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

[videlec]

comment:10

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

[dimpase]

comment:11

Replying to @videlec:

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 :-)

[dimpase]

Author: Dima Pasechnik

[dimpase]

Reviewer: Matthias Koeppe