Opened 9 years ago
Closed 9 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 )
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)
Change History (19)
comment:1 Changed 9 years ago by
- Cc ncohen ppurka added
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 9 years ago by
- Status changed from needs_review to needs_work
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 9 years ago by
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: ↓ 5 Changed 9 years ago by
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: ↓ 6 Changed 9 years ago by
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: ↓ 7 Changed 9 years ago by
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: ↓ 8 Changed 9 years ago by
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?
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 9 years ago by
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: ↓ 10 Changed 9 years ago by
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: ↓ 11 Changed 9 years ago by
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 9 years ago by
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 9 years ago by
- Status changed from needs_work to needs_review
comment:13 Changed 9 years ago by
- 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: ↓ 15 Changed 9 years ago by
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.
comment:15 in reply to: ↑ 14 Changed 9 years ago by
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
Changed 9 years ago by
a patch to have <LP>.number_of_variables() return what it should (just minor changes)
comment:16 Changed 9 years ago by
- Description modified (diff)
Ok. I made the changes and removed some trailing whitespaces which should make patchbot happy.
comment:17 Changed 9 years ago by
Great :-)
Nathann
comment:18 Changed 9 years ago by
- Merged in set to sage-5.2.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
-_-
Ahem... With Gurobi installed the doctests do not pass, because of their stupid way of storing double inequalities :
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