Opened 7 years ago

Closed 7 years ago

#13148 closed enhancement (fixed)

make LP return the number of variables

Reported by: dimpase Owned by: ncohen
Priority: major Milestone: sage-5.2
Component: linear programming Keywords:
Cc: ncohen, ppurka Merged in: sage-5.2.beta0
Authors: Dima Pasechnik Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ppurka)

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 trac_13148-number_of_variables_in_LP.patch to devel/sage

Attachments (1)

trac_13148-number_of_variables_in_LP.patch (2.1 KB) - added by ppurka 7 years ago.
a patch to have <LP>.number_of_variables() return what it should (just minor changes)

Download all attachments as: .zip

Change History (19)

comment:1 Changed 7 years ago by dimpase

  • Cc ncohen ppurka added
  • Status changed from new to needs_review

comment:2 follow-up: Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work

-_-

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

comment:3 in reply to: ↑ 2 ; follow-up: Changed 7 years ago by dimpase

Replying to ncohen:

-_-

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

comment:4 in reply to: ↑ 3 ; follow-up: Changed 7 years ago by ncohen

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

comment:5 in reply to: ↑ 4 ; follow-up: Changed 7 years ago by dimpase

Replying to ncohen:

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

comment:6 in reply to: ↑ 5 ; follow-up: Changed 7 years ago by ncohen

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

comment:7 in reply to: ↑ 6 ; follow-up: Changed 7 years ago by dimpase

Replying to ncohen:

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?

Last edited 7 years ago by dimpase (previous) (diff)

comment:8 in reply to: ↑ 7 ; follow-up: Changed 7 years ago by ncohen

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

comment:9 in reply to: ↑ 8 ; follow-up: Changed 7 years ago by dimpase

Replying to ncohen:

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

comment:10 in reply to: ↑ 9 ; follow-up: Changed 7 years ago by ncohen

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

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

Replying to ncohen:

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

comment:12 Changed 7 years ago by dimpase

  • Status changed from needs_work to needs_review

comment:13 Changed 7 years ago by ncohen

  • Authors set to Dima Pasechnik
  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Well, then... :-)

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

Nathann

comment:14 follow-up: Changed 7 years ago by ppurka

Hello, I think there should be just two minor changes

  1. 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.
  2. the patch should contain the ticket number in its name (I suppose in the name is preferred now?) or in its commit message.

comment:15 in reply to: ↑ 14 Changed 7 years ago by ncohen

Hello, I think there should be just two minor changes

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

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

Changed 7 years ago by ppurka

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

comment:16 Changed 7 years ago by ppurka

  • Description modified (diff)

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

comment:17 Changed 7 years ago by ncohen

Great :-)

Nathann

comment:18 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.2.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.