Port the LP interface

[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.

[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:

• The common part for Lp and Mip can be organized to common class GlpkSolverBase?
• The different parts can be split to distinct classes: LpGlpk?, LpInterpGlpk?, MipGlpk?

[Balazs Dezso]

Under development version of lp port

[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.

[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....

[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?

[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.

[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.

[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.

[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.

[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]).

[Balazs Dezso]

Fixed names

[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)

[Alpar Juttner]

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

[Balazs Dezso]

New version

[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.

[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.

[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.

[Peter Kovacs]

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

[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?

[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?

[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.

[Balazs Dezso]

Next iteration

[Balazs Dezso]

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

[Balazs Dezso]

Documentation improvements

[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).

[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.

[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.

[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.

[Alpar Juttner]

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.