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: sage-6.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 jdemeyer

I personally have no idea on the implementation of all this LP stuff. Would it be easy to implement this?

comment:2 follow-ups: Changed 5 years ago by ncohen

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 ; follow-up: Changed 5 years ago by jdemeyer

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 forwards-compatible (unlike #15521, which is backwards- but not forwards-compatible).

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

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 follow-up: Changed 5 years ago by jdemeyer

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 ncohen

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 ; follow-ups: Changed 5 years ago by ncohen

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, with real 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 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 forwards-compatible (unlike #15521, which is backwards- but not forwards-compatible).

It does make sense.

Nathann

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

Yo !

Essentially, the code should look like

Looks good.

Nathann

comment:9 follow-up: Changed 5 years ago by tmonteil

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 jdemeyer

Replying to tmonteil:

Since integer, binary, real are mutually exclusive, why not simply have a type 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 jdemeyer

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 jdemeyer

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 ; follow-up: Changed 5 years ago by jdemeyer

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 pseudo-code?

comment:14 in reply to: ↑ 13 Changed 5 years ago by ncohen

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 ncohen

  • 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 to is_real and set_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 that
    sage: 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 ncohen

  • 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 git

  • Commit set to b1f43af754d4ab7e136015519c7fc0cdbe32dd36

Branch pushed to git repo; I updated commit sha1. New commits:

b1f43aftrac #16504: A mandatory 'nonnegative' argument for MixedIntegerLinearProgram.new_variable() until the standard changes

comment:18 follow-up: Changed 5 years ago by dimpase

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 jdemeyer

  • Authors set to Nathann Cohen

Replying to dimpase:

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

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 dimpase

  • Cc ingolfured added

comment:21 follow-up: Changed 5 years ago by jdemeyer

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 follow-up: Changed 5 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer

And why remove this warning?

.. WARNING::
-
- By default, all ``x[i]`` are assumed to be non-negative. See
- :meth:`set_min` to set a different lower bound.

comment:23 Changed 5 years ago by jdemeyer

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

Last edited 5 years ago by jdemeyer (previous) (diff)

comment:24 follow-ups: Changed 5 years ago by dimpase

  • 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 jdemeyer

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 jdemeyer

  • Reviewers set to Jeroen Demeyer
  • Work issues set to nonnegative=False doctests

comment:27 Changed 5 years ago by jdemeyer

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 jdemeyer

  • Work issues changed from nonnegative=False doctests to nonnegative=False doctests, avoid isinstance()

comment:29 in reply to: ↑ 21 Changed 5 years ago by ncohen

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 ncohen

And why remove this warning?

.. WARNING::
-
- By default, all ``x[i]`` are assumed to be non-negative. 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 ncohen

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 ncohen

  • Status changed from needs_work to needs_review

comment:33 Changed 5 years ago by git

  • Commit changed from b1f43af754d4ab7e136015519c7fc0cdbe32dd36 to 97b2f1fa06456de3e54da1787ce20915aceb8ad9

Branch pushed to git repo; I updated commit sha1. New commits:

5f81c2dtrac #16504: Tastes and colors ................
97b2f1ftrac #16504: Broken doctest

comment:34 Changed 5 years ago by git

  • Commit changed from 97b2f1fa06456de3e54da1787ce20915aceb8ad9 to d437be4a258a648e86f8cc1845ade75467609601

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e9ac71dtrac #16504: Tastes and colors ................
d437be4trac #16504: Broken doctest

comment:35 Changed 5 years ago by jdemeyer

  • 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 ncohen

Here are the 10 lines you requested.

Nathann

comment:37 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:38 Changed 5 years ago by git

  • Commit changed from d437be4a258a648e86f8cc1845ade75467609601 to ebc3316525036bcc2a94edcddaa81bca26f3ea9c

Branch pushed to git repo; I updated commit sha1. New commits:

ebc3316trac #16504: additional doctest for nonnegative=False

comment:39 Changed 5 years ago by jdemeyer

  • 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 jdemeyer

  • Commit changed from ebc3316525036bcc2a94edcddaa81bca26f3ea9c to e6ff553f8280f25854b2192cf3a4fa5dcd923a0b
  • Work issues nonnegative=False doctests deleted

New commits:

e6ff553Cosmetic changes

comment:41 Changed 5 years ago by jdemeyer

Please review this commit.

comment:42 Changed 5 years ago by ncohen

I see nothing wrong with it !

Nathann

comment:43 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:44 follow-up: Changed 5 years ago by ncohen

Hey man... What about #16308 ?

Nathann

comment:45 in reply to: ↑ 44 Changed 5 years ago by jdemeyer

Replying to ncohen:

Hey man... What about #16308 ?

Easy, I will look at it...

comment:46 Changed 5 years ago by vbraun

  • 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 ncohen

  • 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:

1903937trac #16504: Updates the tutorial

comment:48 Changed 5 years ago by dimpase

  • Status changed from needs_review to positive_review

Yo! YLC LGTM.

comment:49 Changed 5 years ago by ncohen

Your Loving Cousin ? O_o

Last edited 5 years ago by ncohen (previous) (diff)

comment:50 Changed 5 years ago by ncohen

YOUR LAST CHANGES ????

(I think I got it :-P)

comment:51 Changed 5 years ago by dimpase

Your Last Commit ;-)

comment:52 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

Doctests fail in src/sage/numerical/mip.pyx

comment:53 follow-up: Changed 5 years ago by ncohen

Not on my computer. Did you merge anything in between ?

Nathann

comment:54 in reply to: ↑ 53 Changed 5 years ago by dimpase

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 dimpase

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 dimpase

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 dimpase

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 git

  • Commit changed from 190393753fff48a6e210066fe0f0fff931ef404c to 45bc9377d525b94d7f9ddfbba15b9f074a324937

Branch pushed to git repo; I updated commit sha1. New commits:

27a0bcetrac #16504: Merged with beta5
45bc937trac #16504: Broken doctest

comment:59 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:60 Changed 5 years ago by dimpase

  • Status changed from needs_review to positive_review

LGTM

comment:61 Changed 5 years ago by vbraun

  • Branch changed from public/16504 to 45bc9377d525b94d7f9ddfbba15b9f074a324937
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.