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: |
Description (last modified by )
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 allowlb
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
comment:1 Changed 10 years ago by
- Status changed from new to needs_work
comment:2 Changed 10 years ago by
- 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
comment:3 Changed 10 years ago by
- Description modified (diff)
comment:4 follow-up: ↓ 6 Changed 10 years ago by
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: ↓ 7 Changed 10 years ago by
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
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
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
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
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
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
So what are they useful for in SCIP ? Can it produce outputs at .lp or .mpw files ?
Nathann
comment:12 follow-up: ↓ 13 Changed 10 years ago by
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
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
- 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
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: ↓ 17 Changed 10 years ago by
I would suggest an optional parameter "name=None" for add_variable()?
comment:17 in reply to: ↑ 16 Changed 10 years ago by
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
comment:18 Changed 10 years ago by
- Description modified (diff)
The attached patch makes the necessary changes to the
GenericBackend?
and the
GLPK
class.
Coin
and
CPLEX
are not done yet.