Opened 10 years ago

Last modified 10 years ago

#10341 closed enhancement

make MIP backend interface more Python-ic — at Version 18

Reported by: malb Owned by: ncohen
Priority: major Milestone: sage-4.6.2
Component: linear programming Keywords: LP, MIP
Cc: ncohen Merged in:
Authors: Martin Albrecht, Nathann Cohen Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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

Change History (21)

Changed 10 years ago by malb

comment:1 Changed 10 years ago by malb

  • Status changed from new to needs_work

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

comment:2 Changed 10 years ago by ncohen

  • Status changed from needs_work to needs_review

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

Changed 10 years ago by ncohen

comment:3 Changed 10 years ago by ncohen

  • Authors changed from Martin Albrecht to Martin Albrecht, Nathann Cohen
  • Description modified (diff)

comment:4 follow-up: Changed 10 years ago by malb

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

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

comment:6 in reply to: ↑ 4 Changed 10 years ago by ncohen

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

comment:7 in reply to: ↑ 5 Changed 10 years ago by ncohen

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

comment:8 Changed 10 years ago by malb

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()?

comment:9 Changed 10 years ago by ncohen

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

comment:10 Changed 10 years ago by malb

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

comment:11 Changed 10 years ago by ncohen

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

Nathann

comment:12 follow-up: Changed 10 years ago by malb

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.

comment:13 in reply to: ↑ 12 Changed 10 years ago by ncohen

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

comment:14 Changed 10 years ago by malb

  • Status changed from needs_review to needs_work

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?

comment:15 Changed 10 years ago by ncohen

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

comment:16 follow-up: Changed 10 years ago by malb

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

comment:17 in reply to: ↑ 16 Changed 10 years ago by ncohen

Replying to malb:

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

If you need it for SCIP... :-/

Changed 10 years ago by malb

comment:18 Changed 10 years ago by malb

  • Description modified (diff)
Note: See TracTickets for help on using tickets.