make MIP backend interface more Python-ic

[malb]

Sage 4.6.1 will contain a new set of backend classes for mixed integer programming, which will make it easier to write interfaces for other solvers. There has been some off-list discussion about this interface and the follow changes were agreed upon:

• :func: add_linear_constraint should allow lb and ub instead of direction and one bound, it's more expressive.
• :func:add_variable should return the index of the newly created variable instead of the next index.
• change :func:add_linear_constraint to accept any iterable of the form [(c,v) ...]
• min and max should be lower bound (or lb) and upper bound (or ub) to conform to MIP conventions
• allow parameters in :func:add_variable

The patches are to be applied in this order:

• mip_interface_changes.patch
• trac_10431-part2.patch
• trac_10431-part3.patch
• trac_10431-part4.patch
• trac_10431-part5.patch
• trac_10431-part6.patch

CC: @nathanncohen

Component: linear programming

Author: Martin Albrecht, Nathann Cohen

Reviewer: Martin Albrecht, Nathann Cohen

Merged: sage-4.6.2.alpha3

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

[malb]

comment:1

Attachment: mip_interface_changes.patch.gz

The attached patch makes the necessary changes to the GenericBackend and the GLPK class. Coin and CPLEX are not done yet.

[nathanncohen]

comment:2

And here are the modifications to CPLEX and Coin. The doctests pass, plus all the methods of Graph/Digraph/GenericGraph pass with both GLPK, Coin and CPLEX.

I agreed with you patch almost everywhere ! The only modification I made is the "constraints" argument you had placed in the add_constraint method. I really didn't get why you picked this name. I made it "coefficients", as the pairs are actually the coefficient of the sparse matrix, but of course we can discuss it during the review :-)

Nathann

[nathanncohen]

Attachment: trac_10431-part2.patch.gz

[nathanncohen]

Changed author from Martin Albrecht to Martin Albrecht, Nathann Cohen

[malb]

comment:4

Sure, your naming makes much more sense. Are you reviewing mine first, or is your patch your review? I can review your's then?

[malb]

comment:5

I noticed two more interface "issues" we may decide to "fix":

• p.row() returns two lists (indices,coeffs) right now, we could change it to return [(v1,c1),...,(vn,cn)].
• We could allow an optional obj parameter which contains the coefficient of the new variable in the objective function?

Neither of those changes I view as mandatory, just throwing the idea out there to see what others think.

[nathanncohen]

comment:6

Sure, your naming makes much more sense. Are you reviewing mine first, or is your patch your review?

Well, I checked yours while working on it and fixed this "constraints->coefficients" inside of my patch ... If you review mine, both files will have be read by two sets of eyes, so I guess it would count as a valid review :-)

Nathann

[nathanncohen]

comment:7

Replying to @malb:

I noticed two more interface "issues" we may decide to "fix":

• p.row() returns two lists (indices,coeffs) right now, we could change it to return [(v1,c1),...,(vn,cn)].
• We could allow an optional obj parameter which contains the coefficient of the new variable in the objective function?

Neither of those changes I view as mandatory, just throwing the idea out there to see what others think.

Though they sound right... :-)

Nathann

[malb]

comment:8

One more thing: you assume in your interface that one can change column and row names after those have been created. However, this isn't easy in SCIP (I could possibly hack around it by hacking around the API). Can we change that, e.g. by adding name as an optional parameter to add_variable() and add_linear_constraint()?

[nathanncohen]

comment:9

Well, if that's how SCIP's interface is written, I see no way around that .... :-/

I just hope all these optional parameters won't hurt the interface's efficiency. I am eager to have a working stable version of it in Sage, that would let me rebase other patches that have been made invalid because of the work we are doing here. I may spend some time trying to do some performance analysis on the interface afterwards :-D

I'm already sick of these names... They are totally useless for all practical purposes, their only aim is to produce different results in p.show() (which doesn't even use them for the moment) or when writing the LP to files, which is totally orthogonal to actually solving them. Besides, each solver has a different way of managing them, especially Coin. I spent nights just fighting with it, for nothing in the end (oh yes.. it compiles, and there was no regression since the first version of LP.. Who the hell cares ?)

Just to know : are you yourself using names for variables and constraints ?

Nathann

P.S. : Oh, yes.. Let's add this optional argument if there is no way around. If at some point we find a trick, it won't be as hard to remove an optional argument from an interface as any other, as most of the method calls don't include it.

So in the end

[malb]

comment:10

I usually set them (e.g. when converting from polynomial systems), but I guess I'm not really using them usually.

[nathanncohen]

comment:11

So what are they useful for in SCIP ? Can it produce outputs at .lp or .mpw files ?

Nathann

[malb]

comment:12

Yep, and other formats. You can also query a variable (which is a C struct) for its name in your code. For example, you can search for variables by name.

[nathanncohen]

comment:13

Replying to @malb:

Yep, and other formats.

Nice !!

You can also query a variable (which is a C struct) for its name in your code. For example, you can search for variables by name.

Same in GLPK. For the moment, I do not do any work on the matrix once it has been defined. Or rather, I only add more information, but never remove/read anything from it O_o

Nathann

[malb]

comment:14

Okay, what remains to be done then:

• drop setting a variable name by col_name()
• drop setting a constraint name by row_name()
• add an optional parameter name to add_variable and add_linear_constraint
• (optional) make row() return a list [(c1,v1),...,(cn,vn)]
• (optional) add an optional parameter obj to add_variable
• (optional) unify get/set_objective_value

Anything I missed?

[nathanncohen]

comment:15

Oh... Hem.. Actually, if we are to actually drop these methods... -_-

I can not stand these names... Here is the problem : right now, there are no names when you add variables or constraints in MixedIntegerLinearProgram. When p.show() is called, the names are filled with something which makes them at least distinct and recognizable... But if we want to drop these methods, then p.show() has to be rewritten too.. -_-

Nathann

[malb]

comment:16

I would suggest an optional parameter "name=None" for add_variable()?

[jdemeyer]

comment:52

Please fix the commit messages to contain the correct ticket number 10341 on the first line.

[nathanncohen]

Attachment: trac_10431-part4.patch.gz

[nathanncohen]

Attachment: trac_10431-part5.patch.gz

[nathanncohen]

comment:53

Done ! Sorry about that !

Nathann

[jdemeyer]

comment:54

Commit message of first patch still needs to be fixed.

[nathanncohen]

Attachment: mip_interface_changes-fixed_commit_message.patch.gz

[nathanncohen]

comment:55

OOps....

I just uploaded a copy of this one (I can not overwrite it) ^^;

Nathann

[jdemeyer]

comment:56

Please check Sphinx syntax:

docstring of sage.numerical.mip.MixedIntegerLinearProgram.add_constraint:72: (WARNING/2) Literal block expected; none found.

[nathanncohen]

comment:57

Replying to @jdemeyer:

Please check Sphinx syntax:

Right.... Here it is !

Nathann

[nathanncohen]

Attachment: trac_10431-part6.patch.gz

[jdemeyer]

Merged: sage-4.6.2.alpha3