[FlopCpp] Using FLOPC++ with GLPK MathProg examples

[Tim Hultberg]

This does indeed look like it is the same model.

My guesses would be, in this order:
1) You looked wrong and changed 3 and 6
2) There is some small difference in the models we havent noticed
3) Your version of GLPK MathProg does not work correctly.

Tim


>>> Greg Geiselhart <geiselha at optonline.net> 30/01/2007 14:19 >>>
Thanks for the fast response Tim. I've included the GLPK model used in
the
comparison below:

#
# This problem finds a least cost shipping schedule that meets
# requirements at markets and supplies at factories.
#
#  References:
#              Dantzig G B, "Linear Programming and Extensions."
#              Princeton University Press, Princeton, New Jersey,
1963,
#              Chapter 3-3.

set I;
/* canning plants */

set J;
/* markets */

param a{i in I};
/* capacity of plant i in cases */

param b{j in J};
/* demand at market j in cases */

param d{i in I, j in J};
/* distance in thousands of miles */

param f;
/* freight in dollars per case per thousand miles */

param c{i in I, j in J} := f * d[i,j] / 1000;
/* transport cost in thousands of dollars per case */

var x{i in I, j in J} >= 0;
/* shipment quantities in cases */

minimize cost: sum{i in I, j in J} c[i,j] * x[i,j];
/* total transportation costs in thousands of dollars */

s.t. supply{i in I}: sum{j in J} x[i,j] <= a[i];
/* observe supply limit at plant i */

s.t. demand{j in J}: sum{i in I} x[i,j] >= b[j];
/* satisfy demand at market j */

data;

set I := Seattle San-Diego;

set J := New-York Chicago Topeka;

param a := Seattle     350
           San-Diego   600;

param b := New-York    325
           Chicago     300
           Topeka      275;

param d :              New-York   Chicago   Topeka :=
           Seattle     2.5        1.7       1.8
           San-Diego   2.5        1.8       1.4  ;

param f := 90;

end;

Greg Geiselhart
email: geiselha at optonline.net 
gmail: geiselha at gmail.com 

-----Original Message-----
From: Tim Hultberg [mailto:Tim.Hultberg at eumetsat.int] 
Sent: Tuesday, January 30, 2007 7:56 AM
To: flopcpp at list.coin-or.org; Greg Geiselhart
Subject: Re: [FlopCpp] Using FLOPC++ with GLPK MathProg examples

When you add more links, the optimal solutions can never get worse,
but
will normally getter better just as you observed with your flopc++
models.

Since you dont include the GLPK model I cant say if its the same or
not.

Tim

>>> Greg Geiselhart <geiselha at optonline.net> 30/01/2007 13:05 >>>
Hi,

I've been investigating the feasibility of converting GLPK MathProg
problems
to FLOPC++. To understand how to convert a MathProg model to FLOPC++,
I
started with a simple comparison of FLOPC++ examples/transport.cpp to
GLPK
examples/transport.mod. In executing both examples, I seem to get
conflicting optimal solutions:

 

*       glpsol calculates an optimal solution of 156.375

*       FLOPC++ calculates an optimal solution of 156.15

 

In looking at transport.cpp, it occurred to me that the problem
statement
may not exactly match the GLPK transport.mod (in transport.cpp,
transportation links do not seem to be defined for Seattle->Topeka and
San
Diego->New York). To test weather this accounted for the solution
differences, I modified transport.cpp to add those links (the code is
shown
below). When the modified transport problem is executed, the optimal
solution is calculated as 153.675. 

 

Can anyone offer an explanation for the difference in calculated
optimal
solutions? It would seem a direct translation of the GLPK
transport.mod
would require the additional links added in the code below. But this
change
seems to increase the discrepancy with GLPK.

 

Thanks in advance for any insights

 

 

int main() {

    MP_model::getDefaultModel().setSolver(new OsiClpSolverInterface);

    enum  {seattle, sandiego, numS};

    enum  {newyork, chicago, topeka,numD};

 

    MP_set S(numS);          // Sources 

    MP_set D(numD);          // Destinations 

    MP_subset<2> Link(S,D);  // Transportation links (sparse subset of
S*D)

 

    Link.insert(seattle,newyork);

    Link.insert(seattle,chicago);

    Link.insert(seattle,topeka);

    Link.insert(sandiego,newyork);

    Link.insert(sandiego,chicago);

    Link.insert(sandiego,topeka);

 

    MP_data SUPPLY(S);

    MP_data DEMAND(D);

 

    SUPPLY(seattle)=350;  SUPPLY(sandiego)=600;

    DEMAND(newyork)=325;  DEMAND(chicago)=300;  DEMAND(topeka)=275;

 

    MP_data COST(Link);

 

    COST(Link(seattle,newyork)) = 2.5;

    COST(Link(seattle,chicago)) = 1.7;

    COST(Link(seattle,topeka)) = 1.8;

    COST(Link(sandiego,newyork))= 2.5;

    COST(Link(sandiego,chicago))= 1.8;

    COST(Link(sandiego,topeka)) = 1.4;

 

    COST(Link) = 90 * COST(Link) / 1000.0;

 

    MP_variable x(Link);

    x.display("...");

 

    MP_constraint supply(S);

    MP_constraint demand(D);

 

    supply.display("...");

 

    supply(S) =  sum( Link(S,D), x(Link) ) <= SUPPLY(S);

    demand(D) =  sum( Link(S,D), x(Link) ) >= DEMAND(D);

 

    cout<<"Here"<<endl;

 

    minimize( sum(Link, COST(Link)*x(Link)) );

/*

    assert(MP_model::getDefaultModel()->getNumRows()==5);

    assert(MP_model::getDefaultModel()->getNumCols()==4);

    assert(MP_model::getDefaultModel()->getNumElements()==8);

    assert(MP_model::getDefaultModel()->getObjValue()>=156.14 &&
MP_model::getDefaultModel()->getObjValue()<=156.16);

*/

    x.display("Optimal solution:");

    supply.display("Supply dual solution");

    cout<<"Test transport passed."<<endl;

}

 

 

Greg Geiselhart

email: geiselha at optonline.net 

gmail: geiselha at gmail.com