[Coin-discuss] FLOPC++

[Tim Hultberg]

Hi,

I have implemented a C++ class library, FLOPC++, for algebraic
modelling of linear optimization problems (LP/MIP), which I would like
to contribute to COIN-OR, if there is an interest.

The purpose of the class library is to provide modelling facilities
similar to algebraic modelling languages such as GAMS and AMPL
directly within C++ programs, which can give several advantages in terms
of integration with other software, etc. 

In bringing modelling facilities to C++, FLOPC++ is in some sense
similar to Concert Technology (CT) from ILOG. There is however some major
differences:

   * Unlike FLOPC++, CT supports constraint programming.

   * Unlike CT, FLOPC++ provides a truly declarative modelling notation
     (as traditional modelling languages).

   * Unlike CT, FLOPC++ supports "sparse" variables, constraints and data.

   * Unlike CT, FLOPC++ communicates with the solver through the COIN-OSI
     interface. 


To illustrate what is it all about, here is a small example:

#include "flopc.hpp"

void transportModel(
    MP_set& S,
    MP_set& D,
    MP_subset<2>& link, 
    MP_data& capacity, 
    MP_data& dem, 
    MP_data& d, 
    double f
) {
    MP_data c(link);

    MP_index i,j;

    forall( link(i,j), c(link(i,j)) = f * d(link(i,j)) / 1000.0 );

    MP_variable  x(link);

    MP_constraint supply(S),demand(D);

    supply(S(i)) = sum( link(i,j), x(link(i,j))) <= capacity(i); 

    demand(D(j)) = sum( link(i,j), x(link(i,j))) >= dem(j);  

    minimize( sum(link(i,j), c(link(i,j)) * x(link(i,j))) );

    x.display("Optimal solution");
}

main() {
    enum  {seattle,sandiego,numS}; 
    enum  {newyork,chicago,topeka,numD};

    MP_set S(numS);
    MP_set D(numD);

    MP_subset<2> link(S,D);

    MP_data capacity(S); 
    MP_data dem(D); 

    link.insert(seattle,newyork);
    link.insert(seattle,chicago);
    link.insert(sandiego,chicago);
    link.insert(sandiego,topeka);
    //   link.insert(seattle,topeka);   NB.  No link
    //   link.insert(sandiego,newyork); NB.  No link

    MP_data d(link);

    capacity(seattle)=350;  capacity(sandiego)=600;
    dem(newyork)=325;  dem(chicago)=300;  dem(topeka)=275;

    d(link(seattle,newyork))= 2.5;  
    d(link(seattle,chicago))= 1.7;  
    d(link(sandiego,chicago))= 1.8;  
    d(link(sandiego,topeka)) = 1.4;
    //    d(sandiego,newyork)= 2.5;  NB.  No link
    //    d(seattle,topeka) = 1.8;   NB.  No link

    transportModel(S,D,link,capacity,dem,d,90);
} 


It is possible to define several independent models (MP_model), but to
simplify the formulation of small models a default model
(MP_model::default_model) is implicitly used in the example above.

Note the formulation of the two constraints:
    supply(S(i)) = sum( link(i,j), x(link(i,j))) <= capacity(i); 
and
    demand(D(j)) = sum( link(i,j), x(link(i,j))) >= dem(j);  
In the first summation over the "sparse" set link(i,j) the dummy index i is
bound by the constraint being defined, whereas in the similar
summation in the second constraint the other dummy index j is
bound. This handy notation for "slices" of sparse compound sets is
similar to AMPL. 

(Unlike most traditional modelling languages) It is currently NOT
possible to write x(i,j) instead of x(link(i,j)) when referring to a
variable (/data/constraint) defined over a "sparse" set. But I am
planning to implement this as well as other improvements.

A previous version of the library is described in:
   Tim Hultberg: "Formulation of Linear Optimization Problems in C++",
   ed. Soeren S. Nielsen "Programming Languages and Systems in
   Computational Economics and Finance", Kluwer Academic Press, 2002.
However, in this version the library has been complety rewritten in
order to support "sparse" sets.


Best regards, 
                          Tim Hultberg