COIN-OR::LEMON - Graph Library

Opened 16 years ago

Closed 15 years ago

#44 closed task (fixed)

Port the LP interface

Reported by: Alpar Juttner Owned by: Balazs Dezso
Priority: critical Milestone: LEMON 1.1 release
Component: core Version:
Keywords: Cc:
Revision id:

Description (last modified by Alpar Juttner)

The following files are affected:

  • lemon/lp_base.h
  • lemon/lp_base.cc
  • lemon/lp.h
  • lemon/lp_skeleton.h
  • lemon/lp_skeleton.cc
  • lemon/bits/lp_id.h
  • lemon/lp_utils.cc
  • lemon/lp_utils.h
  • lemon/lp_glpk.h
  • lemon/mip_glpk.h
  • lemon/lp_glpk.cc
  • lemon/mip_glpk.cc
  • lemon/lp_cplex.h
  • lemon/mip_cplex.h
  • lemon/lp_cplex.cc
  • lemon/mip_cplex.cc
  • lemon/lp_soplex.h
  • lemon/lp_soplex.cc
  • test/lp_test.cc
  • test/mip_test.cc
  • m4/lx_check_soplex.m4 (already ported)
  • m4/lx_check_cplex.m4 (already ported)
  • m4/lx_check_glpk.m4 (already ported)
  • demo/lp_maxflow_demo.cc
  • demo/lp_demo.cc

We should also consider restructuring these files.

Attachments (8)

aa6dff56b2e1.patch (186.4 KB) - added by Balazs Dezso 15 years ago.
Under development version of lp port
lp_inheritance.png (3.1 KB) - added by Balazs Dezso 15 years ago.
lp-classes.png (23.1 KB) - added by Alpar Juttner 15 years ago.
lp_inheritance.2.png (6.6 KB) - added by Balazs Dezso 15 years ago.
Fixed names
lp.bundle (44.6 KB) - added by Balazs Dezso 15 years ago.
New version
9347462c3106.patch (49.3 KB) - added by Balazs Dezso 15 years ago.
Next iteration
473d56c5aec8.patch (46.9 KB) - added by Balazs Dezso 15 years ago.
Documentation improvements
lp-3aca3bcdf9e1.patch (5.1 KB) - added by Peter Kovacs 15 years ago.

Download all attachments as: .zip

Change History (38)

comment:1 Changed 16 years ago by Alpar Juttner

Description: modified (diff)

comment:2 Changed 16 years ago by Alpar Juttner

Description: modified (diff)

comment:3 Changed 16 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:4 Changed 16 years ago by Balazs Dezso

The LP and MIP structure should be organized different way:

  • The Mip solver inherits from Lp which is very bad idea, for example now it is possible to ask the Mip solver from primal and dual solution, or all control parameters (which should be used in interface) for Lp could be changed from Mip solver, etc.
  • I think there should be a base class, which contains a linear programming problem (SolverBase?). It should responsible for setting the constraints, variables and objective function.
  • The LpSolverBase? and the MipSolverBase? should be inherited virtually from SolverBase?, these contain interface for solving the problem and retrieving the solution, and functions setting column type in MipSolverBase?.
  • The GlpkSolverBase? should inherited virtually from SolverBase? and implement all pure virtual methods defined in SolverBase?.
  • The LpGlpk? should inherited from LpSolverBase? and GlpkSolverBase? and it implements pure virtual methods defined in LpSolverBase?.

The new structure would provide more flexible and cleaner structure:

comment:5 Changed 16 years ago by Balazs Dezso

Owner: changed from Alpar Juttner to Balazs Dezso

comment:6 Changed 15 years ago by Alpar Juttner

Priority: majorcritical

Changed 15 years ago by Balazs Dezso

Attachment: aa6dff56b2e1.patch added

Under development version of lp port

comment:7 Changed 15 years ago by Balazs Dezso

The patch [aa6dff56b2e1] contains a working version of LP port, however it is heavily under development. Unfortunately, I forgot to create the basic port revision, but I will do it with some reverse engineering.

Currently a lot of things changed:

  • The class structure
  • The ID handling
  • The expressions
  • The basic interface
  • Some result retrieving functions
  • Some setting functions
  • Cplex env handling
  • etc....

