should LPs default to assuming nonnegative variables in Sage?

[kcrisman]

In http://ask.sagemath.org/question/3282/ it was revealed that in Sage, the MILP interface defaults (like most such software) to assuming nonnegative variables as a constraint, which they has to be explicitly undone.  It looks like the (possibly unrelated) linear_program command also does this.  This is natural in that world.  However, Nathann did a little digging upon my request and discovered that Matlab and Maple apparently (?) don't assume this.  

So... should we change our interface?  Or should we keep it the same as it was?  I can think of arguments for both.  Input would be appreciated, especially from those who have actually used this functionality (perhaps in contexts not "about" LP).

- kcrisman

[Nathann Cohen]

Yoooooooooooo !

In http://ask.sagemath.org/question/3282/ it was revealed that in Sage, the MILP interface defaults (like most such software) to assuming nonnegative variables as a constraint, which they has to be explicitly undone.  It looks like the (possibly unrelated) linear_program command also does this.  This is natural in that world.  However, Nathann did a little digging upon my request and discovered that Matlab and Maple apparently (?) don't assume this.  

So... should we change our interface?  Or should we keep it the same as it was?  I can think of arguments for both.  Input would be appreciated, especially from those who have actually used this functionality (perhaps in contexts not "about" LP).

I just wanted to add to this (very legitimate) question that I see three ways out :

* Just drop this assumption, and change nothing else

* Change the syntax of p.new_variable() to accept a lower_bound and upper_bound argument, with lower_bound = None and upper_bound = None

* Do the thing above with lower_bound = 0 so that the default behaviour does not change but the users actually have an idea of how to change that

Right now, the only way to change this assumption is not very natural : first you create the variable, then you run p.set_min(variable, None). So somehow, merging this with p.new_variable may be  way out even if we stick with lower_bound = 0. Besides :

* We could also do any of the last two things above, AND get rid of the [gs]et_(min|max). I don't like them anyway.

* I have to say for my defense that I stupidly copied what the actual LP solvers we use were doing when I implemented the interface. And stupid people who are just obeying the orders are never held responsible. (I'm willing to change that anytime, but there'll be blood if following stupidly does not keep you safe anymore. And not only mine :-PPPPPPPPPP)

* I have no idea why the LP solvers we use have a notion of "bounds" on the variables, given that any constraint can define the same kind of bounds. Possibly a difference in the running time, but I am totally guessing and I have no technical idea of their internals.

Nathann

[Andrey Novoseltsev]

I am not an expert on LP, but as an author of alternative (not merged, see http://trac.sagemath.org/ticket/14288 ) LP functionality let me add a couple rubbles nevertheless.

My implementation does not assume any bounds on variables when you construct an LPProblem, but you can add non-negativity or non-positivity explicitly and when constructing LPProblemStandardForm everything is forced to be non-negative.

From what I know of simplex method (after teaching it to a few hundred students ;-)), sign restrictions on variables are quite different from other constraints and, in fact, it is very natural to reduce a system of equality and inequality constraints to a system of equations plus sign restrictions, i.e. leave only the simplest inequalities possible: homogeneous and in a single variable each. I imagine that non-homogeneous inequalities in a single variable also can be handled much more efficiently than generic ones and it is very natural to do it for binary variables.

Let me also without any modesty suggest yet another solution: merge my module without any extra assumptions for use by students and perhaps leave "the real LP functionality" that is used by experts close to actual solvers. I also completely support getting rid of get/set methods for bounds - specify them when defining a variable!

Thank you,
Andrey

[Dima Pasechnik]

On 2013-12-06, kcrisman <kcri...@gmail.com> wrote:
> In http://ask.sagemath.org/question/3282/ it was revealed that in Sage, the
> MILP interface defaults (like most such software) to assuming nonnegative
> variables as a constraint, which they has to be explicitly undone. It
> looks like the (possibly unrelated) linear_program command also does this.

linear_program() is an old interface to cvxopt.
It should go away and be replaced by a cvxopt backend for "main" Sage LP.
(something I meant to write for years, but never got to)

> This is natural in that world. However, Nathann did a little digging upon
> my request and discovered that Matlab and Maple apparently (?) don't assume
> this.

the assumption x>=0 goes back to the old times when LPs were normally in
the "standard" form max c^T x subject to Ax=b, x>=0.

>
> So... should we change our interface? Or should we keep it the same as it
> was? I can think of arguments for both. Input would be appreciated,
> especially from those who have actually used this functionality (perhaps in
> contexts not "about" LP).

I suppose one can add a parameter to the method creaing variables to
LPs, and allowing one to specify nonnegativity.
This, combined with the deprecation, should allow for an easy change -
indeed the default assumption x>=0 is kind of weird for outsiders...

Dima
>
> - kcrisman
>

[Nathann Cohen]

Hellooooooooo !!

I suppose one can add a parameter to the method creaing variables to
LPs, and allowing one to specify nonnegativity.
This, combined with the deprecation, should allow for an easy change -
indeed the default assumption x>=0 is kind of weird for outsiders...

Hmmm..... O_o

*Which* deprecation ? You can deprecate a function, or a keyword, but in this case if we change the default behaviour.... Except adding a warning when a MixedIntegerLinearProgram is built... Or making a new argument mandatoy in the new_variable function... O_o

