make LP return bounds on variables

[dimpase]

Currently there is no bulletproof way to find the lower and the upper bounds on the variables of an LP, as some variables can be added by the backend on the fly, etc. However, this (often crucial!) information is readily available from the backend. Hence the patch attached.

UPDATE:
OK, I was convinced by Nathann that this is not needed.

Depends on #13148

CC: @ppurka

Component: linear programming

Reviewer: Dmitrii Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/13205

[nathanncohen]

comment:1

Do you have something different from http://goo.gl/HEUdk in mind ?

[dimpase]

make (I)LP return bounds on variables

[dimpase]

comment:2

Attachment: trac_13205_LP_return_bounds_on_variables.patch.gz

Replying to @nathanncohen:

Do you have something different from http://goo.gl/HEUdk in mind ?

I don't want to access variables via dictionaries, as this is flaky.
E.g. think of that extra variables Gurobi adds on the fly, one can't put hands on them at all.

[nathanncohen]

comment:5

Yep, but then we would have two ways to do the same thing, with methods that take different arguments. What about changing get_min and get_max so that they accept integers instead ?

All that would need to be added is a type check : if the given value is a MIPVariable type then the old code (one line) is used, and otherwise the backend function is called.

Actually, the only line that this function contains is

return self._backend.variable_lower_bound(self._variables[v])

That is : first take the integer corresponding to the variable, then return the value. More or less what you want to do too :-P

Nathann

[dimpase]

comment:6

Replying to @nathanncohen:

Yep, but then we would have two ways to do the same thing, with methods that take different arguments. What about changing get_min and get_max so that they accept integers instead ?

But then one would also want to have this for set_max() and set_min(), for interface consistency ?

[nathanncohen]

comment:7

Yeah, I guess. Or we can also merge everything into a variable_min and variable_max functions with which you can also set values. What do you think is best ?

[dimpase]

comment:8

Replying to @nathanncohen:

Yeah, I guess. Or we can also merge everything into a variable_min and variable_max functions with which you can also set values. What do you think is best ?

I pondered this question deeply :–) No, it's bad enough that p.get_max(v[9999999]) will always create v[9999999] if it does not exist, instead of throwing ValueError, while p.get_max(9999999) will throw ValueError.

I'd really prefer this two-tier approach, when user-defined variables and solver variables are kept apart interface-wise.

By the way, it also looks strange that v doesn't even know its (I)LP. Or can it be in several LPs at the same time?

[nathanncohen]

comment:9

I pondered this question deeply :–) No, it's bad enough that p.get_max(v[9999999]) will always create v[9999999] if it does not exist, instead of throwing ValueError, while p.get_max(9999999) will throw ValueError.

I know it's ugly, but consider all the LP that only work this way. Honestly, having to declare the variables first would really be a huge mess.

I'd really prefer this two-tier approach, when user-defined variables and solver variables are kept apart interface-wise.

Yeah, but then again it would mean that we need to have two copies of each command, according to how the data is given...

Actually, do you really need to work with MixedIntegerLinearProgam ? It looks like all you want is to access the backend's methods directly, and this you can do if you just deal with GenericBackend.
What about just working with this, and adding to it what you miss from MixedIntegerLinearProgram ?

By the way, it also looks strange that v doesn't even know its (I)LP. Or can it be in several LPs at the same time?

Well, you can mess up with two instances of MixedIntegerLinearProgram so badly that they would have common variables, and this would work, but that would just be for the show :-D

Some time ago I think the variables knew about their LP, but because the LP also knew about the variables it produced a cyclic reference, and Python had to be forced to deallocate the two elements -- I think we removed that not so long ago, while dealing with Cliquer's many memory leaks. Which are fixed in a patch, btw :-)

Nathann

[dimpase]

comment:10

Replying to @nathanncohen:

Actually, do you really need to work with MixedIntegerLinearProgam ? It looks like all you want is to access the backend's methods directly, and this you can do if you just deal with GenericBackend.
What about just working with this, and adding to it what you miss from MixedIntegerLinearProgram ?

OK, I can move this function into GenericBackend.
Would this work for you?

Some time ago I think the variables knew about their LP, but because the LP also knew about the variables it produced a cyclic reference, and Python had to be forced to deallocate the two elements -- I think we removed that not so long ago, while dealing with Cliquer's many memory leaks. Which are fixed in a patch, btw :-)

hmm, I thought that one just cannot have __del__ in these classes, and then they would be garbage-collected just fine...

[nathanncohen]

comment:11

OK, I can move this function into GenericBackend.
Would this work for you?

Well, that's the point : the GenericBackend class already has such methods that let you read/set variables bounds from their ID. And of course at this level everything is done through ID.

hmm, I thought that one just cannot have __del__ in these classes, and then they would be garbage-collected just fine...

Yep, they were garbage-collected but you had to wait for the garbage collector to be called, which is not all the time. A user complained of memory leaks when solving many many many LP in a loop (solving a LP for all graphs on n vertices), and this was one source of problems. When youi remove cyclic dependencies the objects are deallocated without any call to the garbage collector, and in his case it made a difference.

[ppurka]

comment:13

UPDATE: OK, I was convinced by Nathann that this is not needed.

Do you mean to say that this ticket is not needed? If so, this should be closed.

[dimpase]

comment:14

Please give it a positive review, and we'll mark it as won't fix or some such...

[ppurka]

comment:15

Sorry, I must have missed this last message.

[jdemeyer]

comment:16

Please clarify: does something need to be merged or not (if not: set the milestone to sage-duplicate/invalid/wontfix).

[dimpase]

comment:17

Replying to @jdemeyer:

Please clarify: does something need to be merged or not (if not: set the milestone to sage-duplicate/invalid/wontfix).

OK, I was not sure how to do this.

[jdemeyer]

Reviewer: Dmitrii Pasechnik