Opened 10 years ago
Closed 10 years ago
#12823 closed defect (fixed)
Allow constants for objective function & deletion of rows in MixedIntegerLinearProgram
Reported by: | john_perry | Owned by: | ncohen |
---|---|---|---|
Priority: | major | Milestone: | sage-5.1 |
Component: | linear programming | Keywords: | solver objective |
Cc: | ncohen | Merged in: | sage-5.1.beta1 |
Authors: | John Perry, Nathann Cohen | Reviewers: | David Coudert, Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12220, #12736, #12833 | Stopgaps: |
Description (last modified by )
Currently, MixedIntegerLinearProgram? does not allow deleting rows. We would like to enable this for all backends that allow it.
Also, this is a bug.
sage: lp = MixedIntegerLinearProgram() sage: x, y = lp[0], lp[1] sage: lp.add_constraint(2*x + 3*y <= 6) sage: lp.add_constraint(3*x + 2*y <= 6) sage: lp.set_objective(x + y + 7) sage: lp.set_integer(x); lp.set_integer(y) sage: lp.solve() 2.0
The correct value ought to be 9, not 2. The problem is this line in the set_objective()
method of mip.pyx
:
f.pop(-1,0)
John Perry will create a patch for GLPK and CBC; Nathann Cohen will create a patch for Gurobi and CPLEX.
Apply:
Attachments (4)
Change History (71)
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
- Type changed from PLEASE CHANGE to defect
I knew I'd forgotten something in the ticket properties: its type. Sorry. :-(
comment:3 Changed 10 years ago by
- Description modified (diff)
- Status changed from new to needs_info
- Summary changed from Allow constants for objective function in MixedIntegerLinearProgram to Allow constants for objective function & deletion of rows in MixedIntegerLinearProgram
I'm about to upload a new patch that takes into account our offline discussion and enables deletion of rows. The doctests and some warning blocks are only in the backends, though; should those be moved to mip.pyx
? I'm not real clear on that.
comment:4 Changed 10 years ago by
I also corrected the output of show()
.
comment:5 follow-up: ↓ 6 Changed 10 years ago by
Hellooooooooooo John !!
Well, there is no need to test functions 10 times in the same way, so the best is to write real hard tests in the backends, and some tests just meant as examples for the users in the documentation of numerical/mip.pyx. The point is that GLPK is the only solver whose documentation appears in Sage's online reference manual, so we can not easily write important documentation in the backends of CBC, Cplex and Gurobi for the user has almost no way to see it.
Nathann
comment:6 in reply to: ↑ 5 Changed 10 years ago by
Replying to ncohen:
Well, there is no need to test functions 10 times in the same way, so the best is to write real hard tests in the backends, and some tests just meant as examples for the users in the documentation of numerical/mip.pyx.
Okay. I added a relatively simplex doctest for mip.pyx
that illustrates removing constraints in a way that works for both GLPK and Coin. Its warning clause should hopefully alert the reader to look up the details for the solver they are using. While I was at it, I also fixed more output problems in show()
.
I guess it's time for you to referee this one, and to submit a patch for the other solvers. :-)
Changed 10 years ago by
comment:7 Changed 10 years ago by
- Description modified (diff)
comment:8 Changed 10 years ago by
- Dependencies set to 12833
- Description modified (diff)
- Status changed from needs_info to needs_review
Hellooooooooo !!!
Simple. Your meant Simple. Not Simplex :-D
I'm making the same kind of mistake something with crazy words from graph theory or Sage... Crazy :-D
Well... This patch took me... quite some time ! It all began with #12833, which this patch depends upon. Some problems with Gurobi's interface. Which I noticed because my gurobi license was not valid anymore. Once I got this license again (and reinstalled Gurobi), I had a problem when installing cbc with sage -i cbc
, for the first package Sage installed was the old one. Harald Schilly fixed that.
And... Ok, now this patch !
It does not do much actually, just adds the required methods in cplex and Gurobi.
Some important things I should mention. Please tell me what you think of them :
- I renamed self.obj_value to self.obj_constant_term, as I would have expected self.obj_value to store the optimal value reached by the objective function.
- Sage should *never* crash, whatever happens in the code. So as usual ((&*@#)*&@%&* indexes in GLPK) I added a +1 to the indices in GLPK, so that the constraints are numbered from 0 regardless of the solver. I also added tests in GLPK and Coin to ensure no crash happens. CPLEX and Gurobi never crash because of that, as they have a smarter management of exceptions (error codes).
- I also changed some doctests for which solutions were not unique. Actually I just removed the lines printing the value of variables, which were not fundamental, and let the others stay as they really tested the new methods.
- I believe I also added some #optional flags in Coin's file, though everything is mixed up in my head after editing 4 files in a row
:-D
Anyway, everything is tested, and....
~/sage/numerical/backends$ sage -t -optional coin_backend.pyx glpk_backend.pyx gurobi_backend.pyx cplex_backend.pyx sage -t -optional "devel/sage-2/sage/numerical/backends/coin_backend.pyx" [1.3 s] sage -t -optional "devel/sage-2/sage/numerical/backends/cplex_backend.pyx" [1.3 s] sage -t -optional "devel/sage-2/sage/numerical/backends/glpk_backend.pyx" [1.3 s] sage -t -optional "devel/sage-2/sage/numerical/backends/gurobi_backend.pyx" [1.4 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 5.3 seconds ~/sage/numerical/backends$
(And I rarely have all solvers installed at the same time)
Soo... Well, if you agree with my patch (I can send you my cplex/gurobi license if necessary), .... :-)
Thank you very much for your work on that one ! It's good to see this class move a bit :-)
Nathann
comment:9 Changed 10 years ago by
- Status changed from needs_review to needs_work
I'm okay with offsetting the constraint according to the solver. However, line 401 of coin_backend should have
if i < 0 or i >= self.si.getNumRows():
instead of
if i < 0 or i > self.si.getNumRows():
shouldn't it?
comment:10 Changed 10 years ago by
- Status changed from needs_work to needs_review
Ahahaah. Totally right. Updated :-)
I had also totally forgotten to do the same for GLPK O_o
That's what you get when you code through copy/paste in several patches :-P
Nathann
comment:11 follow-up: ↓ 12 Changed 10 years ago by
Why do you enumerate the constraints in coin_backend, maybe others? Why not simply loop i from 0 to len(constraints)?
More: I don't understand this:
for i,c in enumerate(constraints): if i < 0 or i >= nrows: sage_free(rows) raise ValueError("The constraint's index i must satisfy 0 <= i < number_of_constraints") rows[i] = constraints[i]
Seems to me the test should be
if c < 0 or c >= nrows:
shouldn't it? and then you could have
rows[i] = c # same as constraints[i]
comment:12 in reply to: ↑ 11 Changed 10 years ago by
Why do you enumerate the constraints in coin_backend, maybe others? Why not simply loop i from 0 to len(constraints)?
Oh. Because I have been told that "enumerate" had been "optimised", and that as "for i in range(n)" it was translated into "good C code". Actually, here is what it gives :
__pyx_t_4 = 0; __pyx_t_1 = ((PyObject *)__pyx_v_coeff); __Pyx_INCREF(__pyx_t_1); __pyx_t_5 = 0; for (;;) { if (__pyx_t_5 >= PyList_GET_SIZE(__pyx_t_1)) break; __pyx_t_2 = PyList_GET_ITEM(__pyx_t_1, __pyx_t_5); __Pyx_INCREF(__pyx_t_2); __pyx_t_5++; __Pyx_XDECREF(__pyx_v_v); __pyx_v_v = __pyx_t_2; __pyx_t_2 = 0; __pyx_v_i = __pyx_t_4; __pyx_t_4 = (__pyx_t_4 + 1);
So it is more or less the same... In particular, when you have a "for i in range(len(something))" I guess the "len(something)" is evaluated many times.
__pyx_t_4 = PyObject_Length(__pyx_v_constraints); if (unlikely(__pyx_t_4 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 450; __pyx_clineno = __LINE__; goto __pyx_L1_error;} for (__pyx_t_5 = 0; __pyx_t_5 < __pyx_t_4; __pyx_t_5+=1) { __pyx_v_i = __pyx_t_5;
Oh. No, it is not. Ok well.. It looks like it is indeed better as an range(len(thing)) :-D
And anyway it makes more sense this way... Of course there is no way to ensure that "len(thing)" does not change between the loops, but the meaning of "range(len(thing))" is clear, even if "thing" changed later on in the loop.
Updated !
Seems to me the test should be
if c < 0 or c >= nrows:shouldn't it?
Yeah totally.... Stupid me.
Nathann
comment:13 follow-up: ↓ 14 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Work issues set to failing doctests
Patchbot's not happy:
********************************************************************** File "/storage/masiao/sage-5.0.beta13-patchbot/devel/sage-12823/sage/numerical/mip.pyx", line 1101: sage: p.number_of_constraints() Expected: 3 Got: 2 ********************************************************************** File "/storage/masiao/sage-5.0.beta13-patchbot/devel/sage-12823/sage/numerical/mip.pyx", line 1131: sage: p.remove_constraint([0, 1]) Exception raised: Traceback (most recent call last): File "/storage/masiao/sage-5.0.beta13-patchbot/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/storage/masiao/sage-5.0.beta13-patchbot/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/storage/masiao/sage-5.0.beta13-patchbot/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_17[8]>", line 1, in <module> p.remove_constraint([Integer(0), Integer(1)])###line 1131: sage: p.remove_constraint([0, 1]) File "mip.pyx", line 1070, in sage.numerical.mip.MixedIntegerLinearProgram.remove_constraint (sage/numerical/mip.c:6538) def remove_constraint(self, int i): TypeError: an integer is required ********************************************************************** File "/storage/masiao/sage-5.0.beta13-patchbot/devel/sage-12823/sage/numerical/mip.pyx", line 1132: sage: p.show() Expected: Maximization: <BLANKLINE> Constraints: x_0 <= 4.0 ... Got: Maximization: <BLANKLINE> Constraints: x_0 + x_1 <= 10.0 x_0 - x_1 <= 0.0 x_0 <= 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) ********************************************************************** 2 items had failures: 1 of 12 in __main__.example_16 2 of 12 in __main__.example_17 ***Test Failed*** 3 failures. For whitespace errors, see the file /home/masiao/.sage/tmp/fermat-6426/mip_26729.py [2.5 s]
comment:14 in reply to: ↑ 13 ; follow-up: ↓ 15 Changed 10 years ago by
Apparently Nathann ran a doctest on everything except mip.pyx
... LOL
Replying to davidloeffler:
Patchbot's not happy:
********************************************************************** File "/storage/masiao/sage-5.0.beta13-patchbot/devel/sage-12823/sage/numerical/mip.pyx", line 1101: sage: p.number_of_constraints() Expected: 3 Got: 2
Yes, 3
in the doctest should change to 2
.
********************************************************************** File "/storage/masiao/sage-5.0.beta13-patchbot/devel/sage-12823/sage/numerical/mip.pyx", line 1131: sage: p.remove_constraint([0, 1]) Exception raised: ... File "/storage/masiao/sage-5.0.beta13-patchbot/devel/sage-12823/sage/numerical/mip.pyx", line 1132: sage: p.show() Expected: Maximization: <BLANKLINE> Constraints: x_0 <= 4.0 ... Got: Maximization: <BLANKLINE> Constraints: x_0 + x_1 <= 10.0 x_0 - x_1 <= 0.0 x_0 <= 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)
These are both because line 1127, which used to have
sage: p.remove_constraints([2])
was changed to
sage: p.remove_constraint([0,1])
Note the missing s. Fixing that should fix these tests. I'll leave it to Nathann, since these come from his patch.
comment:15 in reply to: ↑ 14 Changed 10 years ago by
- Status changed from needs_work to needs_review
Apparently Nathann ran a doctest on everything except
mip.pyx
... LOL
Ahahaha right :-)
I always assume that the backends' specific files are harder to test, and that the graph/ files are the one that should be test to ensure all returned results are correct :-)
Patch updated !
Nathann
comment:16 Changed 10 years ago by
I've examined the code for the patch. Only one question: in the Gurobi backend, for remove_constraints
, why do you loop and call remove_constraint
on each index? The signature for GRBdelconstrs()
seems to allow sending an index, just like GLPK and Coin. I'm not looking at the documentation for it, though, so maybe that's okay.
It's pretty clear that CPLEX is different, so I understand the loop there.
Anyway, I'd like to test the patch ASAP, and give it a positive review, but -- I don't have either CPLEX or Gurobi installed. I understand those aren't free like Coin and GLPK. How should I test the doctests? Must I download them, or can I take you at your word that you've doctested them and the doctests check out?
comment:17 follow-up: ↓ 18 Changed 10 years ago by
Helloooooooo !!!
To be honest I wondered whether we should really have two functions to remove constraints. It sounds nice to have such a high-level function to remove many constraints at once in mip.pyx, this one calling the remove_constraint methods in the backends, but to have a remove_constraintS in each backend we once more have to duplicate a LOT of code (like add_linear_constraintS, add_variableS) that may as well be implemented once and for all in generic_backend.
Then again it is because we are working on pretty different LP. What do you think ?
Nathann
comment:18 in reply to: ↑ 17 Changed 10 years ago by
Replying to ncohen:
To be honest I wondered whether we should really have two functions to remove constraints.
That's true. I guess we should just have the one function, remove_constraints()
, that accepts an iterable. Sort of like we have get_values()
rather than get_value()
. and so forth.
If you're okay with that, I'll revise my ticket.
comment:19 follow-up: ↓ 21 Changed 10 years ago by
Yooooooo John !
Well, I would prefer much more to have only remove_constraint than remove_constraintS. Otherwise we will be calling remove_constraints([1]) which looks a bit odd. But what about what I just said earlier : remove the S functions from the backends, and write generic ones directly in generic_backend ? The code would be sparser, the features still there !?
And this get_values thing is more or less a mistake, because for me "all" variables are indexed dictionaries :-)
Nathann
comment:20 Changed 10 years ago by
Alternatively we can also have remove_constraint functions that can also take iterators as argument.. It's true that we are dealing with Python here, we can write very weird code :-D
But that would perhaps be better for the mip.pyx interface... If we want the Cython interface to stay somehow efficient.
Nathann
comment:21 in reply to: ↑ 19 ; follow-up: ↓ 22 Changed 10 years ago by
Replying to ncohen:
Well, I would prefer much more to have only remove_constraint than remove_constraintS. Otherwise we will be calling remove_constraints([1]) which looks a bit odd.
Amusingly enough, I think remove_constraint([1,2,3])
looks far more odd than remove_constraints([1])
.
But what about what I just said earlier : remove the S functions from the backends, and write generic ones directly in generic_backend ? The code would be sparser, the features still there !?
I'm not quite following what you're saying. Can you be more specific?
And this get_values thing is more or less a mistake, because for me "all" variables are indexed dictionaries
:-)
I don't understand why that makes it a mistake.
comment:22 in reply to: ↑ 21 ; follow-up: ↓ 23 Changed 10 years ago by
Well, I would prefer much more to have only remove_constraint than remove_constraintS. Otherwise we will be calling remove_constraints([1]) which looks a bit odd.
Amusingly enough, I think
remove_constraint([1,2,3])
looks far more odd thanremove_constraints([1])
.
Ahahahah. What about remove_constraint(1) when you just have one constraint to remove ? :-D
I'm not quite following what you're saying. Can you be more specific?
Of course ! What I do not like with the current implementation is that many functions (plus their documentation) are very long and essentially do the work done by the previous function several times. Like add-variable(s), add_linear_constraint(s), and now remove_constraint(s). It would be easy to have both at the same time at no cost. We could define for each backend the function without the s, exactly as it is, and define in generic_backend the function with a S, which would just repeatedly call the previous function. This way, all the backends would inherit this abstract function, so it would be available in the backends, but we would be able to remove all the duplicated code from the specific backends.
Does that sound like a bad idea to you ?
I don't understand why that makes it a mistake.
Because it was done like a mistake. It was done without properly thinking about how it would be used by other people. Even if it is not so bad after all, it was still done out of careless work :-)
Nathann
comment:23 in reply to: ↑ 22 ; follow-up: ↓ 24 Changed 10 years ago by
Replying to ncohen:
Amusingly enough, I think
remove_constraint([1,2,3])
looks far more odd thanremove_constraints([1])
.Ahahahah. What about remove_constraint(1) when you just have one constraint to remove ?
:-D
That looks perfectly fine. Did you mean remove_constraints(1)
? That does look odd, but not very much so.
What I do not like with the current implementation is that many functions (plus their documentation) are very long and essentially do the work done by the previous function several times. Like add-variable(s), add_linear_constraint(s), and now remove_constraint(s).
Okay.
It would be easy to have both at the same time at no cost. We could define for each backend the function without the s, exactly as it is, and define in generic_backend the function with a S, which would just repeatedly call the previous function.
Well, in cases where the backend provides a way to add or remove multiple rows at once (glpk
for instance), we ought to do that instead, rather than remove one at a time.
This way, all the backends would inherit this abstract function, so it would be available in the backends, but we would be able to remove all the duplicated code from the specific backends.
Does that sound like a bad idea to you ?
No, that sounds like what ought to be done.
Let me make sure I understand what you're saying: when code that we have duplicated in mip.pyx
can be moved to generic_backend.pyx
, we should do that. Prime candidates for this are add_variable(s)
, add_linear_constraint(s)
, and remove_constraint(s)
. We would not actually remove the functions (yet) though we would deprecate them.
If I understand you correctly, here's my counter-proposal: let's finish this ticket first, then open another that does that, targeted for sage 5.x where x>0. Otherwise, this gets a little complicated
I don't understand why that makes it a mistake.
Because it was done like a mistake. It was done without properly thinking about how it would be used by other people. Even if it is not so bad after all, it was still done out of careless work
:-)
All you've said is that it's a mistake, only using different words! I still don't understand why it's wrong.
comment:24 in reply to: ↑ 23 ; follow-up: ↓ 25 Changed 10 years ago by
Hellooooooo !!!
That looks perfectly fine. Did you mean
remove_constraints(1)
? That does look odd, but not very much so.
Yep, that's what I meant. That is precisely how get_values currently works ^^;
Well, in cases where the backend provides a way to add or remove multiple rows at once (
glpk
for instance), we ought to do that instead, rather than remove one at a time.
Hmmm, but we can not do that without writing backend-specific code....
No, that sounds like what ought to be done.
Let me make sure I understand what you're saying: when code that we have duplicated in
mip.pyx
can be moved togeneric_backend.pyx
, we should do that. Prime candidates for this areadd_variable(s)
,add_linear_constraint(s)
, andremove_constraint(s)
. We would not actually remove the functions (yet) though we would deprecate them.
Arggg !! NOononono, I meant duplicated code in the backend files ! That is where we have 2 functions doing the same stuff, rewritten in 4 different files ! :-P
If I understand you correctly, here's my counter-proposal: let's finish this ticket first, then open another that does that, targeted for sage 5.x where x>0. Otherwise, this gets a little complicated
That is agreed. So do we merge this one ? Oh, the Gurobi/CPLEX thing, that's right..
Well, that is up to you. I tested them maaaaaaaaany times, but I can also ask David Coudert to check that tests pass, as he has them installed (well, CPLEX for sure and I do not know about Gurobi). But you really should try CPLEX once, it is soooooooooo much faster for integer problems ! :-)
Nathann
comment:25 in reply to: ↑ 24 ; follow-up: ↓ 26 Changed 10 years ago by
Replying to ncohen:
Well, in cases where the backend provides a way to add or remove multiple rows at once (
glpk
for instance), we ought to do that instead, rather than remove one at a time.Hmmm, but we can not do that without writing backend-specific code....
...Arggg !! NOononono, I meant duplicated code in the backend files ! That is where we have 2 functions doing the same stuff, rewritten in 4 different files !
:-P
Okay, I understand now, and I think it makes better sense, too. ;-)
Duplicated code is one thing, like with the Gurobi, CPLEX, and Coin files. I don't think that's a problem, nor is it incompatible with using the one call in glpk, as I suggest. But I do think we should allow a backend to redefine remove_constraint()
to take advantage of its own efficiency. In particular, glpk should be able to remove several constraints w/one function call, because it makes it possible. That doesn't duplicate code.
If you're okay with that, I think this is something that I could take care of today in generic_backend, glpk_backend, and coin_backed; then you could take care of the others.
If you're not okay with that, then, yeah, it would be best to work this out in a different ticket.
I tested them maaaaaaaaany times, but I can also ask David Coudert to check that tests pass, as he has them installed (well, CPLEX for sure and I do not know about Gurobi).
That's probably a better idea; the refereeing process would look cleaner to me. We've been working on this stuff and there's a temptation to be hasty. I can read through the lines of your code & it can look good, but still miss things I can't test.
But you really should try CPLEX once, it is soooooooooo much faster for integer problems !
:-)
Maybe. :-) I don't want to have to download all these things over & over with each new release of Sage, which occurs far more frequently than I'd like. Though we seem to have been stuck at 4.8 for a surprisingly long time...!
comment:26 in reply to: ↑ 25 Changed 10 years ago by
Okay, I understand now, and I think it makes better sense, too.
;-)
Duplicated code is one thing, like with the Gurobi, CPLEX, and Coin files. I don't think that's a problem, nor is it incompatible with using the one call in glpk, as I suggest. But I do think we should allow a backend to redefineremove_constraint()
to take advantage of its own efficiency. In particular, glpk should be able to remove several constraints w/one function call, because it makes it possible. That doesn't duplicate code.
Well, that is the only code I talk about then. Ok, all in all, perhaps we should keep the code as it is. I really have no use for these *s methods, and to me they just take most of the file for nothing, but of course you are working on a different kind of problems.
If you're okay with that, I think this is something that I could take care of today in generic_backend, glpk_backend, and coin_backed; then you could take care of the others.
This time it is me who does not understand what you mean. What would you like to do in these files ?
My proposition was to remove the s functions and replace them by a generic function that would call the *[!s] functions many times, and you think that it is best to have them exposed. I think you are right, mainly because my main argument is "they are useless", and that if anybody think they are useful they immediately become so :-)
If you're not okay with that, then, yeah, it would be best to work this out in a different ticket.
Well, this ticket is written and does the work we wanted it to do when you opened it. So I'd vote for getting it reviewed, then merged if that is ok with you :-)
That's probably a better idea; the refereeing process would look cleaner to me. We've been working on this stuff and there's a temptation to be hasty. I can read through the lines of your code & it can look good, but still miss things I can't test.
No prob ! I sent him an email a couple of minutes ago, I hope he will have some time to deal with that :-)
Maybe. :-) I don't want to have to download all these things over & over with each new release of Sage, which occurs far more frequently than I'd like. Though we seem to have been stuck at 4.8 for a surprisingly long time...!
I am told Sage-5.0 should be out soon. And I would like veryyyyyyyy much to see #11880 inside of it. This ticket is a nice addition too. Well, I personally got used to compiling Sage every week, but it quickly gets tricky when a user comes and says "This code does not work in 4.8, what should I do ?". Most of the time I have no idea what the code was like at this time :-)
Nathann
comment:27 follow-up: ↓ 28 Changed 10 years ago by
Nathann,
I think there is a better implementation of removing constraints than the one we have right now, one that will avoid code duplication, as you say. Let me think about it this afternoon, and I will upload an alternate patch. This will give us something concrete to discuss.
Otherwise, I think we'll just keep confusing each other.
comment:28 in reply to: ↑ 27 Changed 10 years ago by
I think there is a better implementation of removing constraints than the one we have right now, one that will avoid code duplication, as you say. Let me think about it this afternoon, and I will upload an alternate patch.
(at 19h40) This..... afternoon ? :-D
This will give us something concrete to discuss.
Agreed ! :-)
Otherwise, I think we'll just keep confusing each other.
Well, it is slow but even if it takes many exchanges we end up getting the idea through :-)
Nathann
Changed 10 years ago by
comment:29 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_review to needs_info
I've attached another patch that
- removes
remove_constraints()
frommip.pyx
, - incorporates a generic
remove_constraints()
intogeneric_backend.pyx
, more or less along the lines of what you were doing with CPLEX and gurobi, but - retains the definitions of
remove_constraints()
used previously incoin_backend.pyx
andglpk_backend.pyx
, taking advantage of their respective optimizations.
The CPLEX & Gurobi patch can be changed so that only remove_constraint()
need be defined. If you prefer, we could rename that to remove_single_constraint()
. This eliminates some code duplication, though not much. I think the tradeoff is worth the trouble, myself.
Oh -- notice that I still have the old WARN:: and so on in there. I'll change it to the way you had it, if you're okay with this approach. I have a meeting now, but I wanted to get this out so you could look at it & consider it.
Or, we can stick with the older patches.
comment:30 follow-up: ↓ 32 Changed 10 years ago by
Helloooooooo John !!
Thank you for this other patch ! I will update mine in a few seconds so that the remove_constraintS method disappear from Gurobi and CPLEX, but I would like very much to have a remove_constraint (no s) in mip.pyx. The most natural operation is to remove only one constraint, some of the persons who told me they needed such a feature actually edited LP manually and wanted to "do some tests", in which case the operation they would use the most is to remove only one constraint.
Nathann
Changed 10 years ago by
comment:31 Changed 10 years ago by
Patch updated, without remove_constraintS methods :-)
Nathann
comment:32 in reply to: ↑ 30 Changed 10 years ago by
Replying to ncohen:
...but I would like very much to have a remove_constraint (no s) in mip.pyx.
Okay. I can add it, but it will have to wait until tomorrow, or maybe Monday (depending on how busy I am). If you want it sooner, you can add it to your ticket.
comment:33 follow-up: ↓ 34 Changed 10 years ago by
Hello,
Nathann asks me to pass some tests. So I tried the patchs with sage-5.0-beta13
First, I don't understand the install messages.
compote:~/path-to-sage/devel/sage-myclone> hg qimport ~/Recherche/sage-patchs/trac_12823_const_for_obj_funs.patch adding trac_12823_const_for_obj_funs.patch to series file compote:~/path-to-sage/devel/sage-myclone> hg qpush applying trac_12823_const_for_obj_funs.patch now at: trac_12823_const_for_obj_funs.patch compote:~/path-to-sage/devel/sage-myclone> hg qimport ~/Recherche/sage-patchs/trac_12823-cplex_gurobi.patch adding trac_12823-cplex_gurobi.patch to series file compote:~/Soft/sage-5.0.beta13/devel/sage-myclone> hg qpush applying trac_12823-cplex_gurobi.patch patching file sage/numerical/backends/gurobi_backend.pyx Hunk #2 succeeded at 410 with fuzz 2 (offset -13 lines). Hunk #3 succeeded at 418 with fuzz 1 (offset -13 lines). Hunk #4 succeeded at 431 with fuzz 2 (offset -13 lines). Hunk #7 succeeded at 785 with fuzz 1 (offset -12 lines). now at: trac_12823-cplex_gurobi.patch
I don't have coin or gurobi, so I tried only glpk and cplex
~/path-to-sage/devel/sage-myclone>../../sage -t optional sage/numerical/backends/cplex_backend.pyx sage -t -optional "devel/sage-myclone/sage/numerical/backends/cplex_backend.pyx" [1.2 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 1.2 seconds ~/path-to-sage/devel/sage-myclone>../../sage -t optional sage/numerical/backends/glpk_backend.pyx sage -t -optional "devel/sage-myclone/sage/numerical/backends/glpk_backend.pyx" [1.1 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 1.1 seconds
Then I tried the alternate patch but it fails to apply
compote:~/path-to-sage/devel/sage-myclone> hg qapplied compote:~/path-to-sage/devel/sage-myclone> hg qimport ~/path-to-patchs/trac_12823_alternate_removal.patch adding trac_12823_alternate_removal.patch to series file compote:~/path-to-sage/devel/sage-myclone> hg qpush applying trac_12823_alternate_removal.patch patching file sage/numerical/backends/generic_backend.pyx Hunk #1 FAILED at 251 1 out of 1 hunks FAILED -- saving rejects to file sage/numerical/backends/generic_backend.pyx.rej patching file sage/numerical/mip.pyx Hunk #1 FAILED at 1037 1 out of 5 hunks FAILED -- saving rejects to file sage/numerical/mip.pyx.rej patch failed, unable to continue (try -v) patch failed, rejects left in working dir errors during apply, please fix and refresh trac_12823_alternate_removal.patch compote:~/path-to-sage/devel/sage-myclone> hg qapplied trac_12823_alternate_removal.patch
generic_backend.pyx.rej is
--- generic_backend.pyx +++ generic_backend.pyx @@ -252,7 +252,15 @@ - ``constraints`` -- an iterable containing the indices of the rows to remove. """ - raise NotImplementedError() + if type(constraints) == int: self.remove_constraint(constraints) + + cdef int c + cdef int last = self.nrows() + 1 + + for c in sorted(constraints, reverse=True): + if c != last: + self.remove_constraint(c) + last = c cpdef add_linear_constraint(self, coefficients, lower_bound, upper_bound, name=None): """
and mip.pyx.rej is
--- mip.pyx +++ mip.pyx @@ -1038,45 +1038,6 @@ self.add_constraint(functions[0] - functions[1], max=0, name=name) self.add_constraint(functions[1] - functions[2], max=0, name=name) - def remove_constraint(self, int i): - r""" - Removes a constraint from self. - - INPUT: - - - ``i`` -- Index of the constraint to remove. - - EXAMPLE:: - - sage: p = MixedIntegerLinearProgram() - sage: x, y = p[0], p[1] - sage: p.add_constraint(x + y, max = 10) - sage: p.add_constraint(x - y, max = 0) - sage: p.add_constraint(x - y, max = 0) - sage: p.add_constraint(x, max = 4) - sage: p.remove_constraint(2) - sage: p.show() - Maximization: - <BLANKLINE> - Constraints: - x_0 + x_1 <= 10.0 - x_0 - x_1 <= 0.0 - x_0 <= 4.0 - ... - sage: p.number_of_constraints() - 3 - - WARN:: - - Whether the first constraint is numbered 0 or 1 depends on the backend. - For GLPK, the first constraint has index 1; for Coin, it has index 0. - This is why the example above adds the same constraint twice, - and tries to remove on of its copies. Whether it removes the first - or the second depends on the backend. - Since supplying an invalid number WILL CAUSE A CRASH, please be careful! - """ - self._backend.remove_constraint(i) - def remove_constraints(self, constraints): """ Remove several constraints.
Hope it helps.
comment:34 in reply to: ↑ 33 Changed 10 years ago by
Replying to dcoudert:
Nathann asks me to pass some tests. So I tried the patchs with sage-5.0-beta13
First, I don't understand the install messages.
The first one is okay. The fuzz is due to the fact that I used a different edition of sage to create the patch.
The output of the second patch is problematic. FWIW, I can't install the patch on beta8, so apparently there's some dependency that needs to be listed.
I'm going to try and figure out the dependency, then get back to you. Hopefully I won't have to redo the patch.
comment:35 Changed 10 years ago by
- Dependencies changed from 12833 to #12220, #12833
- Description modified (diff)
Looks like I goofed when creating the patch. Please apply trac_12823_const_for_obj_funs.patch first, then trac_12823_alternate_removal.patch, and finally trac_12823-cplex_gurobi.patch. I have modified the ticket description to reflect this.
I'm actually getting doctest errors on this, so I may upload new patches. But, if you don't get problems after this, that would suggest things are okay. I'm using an older beta, so I'm probably still missing something.
comment:36 Changed 10 years ago by
No, I can't get trac_12823-cplex_gurobi.patch to work, either. Alright, time to rework this.
comment:37 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
The new patch should incorporate all the changes. It passes doctests on 5.0.beta8. It might depend on #12220; I'm not sure. The problems I encountered before were due to my having messed up my queue; I had popped too much, and trac_12823_alternate_removal.patch included material from #12736. Please review...
comment:38 Changed 10 years ago by
- Dependencies changed from #12220, #12833 to #12220, #12736, #12833
It looks as if #12736 is a dependency now, due to some changes in function signatures. Sorry for not noticing that previously. I'm about to update another patch that accounts for some problems this has introduced.
comment:39 Changed 10 years ago by
On sage-5.0.beta8, I have the following patches applied first: trac_12220-all_tests_pass.patch, trac_12220-mad+doc.patch, trac_12220-nocache.patch, trac_12736_more_solver_options_for_glpk.patch (and in that order!). Then I apply trac_12823_rolls_all_into_one.patch.
This now works for me on three different versions of sage. I have confirmed that it works with GLPK and Coin (using sage -t -optional sage/numerical/backends/coin_backend.pyx
), so we need testing of CPLEX and Gurobi. Since Nathann added #12833 as a dependency due to some changes in Gurobi, I presume that this may also be required to test that.
comment:40 follow-up: ↓ 41 Changed 10 years ago by
Hello,
I don't need patch #12220 since it is included in beta13.
I first tried to install patch #12736 and then this patch and it fails. Then I realized that you have installed only half of patch #12736. File trac_12736.patch is missing.
When I install trac_12736_more_solver_options_for_glpk.patch and then this patch, install is OK.
Can you udpate ths patch installing first patch #12220 (3 files) and patch #12736 (2 files).
D.
comment:41 in reply to: ↑ 40 Changed 10 years ago by
Replying to dcoudert:
I don't need patch #12220 since it is included in beta13.
Great.
I first tried to install patch #12736 and then this patch and it fails. Then I realized that you have installed only half of patch #12736. File trac_12736.patch is missing.
If that oversight wasn't embarrassing enough, I looked at it and found that it was a mere change in documentation that caused the problem.
Can you udpate ths patch installing first patch #12220 (3 files) and patch #12736 (2 files).
Done. Hopefully it will finally work. Third time's the charm, and all...
comment:42 Changed 10 years ago by
I have it working on beta8 and beta9, two different systems, with GLPK and Coin 2.7.5.
comment:43 follow-up: ↓ 44 Changed 10 years ago by
Ok, I'm now able to install successfully the patch !
Tests are OK with GLPK but not with CPLEX.
sage -t -optional "devel/sage-myclone/sage/numerical/backends/cplex_backend.pyx" IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ". ********************************************************************** File "/path-to-sage/devel/sage-myclone/sage/numerical/backends/cplex_backend.pyx", line 435: sage: p.solve() # optional - CPLEX Exception raised: Traceback (most recent call last): File "/path-to-sage/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/path-to-sage/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/path-to-sage/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_9[10]>", line 1, in <module> p.solve() # optional - CPLEX###line 435: sage: p.solve() # optional - CPLEX File "mip.pyx", line 1431, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:7747) File "cplex_backend.pyx", line 854, in sage.numerical.backends.cplex_backend.CPLEXBackend.solve (sage/numerical/backends/cplex_backend.c:7823) MIPSolverException: 'CPLEX: The problem is unbounded' ********************************************************************** File "/path-to-sage/devel/sage-myclone/sage/numerical/backends/cplex_backend.pyx", line 437: sage: p.get_values([x,y]) # optional - CPLEX Expected: [0.0, 3.0] Got: [2.0, 0.0] ********************************************************************** 1 items had failures: 2 of 13 in __main__.example_9 ***Test Failed*** 2 failures. For whitespace errors, see the file /home/dcoudert/.sage//tmp/cplex_backend_17001.py [1.2 s] ---------------------------------------------------------------------- The following tests failed: sage -t -optional "devel/sage-myclone/sage/numerical/backends/cplex_backend.pyx" Total time for all tests: 1.2 seconds
I have observed that p.remove_constraint(0)
removes all constraints for the test example, hence the unbounded problem error.
sage: p = MixedIntegerLinearProgram(solver='CPLEX') IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ". sage: x, y = p[0], p[1] sage: p.add_constraint(2*x + 3*y, max = 6) sage: p.add_constraint(3*x + 2*y, max = 6) sage: p.set_objective(x + y + 7) sage: p.set_integer(x); p.set_integer(y) sage: p.show() Maximization: x_0 + x_1 + 7.0 Constraints: 2.0 x_0 + 3.0 x_1 <= 6.0 3.0 x_0 + 2.0 x_1 <= 6.0 Variables: x_0 is an integer variable (min=0.0, max=+oo) x_1 is an integer variable (min=0.0, max=+oo) sage: p.solve() 9.0 sage: p.get_values([x,y]) [2.0, 0.0] sage: p.remove_constraint(0) sage: p.show() Maximization: x_0 + x_1 + 7.0 Constraints: Variables: x_0 is an integer variable (min=0.0, max=+oo) x_1 is an integer variable (min=0.0, max=+oo)
comment:44 in reply to: ↑ 43 Changed 10 years ago by
Replying to dcoudert:
Ok, I'm now able to install successfully the patch !
Finally! :-)
Tests are OK with GLPK but not with CPLEX.
I mis-copied a line from Nathann's patch. I've fixed that in the new patch; can you try the new one?
thx a lot john
comment:45 follow-up: ↓ 46 Changed 10 years ago by
That's much better ! now tests are ok for glpk_backend.pyx and cplex_backend.pyx. I can't test coin or gurobi.
However, the following test fails:
compote:/path-to-sage/devel/sage-myclone> ../../sage -t -optional sage/numerical/mip.pyx sage -t -optional "devel/sage-myclone/sage/numerical/mip.pyx" IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ". ********************************************************************** File "/path-to-sage/devel/sage-myclone/sage/numerical/mip.pyx", line 1578: sage: p.solver_parameter("CPX_PARAM_TILIM", 60) # optional - CPLEX Exception raised: Traceback (most recent call last): File "/path-to-sage/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/path-to-sage/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/path-to-sage/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_29[4]>", line 1, in <module> p.solver_parameter("CPX_PARAM_TILIM", Integer(60)) # optional - CPLEX###line 1578: sage: p.solver_parameter("CPX_PARAM_TILIM", 60) # optional - CPLEX File "mip.pyx", line 1599, in sage.numerical.mip.MixedIntegerLinearProgram.solver_parameter (sage/numerical/mip.c:8173) File "glpk_backend.pyx", line 1525, in sage.numerical.backends.glpk_backend.GLPKBackend.solver_parameter (sage/numerical/backends/glpk_backend.cpp:9375) KeyError: 'CPX_PARAM_TILIM' ********************************************************************** 1 items had failures: 1 of 9 in __main__.example_29 ***Test Failed*** 1 failures. For whitespace errors, see the file /home/dcoudert/.sage//tmp/mip_25176.py [1.5 s] ---------------------------------------------------------------------- The following tests failed: sage -t -optional "devel/sage-myclone/sage/numerical/mip.pyx" Total time for all tests: 1.5 seconds
Sorry about that.
comment:46 in reply to: ↑ 45 Changed 10 years ago by
Replying to dcoudert:
That's much better ! now tests are ok for glpk_backend.pyx and cplex_backend.pyx.
Getting there!
I can't test coin or gurobi.
I've tested Coin. We need Nathann to test gurobi (and maybe he can test coin, too.)
However, the following test fails:
The error makes sense. and, it's easily fixed, I think. Let me know if the newest patch fixes it.
Sorry about that.
Quite the contrary: thank you very much! I just hope we finish this today!
comment:47 follow-up: ↓ 49 Changed 10 years ago by
The tests are now OK.
I have also pass a tests on the entire sage/numerical directory, and only 3 tests are failing: coin_backend.pyx, gurobi_backend.pyx, and generic_backend.pyx.
almost done.
comment:48 Changed 10 years ago by
- Reviewers set to David Coudert
comment:49 in reply to: ↑ 47 Changed 10 years ago by
Replying to dcoudert:
I have also pass a tests on the entire sage/numerical directory, and only 3 tests are failing: coin_backend.pyx, gurobi_backend.pyx, and generic_backend.pyx.
almost done.
When you run these tests, are you running as sage -t -optional
or as sage -t
? These failures would make sense if you were running them as sage -t -optional
. You should get no errors if you leave out -optional
.
comment:50 Changed 10 years ago by
You are right:
- I have no error when running sage -t sage/numerical/
- I have errors with the -optimal flag.
comment:51 Changed 10 years ago by
You mean -optional
, not -optimal
:-)
Okay: now we just need Nathann to give it a positive review for Gurobi, and we're done!
comment:52 Changed 10 years ago by
yes, -optional ;)
comment:53 follow-up: ↓ 54 Changed 10 years ago by
Hellooooooo !!
Sorry for the delay, I am in Austria these days and mostly backpacking, so it is pretty hard to find some time with both my computer and WiFI access :-)
The point is that when I apply you folded patch (but I guess I should try to find out what it contains) I mostly get rejections. I applied before the two patch the current ticket says it depends on : #12736, #12833.
~/sage$ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/12833/trac_12833.patch hg qpush adding trac_12833.patch to series file ~/sage$ hg qpush applying trac_12833.patch now at: trac_12833.patch ~/sage$ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/12823/trac_12823_rolls_all_into_one.patch hg qpush adding trac_12823_rolls_all_into_one.patch to series file ~/sage$ hg qpush applying trac_12823_rolls_all_into_one.patch patching file sage/numerical/backends/gurobi_backend.pyx Hunk #1 FAILED at 0 Hunk #2 FAILED at 23 Hunk #4 FAILED at 82 Hunk #5 FAILED at 101 Hunk #6 FAILED at 112 Hunk #7 FAILED at 125 Hunk #8 FAILED at 136 Hunk #9 FAILED at 190 Hunk #10 FAILED at 233 Hunk #11 FAILED at 244 Hunk #12 FAILED at 397 Hunk #13 FAILED at 405 Hunk #14 succeeded at 431 with fuzz 1 (offset 13 lines). Hunk #15 FAILED at 427 Hunk #18 FAILED at 512 Hunk #19 FAILED at 537 Hunk #20 FAILED at 560 Hunk #21 FAILED at 601 Hunk #22 FAILED at 618 Hunk #23 FAILED at 730 Hunk #24 FAILED at 767 Hunk #25 FAILED at 1011 Hunk #26 FAILED at 1047 Hunk #27 FAILED at 1066 Hunk #28 FAILED at 1086 24 out of 28 hunks FAILED -- saving rejects to file sage/numerical/backends/gurobi_backend.pyx.rej patching file sage/numerical/mip.pyx Hunk #8 FAILED at 455 Hunk #9 FAILED at 525 Hunk #12 FAILED at 591 Hunk #30 FAILED at 1571 4 out of 42 hunks FAILED -- saving rejects to file sage/numerical/mip.pyx.rej patch failed, unable to continue (try -v) patch failed, rejects left in working dir errors during apply, please fix and refresh trac_12823_rolls_all_into_one.patch ~/sage$ hg qapplied trac_12736_more_solver_options_for_glpk.patch trac_12736.patch trac_12833.patch trac_12823_rolls_all_into_one.patch
comment:54 in reply to: ↑ 53 Changed 10 years ago by
Nathann
Replying to ncohen:
Sorry for the delay, I am in Austria these days and mostly backpacking, so it is pretty hard to find some time with both my computer and WiFI access
:-)
Hope you're having fun :-)
The point is that when I apply you folded patch (but I guess I should try to find out what it contains) I mostly get rejections. I applied before the two patch the current ticket says it depends on : #12736, #12833.
I'm not surprised. I forgot to test it w/#12833 first.
I can't get #12833 to apply at all on 5.0.beta9, so I'll have to try this at home, later tonight or tomorrow. Bummer. Stay tuned...
comment:55 follow-up: ↓ 56 Changed 10 years ago by
- Reviewers changed from David Coudert to David Coudert, Nathann Cohen
Okay. I downloaded & build beta 13 on a second computer (the first is a nearly 15 year-old, 32-bit machine, bogged down in testing some other tickets), applied the requisite patches for all dependencies listed, and after a lot of tinkering, got it to work.
I then went back & figured out why beta 8 didn't like #12833 --- some sort of whitespace error --- and tested it there, since I have coin installed there. That works, too.
So Coin & GLPK work on my machines. Someone please test gurobi & cplex again!
An aside: most of the problems seem to have been caused by whitespace!!! Apparently #12833 fixes some whitespace problems in gurobi and mip that I had also tried to fix in the latest patch for this one. I hadn't tried to fix them before; hence the unpleasant surprise.
I hope this one works...
comment:56 in reply to: ↑ 55 Changed 10 years ago by
- Status changed from needs_review to positive_review
Hellooooooooooooo !!!
Well, this one seems well oiled :-)
~/sage/numerical/backends$ sage -t -optional coin_backend.pyx glpk_backend.pyx gurobi_backend.pyx cplex_backend.pyx sage -t -optional "devel/sage-2/sage/numerical/backends/coin_backend.pyx" [1.2 s] sage -t -optional "devel/sage-2/sage/numerical/backends/cplex_backend.pyx" [1.2 s] sage -t -optional "devel/sage-2/sage/numerical/backends/glpk_backend.pyx" [1.2 s] sage -t -optional "devel/sage-2/sage/numerical/backends/gurobi_backend.pyx" [1.4 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 5.0 seconds
And all tests pass in mip.pyx, graph, dgraph, generic_graph. Sooooo... I guess the patch is now positively reviewed :-)
Nathann
comment:57 Changed 10 years ago by
Yessss! :-) It only took... uhm, how many tries? X-D
comment:58 Changed 10 years ago by
Ahahah.. Well, it is still funnier like that compared with times when it takes several months before a ticket gets reviewed :-)
Nathann
comment:59 Changed 10 years ago by
(This being said, the ticket still depends on #12833 ^^;
)
comment:60 Changed 10 years ago by
Hello,
I don't need patch #12833 to apply this patch and all tests are OK (sage -t sage/numerical, and sage -t -optional sage/numerical/backends/glpk_backend.pyx and same for cplex). So we could remove the dependency.
D.
comment:61 Changed 10 years ago by
- Milestone changed from sage-5.0 to sage-5.1
- Work issues failing doctests deleted
comment:62 Changed 10 years ago by
comment:63 Changed 10 years ago by
- Status changed from positive_review to needs_work
The patch needs a proper commit message.
comment:64 Changed 10 years ago by
- Status changed from needs_work to positive_review
comment:65 Changed 10 years ago by
- Status changed from positive_review to needs_work
This needs to be rebased to sage-5.0.rc0:
applying /padic/scratch/jdemeyer/merger/patches/trac_12823_rolls_all_into_one.patch patching file sage/numerical/mip.pyx Hunk #16 FAILED at 809 Hunk #17 FAILED at 852 Hunk #19 FAILED at 969 3 out of 35 hunks FAILED -- saving rejects to file sage/numerical/mip.pyx.rej abort: patch failed to apply
Changed 10 years ago by
comment:66 Changed 10 years ago by
- Status changed from needs_work to positive_review
Patch updated ! ;-)
Nathann
comment:67 Changed 10 years ago by
- Merged in set to sage-5.1.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
I've uploaded a patch for Coin & GLPK. Do we want to take care of deleting constraints in this patch, too? I haven't done that yet; if so, I'll modify the ticket correspondingly.