So please comment the current changes, and advice what could be made better way?

I have also some troubles, where I cannot decide.

  • An LP problem can be categorized into classes, and similarly the primal problem and the dual problem have a type. In addition, the current solution status also can be described. What is the best interface to get type and/or status?
  • How to handle such situations, where the solver does not provide the whole information need by the interface? For example the rays cannot be computed with every solver, assertion, exception should be used? In this case, the ray can be computed with a new optimization problem.
  • With which versions of solvers have to be compatible, for example older cplex, and glpk versions?
  • The documentation should be also improved.

comment:8 in reply to:  7 ; Changed 15 years ago by Alpar Juttner

Replying to deba:

The patch [aa6dff56b2e1] contains a working version of LP port,

For me it does not compile:

 g++ -DHAVE_CONFIG_H -I. -I. -g -O2 -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas -MT lemon/lemon_libemon_la-lp_glpk.lo -MD -MP -MF lemon/.deps/lemon_libemon_la-lp_glpk.Tpo -c lemon/lp_glpk.cc -o lemon/lemon_libemon_la-lp_glpk.o
lemon/lp_glpk.cc: In copy constructor ‘lemon::GlpkSolverBase::GlpkSolverBase(const lemon::GlpkSolverBase&)’:
lemon/lp_glpk.cc:38: error: ‘glp_copy_prob’ was not declared in this scope
lemon/lp_glpk.cc: In member function ‘virtual double lemon::LpGlpk::_getPrimalRay(int) const’:
lemon/lp_glpk.cc:655: error: ‘glp_get_unbnd_ray’ was not declared in this scope
lemon/lp_glpk.cc: In member function ‘virtual double lemon::LpGlpk::_getDualRay(int) const’:
lemon/lp_glpk.cc:706: error: ‘glp_get_unbnd_ray’ was not declared in this scope
make: *** [lemon/lemon_libemon_la-lp_glpk.lo] Error 1
make: *** Waiting for unfinished jobs....

comment:9 in reply to:  7 ; Changed 15 years ago by Alpar Juttner

Replying to deba:

The patch [aa6dff56b2e1] contains a working version of LP port, however it is heavily under development.

Here is some naive observations:

  • I find the name of SolverBase too general. What about calling it LpBase or LpSolverBase instead?
  • I miss a solve() method (or something similar) from the class SolverBase. Is that intentional
  • I can't find an interface for querying the solution neither in SolverBase nor in e.g. LpGlpk
  • I find the MipSolverBase interface a bit bloated. Do we really need all the three way for declaring that a variable is integer or not?

comment:10 in reply to:  8 ; Changed 15 years ago by Balazs Dezso

Replying to alpar:

Replying to deba:

The patch [aa6dff56b2e1] contains a working version of LP port,

For me it does not compile:

 g++ -DHAVE_CONFIG_H -I. -I. -g -O2 -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas -MT lemon/lemon_libemon_la-lp_glpk.lo -MD -MP -MF lemon/.deps/lemon_libemon_la-lp_glpk.Tpo -c lemon/lp_glpk.cc -o lemon/lemon_libemon_la-lp_glpk.o
lemon/lp_glpk.cc: In copy constructor ‘lemon::GlpkSolverBase::GlpkSolverBase(const lemon::GlpkSolverBase&)’:
lemon/lp_glpk.cc:38: error: ‘glp_copy_prob’ was not declared in this scope
lemon/lp_glpk.cc: In member function ‘virtual double lemon::LpGlpk::_getPrimalRay(int) const’:
lemon/lp_glpk.cc:655: error: ‘glp_get_unbnd_ray’ was not declared in this scope
lemon/lp_glpk.cc: In member function ‘virtual double lemon::LpGlpk::_getDualRay(int) const’:
lemon/lp_glpk.cc:706: error: ‘glp_get_unbnd_ray’ was not declared in this scope
make: *** [lemon/lemon_libemon_la-lp_glpk.lo] Error 1
make: *** Waiting for unfinished jobs....

These functions are quite new in glpk, it comes from 4.33 version.

comment:11 in reply to:  10 Changed 15 years ago by Alpar Juttner

Replying to deba:

These functions are quite new in glpk, it comes from 4.33 version.