Nathann

[Andrey Novoseltsev]

Perhaps keep default >=0 but when new_variable is called issue DeprecationWarning that the default will change? New parameters should allow setting both >=0 and free explicitly, so that those who want >=0 in the future can set it now and those who don't can also set it now, and when the default will change - no code will be broken, just some of it will explicitly set a parameter which is there by default anyway, which is not that big of a deal.

get/set methods on the other hand can just be deprecated directly.

Andrey

[Nathann Cohen]

> Perhaps keep default >=0 but when new_variable is called issue DeprecationWarning that the default will change? New parameters should allow setting both >=0 and free explicitly, so that those who want >=0 in the future can set it now and those who don't can also set it now, and when the default will change - no code will be broken, just some of it will explicitly set a parameter which is there by default anyway, which is not that big of a deal.
>
> get/set methods on the other hand can just be deprecated directly.

Hmmm.. Well, indeed new_variable could give a warning whenever the
future "min" argument is left undefined. Makes sense. Though p['x']
call new_variable implicitly. Hmmmmmm.. Okay okay, this way works.

Nathann

[Stephen Hartke]

I frequently use the IP/LP functionality in Sage for problems in graph theory.  I'm now used to the assumption that most solvers make about variables being nonnegative, but I find it nonobvious and it has tripped me up several times in the past.  I think that making no assumption about variables but letting nonnegativity be added when the variable is declared would be great.  

Might it make sense to add a type of variable (ie, "continuous", "integer", "binary", "nonnegative")?  One disadvantage is that nonnegative continuous is different than nonnegative integer.

One additional comment: The set_min (and set_max) functionality is still needed, even if there is a way to indicate bounds when declaring variables.  One situation is for indexed variables where they had different bounds.  Another situation occurs when "fixing" a variable to a value after the program has been created.  For instance, an IP might model finding a maximum independent set in a graph, but I might wish to ask about independent sets that contain a specific vertex.  This is easy to do from the usual IP by forcing that variable to 1.

Best wishes,

Stephen

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To post to this group, send email to sage-...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/groups/opt_out.

[Nathann Cohen]

Yoooooooo !!

> I frequently use the IP/LP functionality in Sage for problems in graph
> theory.

Hmmm.. I'm *very* glad to learn this :-)

> I'm now used to the assumption that most solvers make about
> variables being nonnegative, but I find it nonobvious and it has tripped me
> up several times in the past. I think that making no assumption about
> variables but letting nonnegativity be added when the variable is declared
> would be great.
>
> Might it make sense to add a type of variable (ie, "continuous", "integer",
> "binary", "nonnegative")? One disadvantage is that nonnegative continuous
> is different than nonnegative integer.

Or at least it could be a shortcut to "nonnegative + continuous".

p.new_variable(nonnegative=True) could be cool indeed.

> One additional comment: The set_min (and set_max) functionality is still
> needed, even if there is a way to indicate bounds when declaring variables.
> One situation is for indexed variables where they had different bounds.
> Another situation occurs when "fixing" a variable to a value after the
> program has been created. For instance, an IP might model finding a maximum
> independent set in a graph, but I might wish to ask about independent sets
> that contain a specific vertex. This is easy to do from the usual IP by
> forcing that variable to 1.

Oh. Right. I add a constraint that b[v] == 1 in this case, but it makes sense.

Nathann

[Stephen Hartke]

On Sat, Dec 14, 2013 at 8:32 AM, Nathann Cohen <nathan...@gmail.com> wrote:

> I frequently use the IP/LP functionality in Sage for problems in graph
> theory.

Hmmm.. I'm *very* glad to learn this :-)

And I appreciate all the work that you and the other Sage developers have put into making the IP/LP functionality in Sage so powerful and easy to use!

> One additional comment: The set_min (and set_max) functionality is still
> needed, even if there is a way to indicate bounds when declaring variables.
> One situation is for indexed variables where they had different bounds.
> Another situation occurs when "fixing" a variable to a value after the
> program has been created.  For instance, an IP might model finding a maximum
> independent set in a graph, but I might wish to ask about independent sets
> that contain a specific vertex.  This is easy to do from the usual IP by
> forcing that variable to 1.

Oh. Right. I add a constraint that b[v] == 1 in this case, but it makes sense.

As Andrey pointed out, bounds on variables are different from other constraints.  My understanding is that solvers deal with variable bounds in a different and more efficient way than other constraints.  This is particularly important when doing branch-and-bound to solve an IP, since the variable being branched on has new bounds placed on it.

Best wishes,

Stephen

[Nathann Cohen]

Helloooooooo everybody !

This is .... almost done ! Almost done, because we can't do anything like that without deprecating stuff for a while (especially when I have no idea how many people use that), so I created ticket #15521.

This adds deprecation warnings to have everybody explicitly say that they want to use nonnegative variables, until we can make "real" variables the default.

Annnnnnnnd it's now waiting for a review ! :-)

http://trac.sagemath.org/ticket/15521

Nathann

--
You received this message because you are subscribed to a topic in the Google Groups "sage-devel" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/3vrPzUqFpM4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sage-devel+...@googlegroups.com.