make LP return the number of variables #13148

dimpase · 2012-06-21T14:12:29Z

Currently there is no way to know how many variables an LP actually has, without parsing its constraints. However, this information is readily available from the backend. Hence the patch attached.

Apply attachment: trac_13148-number_of_variables_in_LP.patch to devel/sage

CC: @nathanncohen @ppurka

Component: linear programming

Author: Dima Pasechnik

Reviewer: Nathann Cohen

Merged: sage-5.2.beta0

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

nathanncohen · 2012-06-22T05:55:19Z

comment:2

-_-

Ahem... With Gurobi installed the doctests do not pass, because of their stupid way of storing double inequalities :

sage: p = MixedIntegerLinearProgram()
sage: p.add_constraint(p[0] - p[2], min = 1, max = 4)
sage: p.number_of_variables()
3
sage: p.show()
Maximization:
 
Constraints:
  R0: 4.0 <= x_0 - x_1 + RgR0 <= 4.0
Variables:
  x_0 is a continuous variable (min=0.0, max=+oo)
  x_1 is a continuous variable (min=0.0, max=+oo)
  RgR0 is a continuous variable (min=0.0, max=3.0)

Of course I expect that your code works with any other solver ^^;

Could you change the first constraint so that it is a "simple" inequality (with not both an upper and lower bound) ?

Your patch also needs some commit message. And I do not know if there is any rule about patches filenames ending with a .patch, but we will find out soon :-)

Sorry about this Gurobi ugliness :-p

Nathann

dimpase · 2012-06-22T08:11:36Z

comment:3

Replying to @nathanncohen:

-_-

Ahem... With Gurobi installed the doctests do not pass, because of their stupid way of storing double inequalities :

sage: p = MixedIntegerLinearProgram()
sage: p.add_constraint(p[0] - p[2], min = 1, max = 4)
sage: p.number_of_variables()
3
sage: p.show()
Maximization:
 
Constraints:
  R0: 4.0 <= x_0 - x_1 + RgR0 <= 4.0
Variables:
  x_0 is a continuous variable (min=0.0, max=+oo)
  x_1 is a continuous variable (min=0.0, max=+oo)
  RgR0 is a continuous variable (min=0.0, max=3.0)

as far as I am concerned this is an LP with 3 variables, not 2.
So my code is right :–)
(well, you don't have means to control that RgR0, so what?)
When you construct the usual dual of such an LP, you'll end up with
a different dual.

Of course I expect that your code works with any other solver ^^;

Could you change the first constraint so that it is a "simple" inequality (with not both an upper and lower bound) ?

hmm, I don't see what you mean here.

Your patch also needs some commit message. And I do not know if there is any rule about patches filenames ending with a .patch, but we will find out soon :-)

Sorry about this Gurobi ugliness :-p

Nathann

nathanncohen · 2012-06-22T08:50:14Z

comment:4

as far as I am concerned this is an LP with 3 variables, not 2.
So my code is right :–)

Yeah, but itbreaks doctests.

(well, you don't have means to control that RgR0, so what?)

None at all. When you add a as a constraint a linar function + two bounds (min and max) Gurobi automatically creates a newbounded variable and makes the constraint an equality.
That's stupid, boring, whatever you want, but this is still how it behaves.

When you construct the usual dual of such an LP, you'll end up with
a different dual.

Yeah. That's why I told you by email that you would be surpised by the behviour of some solvers on his respect.

hmm, I don't see what you mean here.

If you remove either the min or the max bound from your code Gurobi will not do that and break the doctest, that's all...

Nathann

dimpase · 2012-06-22T09:17:47Z

comment:5

Replying to @nathanncohen:

as far as I am concerned this is an LP with 3 variables, not 2.
So my code is right :–)

Yeah, but itbreaks doctests.

it only does so if you hack your Sage installation to make Gurobi the default
solver. Correct me if I'm wrong, but isn't the default LP solver GLPK?