The glpk version should be checked by the configure script.

Changed 15 years ago by Balazs Dezso

Attachment: lp_inheritance.png added

comment:12 in reply to:  9 ; Changed 15 years ago by Balazs Dezso

Replying to alpar:

  • I find the name of SolverBase too general. What about calling it LpBase or LpSolverBase instead?
  • I miss a solve() method (or something similar) from the class SolverBase. Is that intentional
  • I can't find an interface for querying the solution neither in SolverBase nor in e.g. LpGlpk

The lp_inheritance.png shows the class design of the current implementation (the names are slightly differ). The SolverBase? contain the common part of Mip and Lp interface, while separate classes contain the specialized parts. If you would like to use a general lp solver in an algorithm, currently the LpBase?(LpSolverBase?) reference should be passed as parameter, similarly MipBase?(MipSolverBase?) instead of SolverBase?. The advantage of this solution is that the Mip solver does not contain Lp related functions (primal-dual solution, basis access, etc.). We have one more choice, the SolverBase? also could contain some solver and solution retrieving function(basically one solve() function and getting the column results and objective value result), however I'm not sure that it is a good decision. What is your opinion?

  • I find the MipSolverBase interface a bit bloated. Do we really need all the three way for declaring that a variable is integer or not?

Ok, I think we can hold just the colType() functions.

Changed 15 years ago by Alpar Juttner

Attachment: lp-classes.png added

comment:13 in reply to:  12 ; Changed 15 years ago by Alpar Juttner

Replying to deba:

The lp_inheritance.png shows the class design of the current implementation (the names are slightly differ). The SolverBase? contain the common part of Mip and Lp interface, while separate classes contain the specialized parts. If you would like to use a general lp solver in an algorithm, currently the LpBase?(LpSolverBase?)

I'm confused now. There is neither LpBase nor LpSolverBase in the port you sent ([aa6dff56b2e1]), see lp-classes.png showing the generated class inheritance diagram.

Anyhow, then name of SolverBase is just too general. There are so many other "solvers" beyond LP/MIP, which need completely different interfaces.

comment:14 in reply to:  13 ; Changed 15 years ago by Peter Kovacs

Replying to alpar:

I'm confused now. There is neither LpBase nor LpSolverBase in the port you sent ([aa6dff56b2e1]), see lp-classes.png showing the generated class inheritance diagram.

Balazs wrote wrong (but similar) class names on the image. He used the names LpBase, MipBase, GlpkBase instead of LpSolverBase, MipSolverBase and GlpkSolverBase, respectively, and used GlpkLp, GlpkMip instead of LpGlpk and MipGlpk respectively.

I copied the following lines from his changeset:

  • class LpSolverBase : virtual public SolverBase
  • class MipSolverBase : virtual public SolverBase
  • class GlpkSolverBase : virtual public SolverBase
  • class LpGlpk : public GlpkSolverBase, public LpSolverBase
  • class MipGlpk : public GlpkSolverBase, public MipSolverBase

It is the same as your inheritance diagram with the exception that LpSolverBase class is somehow missing from the diagram. (The relation noted in the first line of the above list is missing from the diagram, but it can be found at line 1568 in lp_base.h in [aa6dff56b2e1]).

Changed 15 years ago by Balazs Dezso

Attachment: lp_inheritance.2.png added

Fixed names

comment:15 in reply to:  14 ; Changed 15 years ago by Alpar Juttner

Replying to kpeter:

Replying to alpar:

I'm confused now. There is neither LpBase nor LpSolverBase in the port you sent ([aa6dff56b2e1]), see lp-classes.png showing the generated class inheritance diagram.

Balazs wrote wrong (but similar) class names on the image. He used the names LpBase, MipBase, GlpkBase instead of LpSolverBase, MipSolverBase and GlpkSolverBase, respectively, and used GlpkLp, GlpkMip instead of LpGlpk and MipGlpk respectively.

I copied the following lines from his changeset:

  • class LpSolverBase : virtual public SolverBase
  • class MipSolverBase : virtual public SolverBase
  • class GlpkSolverBase : virtual public SolverBase
  • class LpGlpk : public GlpkSolverBase, public LpSolverBase
  • class MipGlpk : public GlpkSolverBase, public MipSolverBase

