Making a copy of a MixedIntegerLinearProgram

[Emil]

I would like to solve a large number of very similar linear programs.
More specifically I would like to be able to

1) Create a MixedIntegerLinearProgram, and add some constraints.
2) Keep this MILP somewhere.
3) (Repeated many times) Take a copy of the saved MILP, add a few more
constraints specific to this problem instance, and solve it.

The difficulty I have is that I am unclear how to add new constraints
that include previous variables. Suppose I do

lp = MixedIntegerLinearProgram(maximization=True)
x = lp.new_variable()

Then I do:

nlp = copy(lp)
x = nlp.new_variable()

The variable 'x' now seems to contain different variables. So I cannot
add any constraints that use the existing variables. Or is there some
way to do this? Thanks,

Emil

[Nathann Cohen]

Hellooooooo Emil !!!

Well, I just tried something and it ended upi crashing Sage, so I can just advise you to create all your variables in the first LP from the start, *then* to copy the MixedIntegerLinearProgram object. Of course it is a bad answer :-)

John Perry was the one who needed this copy() feature for MILP and he was doing things similar to the ones you attempt. As I only had integer programs in mind when I wrote this class (hence hard problems to solve. hence the times it takes to generate the LP is totally small compared to the rest) I am totally ready to admit that it is not very suited to such computations. Dima mentionned recently that we may create some "LinearProgram" class at some point which would be thought *for* this type of problems, but I would fint it hard to write it myself considering that that would not be a user of it.... Hence no clue of what should be possible or not with it :-)

Nathann

[Nathann Cohen]

By the way, could I ask you what lead you to create and solve many LP ? I mean, what are you solving which requires you to do that ? ^^;

Nathann

[Emil]

Hi Nathann,

Thanks for writing the MILP class - it works very well. Now, I can do:

x = lp.new_variable()

Is there any way to do something like

x = lp.get_existing_variables()

?

I'm working on some graph theoretic stuff: I'm solving two LPs for
each graph, for as many graphs as I can. - Emil.

> --
> To post to this group, send email to sage-s...@googlegroups.com
> To unsubscribe from this group, send email to
> sage-support...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/sage-support
> URL: http://www.sagemath.org

[john_perry_usm]

On Monday, May 14, 2012 7:32:25 PM UTC-5, Emil wrote:

lp = MixedIntegerLinearProgram(maximization=True)
x = lp.new_variable()

Then I do:

nlp = copy(lp)
x = nlp.new_variable()

The variable 'x' now seems to contain different variables. So I cannot
add any constraints that use the existing variables. Or is there some
way to do this? Thanks,

x *should* contain different variables, for two reasons. First, nlp already has a variable (a copy of the one you created for lp), so if you ask nlp to create a new variable for it, it won't return the variable lp created earlier.

Second, after copying lp to nlp, you might want to change some variables in one from real to integer, or vice-versa.

Also, I don't think Sage has ever let you create variables & add constraints that way. I don't know why, but if I want a variable with a compact notation, I've found MILP lets you do it this way:

    sage: x, y = lp[0], lp[1]

but NOT

    sage: x, y = lp.new_variable(), lp.new_variable()

You'll get variables alright, but you can't add constraints using the second. The first works fine.

To add constraints, I usually do the following:

    sage: lp = MixedIntegerLinearProgram(maximization=False)
    sage: lp.add_constraint(2*lp[0] + 3*lp[1] <= 1)
    sage: nlp = copy(lp)
    sage: nlp.add_constraint(3*lp[0] - 2*lp[1] <= 1)

Or, if you like, use x, y, etc., defining them as I did above (the FIRST way).

regards
john perry

[Emil]

On 15 May 2012 13:38, john_perry_usm <john....@usm.edu> wrote:
>I've found MILP lets you do it this way:
>
>     sage: x, y = lp[0], lp[1]

Ahh! Thanks, this is what I need. (Is this documented anywhere?) - Emil

[Emil]

Next issue is that the Gurobi backend doesn't support the copy:

AttributeError: 'sage.numerical.backends.gurobi_backend.GurobiBacke'
object has no attribute 'copy'

Any idea how much work this would be to do?

(I can now do what I wanted to do before, at least with GLPK.)

Emil

[Nathann Cohen]

Hellooooooo !!

> Next issue is that the Gurobi backend doesn't support the copy:

Oops ^^;

> Any idea how much work this would be to do?

Oh, it's usually quite straightforward to implement such things.
Usually the feature already exists in the solver's C api, and all the
work that needs to be done is to expose it in Sage :-)

Nathann

[Emil]

On 15 May 2012 15:21, Nathann Cohen <nathan...@gmail.com> wrote:
> Oh, it's usually quite straightforward to implement such things.
> Usually the feature already exists in the solver's C api, and all the
> work that needs to be done is to expose it in Sage :-)

Any chance you could make a patch? :) (I'd volunteer myself, but I
would probably mess it up!)

Emil

[Nathann Cohen]

Helloooooooo Emil !!

> Any chance you could make a patch? :)   (I'd volunteer myself, but I
> would probably mess it up!)

Hmmmm.... I could, but this patch is so local that it really is an
ideal occasion to write your first patch... Are you sure you do not
want to give it a try ? It is fun to be a developper, you will feel
like Sage becomes your home directory, and everybody will throw rocks
at you you create new bugs...... And all all the while you will be
having fun :-D

Nathann

[Emil]

OK I'll take a look :)