(well, you don't have means to control that RgR0, so what?)

None at all. When you add a as a constraint a linar function + two bounds (min and max) Gurobi automatically creates a newbounded variable and makes the constraint an equality.
That's stupid, boring, whatever you want, but this is still how it behaves.

Ah, I see, thanks.

When you construct the usual dual of such an LP, you'll end up with
a different dual.

Yeah. That's why I told you by email that you would be surpised by the behviour of some solvers on his respect.

Well, I constructed LPs that CPLEX can solve by primal simplex, but not by the dual. LPs that CPLEX finds out to be infeasible, but for which it fails to give you an infeasibility certificate. I don't think they can surprise me any more :-)

Dima

nathanncohen · 2012-06-22T10:16:55Z

comment:6

it only does so if you hack your Sage installation to make Gurobi the default
solver. Correct me if I'm wrong, but isn't the default LP solver GLPK?

Well. No, Gurobi becomes the default solver as soon as you install it.

But that is not the problem Dima. I you remove this "min" or "max" in your file the doctest does not break anymore, what's the point of insisting to keep it ? What's the point ?

Well, I constructed LPs that CPLEX can solve by primal simplex, but not by the dual. LPs that CPLEX finds out to be infeasible, but for which it fails to give you an infeasibility certificate. I don't think they can surprise me any more :-)

Ahahaah... Scary, scary things ....

Nathann

dimpase · 2012-06-22T11:09:10Z

comment:7

Replying to @nathanncohen:

it only does so if you hack your Sage installation to make Gurobi the default
solver. Correct me if I'm wrong, but isn't the default LP solver GLPK?

Well. No, Gurobi becomes the default solver as soon as you install it.

Oh dear... And if I install, say, CPLEX? Will it take over? This is strange. Even web browsers don't behave like this :–) Anyway...

But that is not the problem Dima. I you remove this "min" or "max" in your file the doctest does not break anymore, what's the point of insisting to keep it ? What's the point ?

Cause this would not be what I'd call 100% doctest coverage. :–)
If someone else (or me, 6 months later :–)) would stumble upon this crap?

OK, I can specify the solver to use, then it will work.
By the way, how would I mark a test so that it would only be invoked if GUROBI is installed?
Is it # optional ??? ? And what would be ??? there?

nathanncohen · 2012-06-22T11:12:22Z

comment:8

Well. No, Gurobi becomes the default solver as soon as you install it.

Oh dear... And if I install, say, CPLEX? Will it take over? This is strange. Even web browsers don't behave like this :–) Anyway...

It would. You will find out how it behaves by looking at numerical/backends/generic_backend, bottom of the file.
This is made so that the best solver available will be used to solve.... graph problems :-P

Cause this would not be what I'd call 100% doctest coverage :–)
OK, I can specify the solver to use, then it will work.

And you woul prefer to specify manually the solver you want to use, in this case GLPK, and say that the other solvers will not be tested ? This would be 100% coverage ? Or add one doctest per solver ?

By the way, how would I mark a test so that it would only be invoked if GUROBI is installed?
Is it # optional ??? ? And what would be ??? there?

It would be # optional - gurobi
There are many instances of that in numerical/gurobi_backend

Nathann

dimpase · 2012-06-22T11:22:24Z

comment:9

Replying to @nathanncohen:

Well. No, Gurobi becomes the default solver as soon as you install it.

Oh dear... And if I install, say, CPLEX? Will it take over? This is strange. Even web browsers don't behave like this :–) Anyway...

It would. You will find out how it behaves by looking at numerical/backends/generic_backend, bottom of the file.
This is made so that the best solver available will be used to solve.... graph problems :-P

Cause this would not be what I'd call 100% doctest coverage :–)
OK, I can specify the solver to use, then it will work.

And you woul prefer to specify manually the solver you want to use, in this case GLPK, and say that the other solvers will not be tested ? This would be 100% coverage ? Or add one doctest per solver ?

One way or another, this weirdness must be exposed in doctests and/or in docs. And I'll add this in docs.

I presume there is a function to find the default solver...

By the way, how would I mark a test so that it would only be invoked if GUROBI is installed?
Is it # optional ??? ? And what would be ??? there?

It would be # optional - gurobi
There are many instances of that in numerical/gurobi_backend

Nathann

nathanncohen · 2012-06-22T11:25:25Z

comment:10

One way or another, this weirdness must be exposed in doctests and/or in docs. And I'll add this in docs.

I presume there is a function to find the default solver...

Probbly there... Actually I' surprised I did not write it already.

http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html

Or else we can change that... What would you think of forgetting about this behavour, and deciding that the default solver is GLPK unless some line in ~/.sage/init.sage says otherwise ?

I would find this behaviour much more sensible now :-)

Nathan

dimpase · 2012-06-23T09:58:37Z

comment:11

Replying to @nathanncohen:

One way or another, this weirdness must be exposed in doctests and/or in docs. And I'll add this in docs.

I presume there is a function to find the default solver...

Probbly there... Actually I' surprised I did not write it already.

http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html

Or else we can change that... What would you think of forgetting about this behavour, and deciding that the default solver is GLPK unless some line in ~/.sage/init.sage says otherwise ?

I would find this behaviour much more sensible now :-)

hopefully the new patch addresses all the things discussed. :–)

Nathan

nathanncohen · 2012-06-23T16:38:45Z

comment:13