It is the same as your inheritance diagram with the exception that LpSolverBase class is somehow missing from the diagram.

I typically read only the documentation for the very first review, and I would like to keep this habit. So, if the doxygen tell me that LpSolverBase is not there, then I consider it to be missing from the commits.

The same applies to the missing part of the interface (the solve() method (or something similar) from the class SolverBase and the interface for querying the solution either in SolverBase or in e.g. LpGlpk)

comment:16 Changed 15 years ago by Balazs Dezso

Status: newassigned

comment:17 in reply to:  15 ; Changed 15 years ago by Alpar Juttner

Balazs, could you fix the doc so that all relevant classes and member functions will be visible in the doc?

Changed 15 years ago by Balazs Dezso

Attachment: lp.bundle added

New version

comment:18 in reply to:  17 ; Changed 15 years ago by Balazs Dezso

Replying to alpar:

Balazs, could you fix the doc so that all relevant classes and member functions will be visible in the doc?

I made it in the lp.bundle. The bundle contains also the basic port of the lp related stuffs. I also renamed some classes. I hope, the basic structure and the naming convention of the solvers are acceptable, and just the documentation and some details should be polished yet.

comment:19 in reply to:  18 ; Changed 15 years ago by Alpar Juttner

Replying to deba:

I made it in the lp.bundle. The bundle contains also the basic port of the lp related stuffs. I also renamed some classes. I hope, the basic structure and the naming convention of the solvers are acceptable, and just the documentation and some details should be polished yet.

Two short comments:

  • I still dislike to the name SolverBase, as it is too general. There are much more "solvers" than the LP/MIP related ones.
  • Now operator*() is used to obtain the constant component of an Expr. I don't like it either. Instead, I would use (the binary version) operator*(Expr, Expr) for computing the dot product of two expressions. For example, in this way you could substitute a solution into a constraint. Syntactically, this would not conflict the current usage of operator*, but I find it confusing. If you don't, then we can keep it.

comment:20 in reply to:  19 ; Changed 15 years ago by Peter Kovacs

Replying to alpar:

Two short comments:

  • I still dislike to the name SolverBase, as it is too general. There are much more "solvers" than the LP/MIP related ones.

I agree. A more specific name would be better. What about LinearSolverBase or LpMipSolverBase or LpMipBase?

  • Now operator*() is used to obtain the constant component of an Expr. I don't like it either.

It is strange for me, too.

Another suggestion (according to our email discussion): in SolverBase::Expr using ColIt and ConstColIt would be better than MapIt and ConstMapIt. Similarly DualExpr::(Const)MapIt --> DualExpr::(Const)RowIt.

comment:21 Changed 15 years ago by Peter Kovacs

Btw. we should collect the all the renamings related to the LP tools in order to extend the migration guide and script.

comment:22 in reply to:  20 ; Changed 15 years ago by Balazs Dezso

Replying to kpeter:

Replying to alpar:

Two short comments:

  • I still dislike to the name SolverBase, as it is too general. There are much more "solvers" than the LP/MIP related ones.

I agree. A more specific name would be better. What about LinearSolverBase or LpMipSolverBase or LpMipBase?

I suggest the following renaming: SolverBase? -> LpBase?, LpBase? -> LpSolver?, MipBase? -> MipSolver?. What is your opinion? I like only the LinearSolverBase? from the suggested names, but maybe the newly proposed names are better.

  • Now operator*() is used to obtain the constant component of an Expr. I don't like it either.

It is strange for me, too.

I had the idea, that the expressions are similar to the arrays. For the arrays, we can get the 0th item with operator*(), which could be the constant component of the expression. Maybe it was a bad idea.

Another suggestion (according to our email discussion): in SolverBase::Expr using ColIt and ConstColIt would be better than MapIt and ConstMapIt. Similarly DualExpr::(Const)MapIt --> DualExpr::(Const)RowIt.

I like rather the CoeffIt? and ConstCoeffIt?.

Other question, the SolverBase? don't contain solve() and problem retrieving functions, don't we need it?

comment:23 in reply to:  22 ; Changed 15 years ago by Alpar Juttner

Replying to deba:

