Opened 5 years ago
Closed 5 years ago
#16504 closed defect (fixed)
A mandatory 'nonnegative' argument for MixedIntegerLinearProgram.new_variable() until the standard changes
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  linear programming  Keywords:  
Cc:  ncohen, dimpase, vbraun, dcoudert, hartke, wdj, john_perry, benjaminfjones, ingolfured  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Jeroen Demeyer 
Report Upstream:  N/A  Work issues:  
Branch:  45bc937 (Commits)  Commit:  45bc9377d525b94d7f9ddfbba15b9f074a324937 
Dependencies:  Stopgaps: 
Description
This should create an unbounded real variable:
sage: p = MixedIntegerLinearProgram() sage: x = p.new_variable(nonnegative=False)
We should see nonnegative
as a toggle, not as a type. The following should also work as expected intuitively:
sage: x = p.new_variable(integer=True, nonnegative=False) sage: x = p.new_variable(integer=True, nonnegative=True)
Change History (61)
comment:1 Changed 5 years ago by
comment:2 followups: ↓ 3 ↓ 4 Changed 5 years ago by
Yes, it would be easy. The main problem is that if you want to change the current behaviour of the function (i.e. if you want nonnegative=False to be the default) then you will have to "make nonnegative mandatory" for a while and raise a warning when it is not set. Otherwise when you will change it, guys who currently use "integer=True" to mean "nonnegative integer" will find themselves with LP returning weird answers.
That was the point of #15521.
Also, it may seem weird to see all these variables be nonnegative by default but that's really the standard for LP solvers. The LP backends really assume non negativity unless asked otherwise, and changing the standard in Sage is really something that we do "for the general mathematicians knowing that it could surprise guys used to LP".
Nathann
comment:3 in reply to: ↑ 2 ; followup: ↓ 7 Changed 5 years ago by
Replying to ncohen:
That was the point of #15521.
I don't think that #15521 made things more clear...
How about this:
we require at most one of integer
, binary
, real
to be given, with real
the default if none is given.
nonnegative
is a boolean determining whether or not the variable is assumed to be nonnegative. In the function, we have nonnegative=None
by default which is currently interpreted as nonnegative=True
but with the warning from #15521.
I think this proposal is backwards and forwardscompatible (unlike #15521, which is backwards but not forwardscompatible).
comment:4 in reply to: ↑ 2 ; followup: ↓ 6 Changed 5 years ago by
Replying to ncohen:
The main problem is that if you want to change the current behaviour of the function (i.e. if you want nonnegative=False to be the default) then you will have to "make nonnegative mandatory" for a while and raise a warning when it is not set.
I agree with this, but I don't see the problem. The deprecation warning from #15521 isn't a problem either...
comment:5 followup: ↓ 8 Changed 5 years ago by
Essentially, the code should look like
def new_variable(self, real=False, binary=False, integer=False, nonnegative=None): if sum([real, binary, integer]) >= 2: raise ValueError("exactly one of the available types has to be True") if nonnegative is None: deprecation(15521, "The default value of 'nonnegative' will change, to "+ "False instead of True. " + "You should add the explicit 'nonnegative=True'.") nonnegative = True if binary: vtype = self.__BINARY elif integer: vtype = self.__INTEGER else: # real is the default if no type is explicitly given vtype = self.__REAL # Set minimum value to 0 or oo depending on "nonnegative" ...
comment:6 in reply to: ↑ 4 Changed 5 years ago by
I agree with this, but I don't see the problem. The deprecation warning from #15521 isn't a problem either...
It is not a problem, it just means that "doing the job" takes one year :P
Nathann
comment:7 in reply to: ↑ 3 ; followups: ↓ 11 ↓ 12 Changed 5 years ago by
I don't think that #15521 made things more clear...
Well, then improve it if you do not like it :P
How about this: we require at most one of
integer
,binary
,real
to be given, withreal
the default if none is given.
Makes sense. Even though, with the turn that events take, I wonder if it would not be better to require one of them to be explicitly given : no default. Again, nonnegative variables are the default in this field, and we switched to another. Requiring a variable would require the users to read the doc, which may avoid misunderstandings.
nonnegative
is a boolean determining whether or not the variable is assumed to be nonnegative. In the function, we havenonnegative=None
by default which is currently interpreted asnonnegative=True
but with the warning from #15521.I think this proposal is backwards and forwardscompatible (unlike #15521, which is backwards but not forwardscompatible).
It does make sense.
Nathann
comment:8 in reply to: ↑ 5 ; followup: ↓ 13 Changed 5 years ago by
Yo !
Essentially, the code should look like
Looks good.
Nathann
comment:9 followup: ↓ 10 Changed 5 years ago by
Since integer, binary, real
are mutually exclusive, why not simply have a type
variable that takes one on the three values ?
comment:10 in reply to: ↑ 9 Changed 5 years ago by
Replying to tmonteil:
Since
integer, binary, real
are mutually exclusive, why not simply have atype
variable that takes one on the three values ?
Backwards compatibility. With my proposal, we would have full backwards compatibility.
comment:11 in reply to: ↑ 7 Changed 5 years ago by
Replying to ncohen:
Even though, with the turn that events take, I wonder if it would not be better to require one of them to be explicitly given : no default.
Again, for backwards compatibility, we cannot just do that.
comment:12 in reply to: ↑ 7 Changed 5 years ago by
Replying to ncohen:
nonnegative variables are the default in this field, and we switched to another.
No, we didn't switch, we just added a deprecation warning. This ticket doesn't change that.
comment:13 in reply to: ↑ 8 ; followup: ↓ 14 Changed 5 years ago by
Replying to ncohen:
Looks good.
Hi Nathann,
Given that you know this code and I don't, could you make the final implementation based on my pseudocode?
comment:14 in reply to: ↑ 13 Changed 5 years ago by
Yo !
Given that you know this code and I don't, could you make the final implementation
Hmmmm.... You are hardly a beginner with Sage, but let's make a deal : I implement this ticket and you finish #16308 using #16374 that has been merged in the meantime ? I need this for my combinatorial design stuff :P
Nathann
comment:15 Changed 5 years ago by
 Branch set to u/ncohen/16504
 Status changed from new to needs_review
Hello !
Here is the branch. Took much longer than I thought.
What it does :
 Removes the
is_nonnegative
,set_nonnegative
functions that were introduced in #15521 as 'nonnegative' is not meant to be a variable type but a 'property' of any type. Those functions are renamed tois_real
andset_real
, i.e. their status before #16504
 It was formerly possible to do things like that
sage: p = MixedIntegerLinearProgram() sage: v = p.new_variable() sage: p.set_min(v[0],15) sage: p.get_min(v[0]) 15.0
but it was NOT possible to do things like thatsage: p.set_min(v,17) sage: p.get_min(v[18]) 17.0
i.e. it was possible to define upper/lower bound on a specific variable, but not to do the same on a dictionary of variables in such a way that the new variables created fro the dictionary will inherit the bounds. But that's exactly what we wanted to do here.
Thus I needed to add arguments lower/upper bound to the constructor of
MIPVariable
, plus set functions where it was needed.
Well... needs_review
!
Nathann
comment:16 Changed 5 years ago by
 Summary changed from Fix the confusion in MILP.new_variable() to A mandatory 'nonnegative' argument for MixedIntegerLinearProgram.new_variable() until the standard changes
comment:17 Changed 5 years ago by
 Commit set to b1f43af754d4ab7e136015519c7fc0cdbe32dd36
Branch pushed to git repo; I updated commit sha1. New commits:
b1f43af  trac #16504: A mandatory 'nonnegative' argument for MixedIntegerLinearProgram.new_variable() until the standard changes

comment:18 followup: ↓ 19 Changed 5 years ago by
As now p.set_min(v,17)
becomes possible, why not have optional max
and min
in new_variable()
(many solvers have it, at least per variable) ? E.g. v=p.new_variable(min=17, max=18)
. A usual application is relaxation of binary IPs, so one would have real variables p.new_variable(min=0, max=1)
.
comment:19 in reply to: ↑ 18 Changed 5 years ago by
Replying to dimpase:
As now
p.set_min(v,17)
becomes possible, why not have optionalmax
andmin
innew_variable()
(many solvers have it, at least per variable) ? E.g.v=p.new_variable(min=17, max=18)
. A usual application is relaxation of binary IPs, so one would have real variablesp.new_variable(min=0, max=1)
.
I agree, but perhaps not on this ticket. Let's try not to do too many things at the same time.
comment:20 Changed 5 years ago by
 Cc ingolfured added
comment:21 followup: ↓ 29 Changed 5 years ago by
Can you undo this change:
@@ 241,11 +239,10 @@ cdef class MixedIntegerLinearProgram(SageObject): sage: g = graphs.PetersenGraph() sage: p = MixedIntegerLinearProgram(maximization=True)  sage: b = p.new_variable() + sage: b = p.new_variable(binary=True) sage: p.set_objective(sum([b[v] for v in g])) sage: for (u,v) in g.edges(labels=None): ... p.add_constraint(b[u] + b[v], max=1)  sage: p.set_binary(b) sage: p.solve(objective_only=True) 4.0 """
comment:22 followup: ↓ 30 Changed 5 years ago by
 Reviewers set to Jeroen Demeyer
And why remove this warning?
.. WARNING::

 By default, all ``x[i]`` are assumed to be nonnegative. See
 :meth:`set_min` to set a different lower bound.
comment:23 Changed 5 years ago by
 Status changed from needs_review to needs_work
 Work issues set to nonnegative=False doctests
You should add more doctests for nonnegative=False
. As far as I can see, there is no doctest for an actual MILP problem with nonnegative=False
variables. You should doctest this both for integer
and real
types.
comment:24 followups: ↓ 25 ↓ 31 Changed 5 years ago by
 Reviewers Jeroen Demeyer deleted
 Work issues nonnegative=False doctests deleted
Am I correct that this is a safe change in the sense that the existing code using nonnegative=True
as default would either continue to work, or will refuse to work? I.e. people won't possibly start getting wrong answers?
comment:25 in reply to: ↑ 24 Changed 5 years ago by
Replying to dimpase:
Am I correct that this is a safe change in the sense that the existing code using
nonnegative=True
as default would either continue to work, or will refuse to work? I.e. people won't possibly start getting wrong answers?
Old code should work exactly as before, possibly with a deprecation warning.
comment:26 Changed 5 years ago by
 Reviewers set to Jeroen Demeyer
 Work issues set to nonnegative=False doctests
comment:27 Changed 5 years ago by
Could you replace
if isinstance(v, MIPVariable): v.set_min(min) else: self._backend.variable_lower_bound(self._variables[v], min)
by the more Pythonic
try: v.set_min(min) except AttributeError: self._backend.variable_lower_bound(self._variables[v], min)
My personal opinion is that v.set_min(min)
should actually work in all cases, but that's perhaps for a new ticket.
comment:28 Changed 5 years ago by
 Work issues changed from nonnegative=False doctests to nonnegative=False doctests, avoid isinstance()
comment:29 in reply to: ↑ 21 Changed 5 years ago by
Can you undo this change:
Why ? O_o
It's better in the new version, isn't it ? O_o
Nathann
comment:30 in reply to: ↑ 22 Changed 5 years ago by
And why remove this warning?
.. WARNING::   By default, all ``x[i]`` are assumed to be nonnegative. See  :meth:`set_min` to set a different lower bound.
Because there is no need for a warning anymore : now the user explicitly says whether he wants the variables to be nonnegative or not, or he gets a warning.
Plus it will be the other way around next year.
Nathann
comment:31 in reply to: ↑ 24 Changed 5 years ago by
Am I correct that this is a safe change in the sense that the existing code using
nonnegative=True
as default would either continue to work, or will refuse to work? I.e. people won't possibly start getting wrong answers?
It will work, and there should be no wrong answer (unless there is a bug somewhere). The default behaviour is now "nonnegative + warning", and the correct way to use this class is to specify a value for nonnegative.
Nathann
comment:32 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:33 Changed 5 years ago by
 Commit changed from b1f43af754d4ab7e136015519c7fc0cdbe32dd36 to 97b2f1fa06456de3e54da1787ce20915aceb8ad9
comment:34 Changed 5 years ago by
 Commit changed from 97b2f1fa06456de3e54da1787ce20915aceb8ad9 to d437be4a258a648e86f8cc1845ade75467609601
comment:35 Changed 5 years ago by
 Status changed from needs_review to needs_work
 Work issues changed from nonnegative=False doctests, avoid isinstance() to nonnegative=False doctests
Still needs nonnegative=False
doctests.
comment:36 Changed 5 years ago by
Here are the 10 lines you requested.
Nathann
comment:37 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:38 Changed 5 years ago by
 Commit changed from d437be4a258a648e86f8cc1845ade75467609601 to ebc3316525036bcc2a94edcddaa81bca26f3ea9c
Branch pushed to git repo; I updated commit sha1. New commits:
ebc3316  trac #16504: additional doctest for nonnegative=False

comment:39 Changed 5 years ago by
 Branch changed from u/ncohen/16504 to u/jdemeyer/ticket/16504
 Created changed from 06/20/14 15:11:13 to 06/20/14 15:11:13
 Modified changed from 06/24/14 07:31:52 to 06/24/14 07:31:52
comment:40 Changed 5 years ago by
 Commit changed from ebc3316525036bcc2a94edcddaa81bca26f3ea9c to e6ff553f8280f25854b2192cf3a4fa5dcd923a0b
 Work issues nonnegative=False doctests deleted
New commits:
e6ff553  Cosmetic changes

comment:41 Changed 5 years ago by
Please review this commit.
comment:42 Changed 5 years ago by
I see nothing wrong with it !
Nathann
comment:43 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:44 followup: ↓ 45 Changed 5 years ago by
Hey man... What about #16308 ?
Nathann
comment:45 in reply to: ↑ 44 Changed 5 years ago by
comment:46 Changed 5 years ago by
 Status changed from positive_review to needs_work
doctest failure src/doc/en/thematic_tutorials/linear_programming.rst
comment:47 Changed 5 years ago by
 Branch changed from u/jdemeyer/ticket/16504 to public/16504
 Commit changed from e6ff553f8280f25854b2192cf3a4fa5dcd923a0b to 190393753fff48a6e210066fe0f0fff931ef404c
 Status changed from needs_work to needs_review
Cursed tutorial. Sorry 'bout that :/
I rewrote the necessary part in an additional commit.
Nathann
New commits:
1903937  trac #16504: Updates the tutorial

comment:49 Changed 5 years ago by
Your Loving Cousin ? O_o
comment:50 Changed 5 years ago by
YOUR LAST CHANGES ????
(I think I got it :P
)
comment:51 Changed 5 years ago by
Your Last Commit ;)
comment:52 Changed 5 years ago by
 Status changed from positive_review to needs_work
Doctests fail in src/sage/numerical/mip.pyx
comment:53 followup: ↓ 54 Changed 5 years ago by
Not on my computer. Did you merge anything in between ?
Nathann
comment:54 in reply to: ↑ 53 Changed 5 years ago by
Replying to ncohen:
Not on my computer. Did you merge anything in between ?
same here, works for me too, so that must be cosmic rays (possibly emitted by git) affecting Volker's machine...
comment:55 Changed 5 years ago by
just to make sure I merged public/16504 over the latest 6.3.beta5, and I get 2 failures:
sage t src/sage/numerical/mip.pyx ********************************************************************** File "src/sage/numerical/mip.pyx", line 253, in sage.numerical.mip.MixedIntegerLinearProgram Failed example: for type in ["binary", "integer"]: k = 3 items = [1/5, 1/3, 2/3, 3/4, 5/7] maximum=1 p=MixedIntegerLinearProgram() box=p.new_variable(**{type:True}) for b in range(k): p.add_constraint(p.sum([items[i]*box[i,b] for i in range(len(items))]) <= maximum) for i in range(len(items)): p.add_constraint(p.sum([box[i,b] for b in range(k)]) == 1) p.set_objective(None) _ = p.solve() box=p.get_values(box) print(all(v in ZZ for v in box.values())) Expected: True True Got: True doctest:839: DeprecationWarning: The default value of 'nonnegative' will change, to False instead of True. You should add the explicit 'nonnegative=True'. See http://trac.sagemath.org/15521 for details. True ********************************************************************** File "src/sage/numerical/mip.pyx", line 364, in sage.numerical.mip.MixedIntegerLinearProgram.? Failed example: v = p.new_variable(real=True) Expected: doctest:839: DeprecationWarning: The default value of 'nonnegative' will change, to False instead of True. You should add the explicit 'nonnegative=True'. See http://trac.sagemath.org/15521 for details. Got: <BLANKLINE> ********************************************************************** 2 items had failures: 1 of 9 in sage.numerical.mip.MixedIntegerLinearProgram 1 of 15 in sage.numerical.mip.MixedIntegerLinearProgram.? [440 tests, 2 failures, 8.08 s]  sage t src/sage/numerical/mip.pyx # 2 doctests failed  Total time for all tests: 8.7 seconds cpu time: 8.1 seconds cumulative wall time: 8.1 seconds
comment:56 Changed 5 years ago by
the following obvious change fixes the things:
diff git a/src/sage/numerical/mip.pyx b/src/sage/numerical/mip.pyx index 2f8d0e3..5741f68 100644  a/src/sage/numerical/mip.pyx +++ b/src/sage/numerical/mip.pyx @@ 265,6 +265,8 @@ cdef class MixedIntegerLinearProgram(SageObject): ....: box=p.get_values(box) ....: print(all(v in ZZ for v in box.values())) True + doctest:839: DeprecationWarning: The default value of 'nonnegative' will change, to False inst + See http://trac.sagemath.org/15521 for details. True """ @@ 362,8 +364,6 @@ cdef class MixedIntegerLinearProgram(SageObject): sage: p = MixedIntegerLinearProgram() sage: v = p.new_variable(real=True)  doctest:839: DeprecationWarning: The default value of 'nonnegative' will change, to False  See http://trac.sagemath.org/15521 for details. sage: p.get_min(v[0]) 0.0 """
comment:57 Changed 5 years ago by
To fix this properly, some commit untangling is needed, I suppose. Probably, a rebase over beta5 might be the easiest option, but I am not 100% sure.
comment:58 Changed 5 years ago by
 Commit changed from 190393753fff48a6e210066fe0f0fff931ef404c to 45bc9377d525b94d7f9ddfbba15b9f074a324937
comment:59 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:61 Changed 5 years ago by
 Branch changed from public/16504 to 45bc9377d525b94d7f9ddfbba15b9f074a324937
 Resolution set to fixed
 Status changed from positive_review to closed
I personally have no idea on the implementation of all this LP stuff. Would it be easy to implement this?