Well, then... :-)

Sorry for this ugliness Dima ! Perhaps this class will change totally over time :-)

Nathann

nathanncohen · 2012-06-23T16:38:45Z

Author: Dima Pasechnik

nathanncohen · 2012-06-23T16:38:45Z

Reviewer: Nathann Cohen

ppurka · 2012-06-23T17:04:40Z

comment:14

Hello, I think there should be just two minor changes

in the documentation, the latex equations should probably be enclosed under backticks like `m <= c^T x <= M`, so that the superscripts are rendered properly in the notebook.
the patch should contain the ticket number in its name (I suppose in the name is preferred now?) or in its commit message.

nathanncohen · 2012-06-23T17:07:37Z

comment:15

Hello, I think there should be just two minor changes

in the documentation, the latex equations should probably be enclosed under backticks like `m <= c^T x <= M`, so that the superscripts are rendered properly in the notebook.

Ahahahaha. Right, right, and for that I blame the rose wine of southern France (God, this place is sunny !!)

the patch should contain the ticket number in its name (I suppose in the name is preferred now?) or in its commit message.

Hmmmm... On the other hand I believe that the ticket numbers are now added automatically and that Jeroen prefers when there are none in the patch's message.

HAve fuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuun !

Nathann

ppurka · 2012-06-23T17:10:25Z

Attachment: trac_13148-number_of_variables_in_LP.patch.gz

a patch to have .number_of_variables() return what it should (just minor changes)

ppurka · 2012-06-23T17:11:46Z

comment:16

Ok. I made the changes and removed some trailing whitespaces which should make patchbot happy.

nathanncohen · 2012-06-23T17:12:41Z

comment:17

Great :-)

Nathann

jdemeyer · 2012-07-02T15:24:53Z

Merged: sage-5.2.beta0

dimpase added this to the sage-5.2 milestone Jun 21, 2012

dimpase added c: linear programming labels Jun 21, 2012

dimpase assigned nathanncohen Jun 21, 2012

dimpase added the s: needs review label Jun 21, 2012

nathanncohen mannequin added s: needs work and removed s: needs review labels Jun 22, 2012

dimpase added s: needs review and removed s: needs work labels Jun 23, 2012

nathanncohen mannequin added s: positive review and removed s: needs review labels Jun 23, 2012

This comment has been minimized.

Sign in to view

jdemeyer removed the s: positive review label Jul 2, 2012

jdemeyer closed this as completed Jul 2, 2012

dimpase mentioned this issue Jul 17, 2012

make LP return bounds on variables #13205

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

make LP return the number of variables #13148

make LP return the number of variables #13148

dimpase commented Jun 21, 2012

nathanncohen mannequin commented Jun 22, 2012

dimpase commented Jun 22, 2012

nathanncohen mannequin commented Jun 22, 2012

dimpase commented Jun 22, 2012

nathanncohen mannequin commented Jun 22, 2012

dimpase commented Jun 22, 2012

nathanncohen mannequin commented Jun 22, 2012

dimpase commented Jun 22, 2012

nathanncohen mannequin commented Jun 22, 2012

dimpase commented Jun 23, 2012

nathanncohen mannequin commented Jun 23, 2012

nathanncohen mannequin commented Jun 23, 2012

nathanncohen mannequin commented Jun 23, 2012

ppurka commented Jun 23, 2012

nathanncohen mannequin commented Jun 23, 2012

ppurka commented Jun 23, 2012

This comment has been minimized.

ppurka commented Jun 23, 2012

nathanncohen mannequin commented Jun 23, 2012

jdemeyer commented Jul 2, 2012

make LP return the number of variables #13148

make LP return the number of variables #13148

Comments

dimpase commented Jun 21, 2012

nathanncohen mannequin commented Jun 22, 2012

dimpase commented Jun 22, 2012

nathanncohen mannequin commented Jun 22, 2012

dimpase commented Jun 22, 2012

nathanncohen mannequin commented Jun 22, 2012

dimpase commented Jun 22, 2012

nathanncohen mannequin commented Jun 22, 2012

dimpase commented Jun 22, 2012

nathanncohen mannequin commented Jun 22, 2012

dimpase commented Jun 23, 2012

nathanncohen mannequin commented Jun 23, 2012

nathanncohen mannequin commented Jun 23, 2012

nathanncohen mannequin commented Jun 23, 2012

ppurka commented Jun 23, 2012

nathanncohen mannequin commented Jun 23, 2012

ppurka commented Jun 23, 2012

This comment has been minimized.

ppurka commented Jun 23, 2012

nathanncohen mannequin commented Jun 23, 2012

jdemeyer commented Jul 2, 2012