I suggest the following renaming: SolverBase? -> LpBase?, LpBase? -> LpSolver?, MipBase? -> MipSolver?. What is your opinion? I like only the LinearSolverBase? from the suggested names, but maybe the newly proposed names are better.

And what about the "default LP" typedef? How would you call it?

  • Now operator*() is used to obtain the constant component of an Expr. I don't like it either.

It is strange for me, too.

I had the idea, that the expressions are similar to the arrays. For the arrays, we can get the 0th item with operator*(), which could be the constant component of the expression. Maybe it was a bad idea.

Not necessarily. My concern was that it may conflict (semantically) with the other (future) meaning of operator*(). What do you think of it?

On the other hand, we can also use operator() for the dot product, (i.e. is c and x are expressions, then c(x) (and x(c) would mean the dot product of them).

Other question, the SolverBase? don't contain solve() and problem retrieving functions, don't we need it?

solve() should return something indicating the type of the obtained solution. Can it be of the same type for LP and MIP?

comment:24 in reply to:  23 Changed 15 years ago by Balazs Dezso

Replying to alpar:

Replying to deba:

I suggest the following renaming: SolverBase? -> LpBase?, LpBase? -> LpSolver?, MipBase? -> MipSolver?. What is your opinion? I like only the LinearSolverBase? from the suggested names, but maybe the newly proposed names are better.

And what about the "default LP" typedef? How would you call it?

It could remain Lp and Mip, as they are in the SVN releases.

  • Now operator*() is used to obtain the constant component of an Expr. I don't like it either.

It is strange for me, too.

I had the idea, that the expressions are similar to the arrays. For the arrays, we can get the 0th item with operator*(), which could be the constant component of the expression. Maybe it was a bad idea.

Not necessarily. My concern was that it may conflict (semantically) with the other (future) meaning of operator*(). What do you think of it?

On the other hand, we can also use operator() for the dot product, (i.e. is c and x are expressions, then c(x) (and x(c) would mean the dot product of them).

Other question, the SolverBase? don't contain solve() and problem retrieving functions, don't we need it?

solve() should return something indicating the type of the obtained solution. Can it be of the same type for LP and MIP?

The solve() functions return now SolveExitStatus?, which gives back whether the solving were successful, or not. It can be common for both solver type. In addtion, the sol() and the solValue() functions can be synonyms for primal() and primalValue() in the LP side.

Changed 15 years ago by Balazs Dezso

Attachment: 9347462c3106.patch added

Next iteration

comment:25 Changed 15 years ago by Balazs Dezso

I have uploaded a new patch [9347462c3106]. It contains renamings, improvements and bug fixes.

Changed 15 years ago by Balazs Dezso

Attachment: 473d56c5aec8.patch added

Documentation improvements

comment:26 Changed 15 years ago by Balazs Dezso

I have uploaded the patch [473d56c5aec8], which contains lot of documentation improvements, and a minor bug fix, and some interface change (see commit log).

comment:27 in reply to:  26 ; Changed 15 years ago by Alpar Juttner

Replying to deba:

I have uploaded the patch [473d56c5aec8], which contains lot of documentation improvements, and a minor bug fix, and some interface change (see commit log).

The patches do not compile as lemon/bits/solver_bits.h seems to be missing.

comment:28 in reply to:  27 Changed 15 years ago by Peter Kovacs

Replying to alpar:

The patches do not compile as lemon/bits/solver_bits.h seems to be missing.

Could we fix it? It would be important to push these changesets to the main branch as soon as it possible.

Changed 15 years ago by Peter Kovacs

Attachment: lp-3aca3bcdf9e1.patch added

comment:29 in reply to:  27 Changed 15 years ago by Peter Kovacs

Replying to alpar:

The patches do not compile as lemon/bits/solver_bits.h seems to be missing.

[3aca3bcdf9e1] adds the missing file, so the patches can be compiled.

comment:30 Changed 15 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

The port and the reworked version went to the main, reorganized to [7afc121e0689] and [ed54c0d13df0]. In addition [76ec7bd57026] bypasses warnings with emitted by gcc 4.3.

Finally, [08d495d48089] renames the header files by removing the lp_ prefixes and [9b082b3fb33f] changes Lp*/Mip* to *Lp/*Mip.

I guess I can close the ticket.

Note: See TracTickets for help on using tickets.