[Coin-discuss] Problem in Osi/Clp...

Sat Apr 1 03:52:52 EST 2006

Mathieu,

Maximization should be OK now.

I think writeLP behavior is deliberate as Francois Margot's readLp converts
to minimization.  If you explicitly set objsense to 1.0 in call to writeLp
you should get objective flipped (and minimization written).  If you feel
strongly enough about it, post remark about writeLP to Coin-discuss and let
Francois Margot sort it out.

John Forrest

             mathieu lacroix                                               
             <mathieu.lacroix@                                             
             isima.fr>                                                  To 
                                       John J Forrest/Watson/IBM at IBMUS     
             03/31/06 12:22 PM                                          cc 

                                                                   Subject 
             Please respond to         Re: [Coin-discuss] Problem in       
             coin-discuss at list         Osi/Clp...                          
               .coin-or.org                                                

Hi,

I'm writting an e-mail for three different things. First, thank you for
your answer to my problem.  I'm now able to  solve my integer  problem with
Osi/Clp. And Coin-or is now used in linear programming lesson. But it seems
to stay some mistakes. The first one is that branchAndBound() in clp seems
to work only with minimization problem. With my little example, if I try to
solve my maximization problem, it doesn't work at all. The solution is not
optimal. I have to write my problem as an minimization one. To show you
this bug, I attach the program in this e-mail. If you run it keeping
comments (so just minization problem), the program will display  (which is
the optimal solution) :
The integer optimal solution is:
  a0 = 0
  a1 = 100
  a2 = 0
  a3 = 3
  objective value = -103

But, now, if you uncomment the line for maximization resolution, the both
"optimal" solutions found will be :
The integer optimal solution is:
  a0 = 0
  a1 = 82
  a2 = 1
  a3 = 2
  objective value = -85

This two solutions are different although problems are the same. And if you
try to solve minimization problem and then maximization one, there will be
some troubles :
Appel de la methode OsiClpSolverInterface::branchAndBound()
The LP relaxation is infeasible
terminate called after throwing an instance of 'CoinError'
Abandon

I have found another little mistake. In the method "writeLp()", even if you
have a minization problem, it is always written in the file "Minimization"
instead of "Maximization (you can check it by opening after running my
program the two files : minimizationProblem.lp and maximizationProblem.lp.

Thank you for your work.

Best regards,

Mathieu LACROIX

mathieu lacroix wrote:

            Hi,

            I want to use the module CLP and OSI for teaching in
            university. The instruction is linear programming. But in the
            problem they have to solve, there is some part of integer
            linear programming. As it isn't an integer linear programming
            lesson and as the ILP they have to solve is very very small, I
            would like to solve it using only the modules OSI/CLP. I have
            seen that object OsiXxxInterfaceSolver has a member
            branchAndBound() (It is exactly what I search!). But it seems
            to not work with CLP (but with CPLEX). So, I want to know how
            to do with CLP/COIN, since I don't want to use something like
            BCP which is too complex for the use I need in teaching.

            Best regards,

            Mathieu LACROIX
            _______________________________________________
            Coin-discuss mailing list
            Coin-discuss at list.coin-or.org
            http://list.coin-or.org/mailman/listinfo/coin-discuss

--
Mathieu LACROIX
mathieu.lacroix at isima.fr
Université Blaise Pascal - Clermont Fd II
Laboratoire LIMOS
Bâtiment ISIMA - Bureau D112
Complexe scientifique des Cézeaux
63 177 Aubière, Cedex - France
Tel : 04.73.40.79.48
Fax : 04.73.40.76.39
#ifdef COIN_USE_CLP
#include "OsiClpSolverInterface.hpp"
typedef OsiClpSolverInterface OsiXxxSolverInterface;
#endif

#include "CoinPackedVector.hpp"
#include "CoinPackedMatrix.hpp"

#include <iostream>
using namespace std;

//We want to solve this integer linear problem using Osi and Clp with the
method branchAndBound()

//   Maximize
//      x0 + x1 + x2 + x3
//
//    Subject To
//      45 x0 + 0.50000 x1 + 31 x2 + 14 x3 <= 100
//
//    Bounds
//      0 <= x0 <= 100
//      0 <= x1 <= 100
//      0 <= x2 <= 100
//      0 <= x3 <= 100
//
//    Integers
//      x0 x1 x2 x3
//    End

int main(int argc, char* argv[])
{
     //We create the problem
     OsiXxxSolverInterface* sub = new OsiXxxSolverInterface();

     int n_cols = 4;
     CoinPackedVector row;

     double * objective    = new double[n_cols];//the objective
coefficients
     double * col_lb       = new double[n_cols];//the column lower bounds
     double * col_ub       = new double[n_cols];//the column upper bounds

     for(int i=0;i<n_cols;i++)
     {
               col_lb[i] = 0.0;
               col_ub[i] = 100.0;
     }
     CoinPackedMatrix * matrix =  new CoinPackedMatrix();
     matrix->setDimensions(0, n_cols);

     int n_rows = 1;
     double * row_lb = new double[n_rows]; //the row lower bounds
     double * row_ub = new double[n_rows]; //the row upper bounds

     row.clear();
     row.insert(0,45.0);
     row.insert(1,0.5);
     row.insert(2,31.0);
     row.insert(3,14);
     matrix->appendRow(row);
     row.clear();

     //Define the objective coefficients.
     for(int i=0;i<4;i++)
               objective[i] =0.0;

     row_lb[0]=-1*sub->getInfinity();
     row_ub[0] = 100.0;

     sub->loadProblem(*matrix, col_lb, col_ub, objective, row_lb, row_ub);
     matrix->clear();

     for(int i=0;i<n_cols;i++)
               sub->setInteger(i);

  double *new_coef_obj =  new double[n_cols];

/*

     //We solve the problem by maximization with all objective coefficients
equal to 1.0
      for(int i=0;i<n_cols;i++)
               new_coef_obj[i]= 1.0;

     sub->setObjective(new_coef_obj);

     sub->setObjSense(-1.0);
     sub->writeLp("maximizationProblem");

     sub->branchAndBound();

     cout << "********************************"<<endl;
     cout << "**Solving maximization problem**" << endl;
     cout << "********************************"<<endl;

     const  double objective_value = sub->getObjValue();
     const  double * solution = sub->getColSolution();

     cout << "\nThe integer optimal solution is:" << endl
               << "  a0 = " << solution[0] << endl
               << "  a1 = " << solution[1] << endl
               << "  a2 = " << solution[2] << endl
               << "  a3 = " << solution[3] << endl
               << "  objective value = " << objective_value << endl;

*/

  //We solve the problem by minimization and all objective coefficients
equal to -1.0
     sub->setObjSense(1.0);

     for(int i=0;i<n_cols;i++)
               new_coef_obj[i]=- 1.0;

     sub->setObjective(new_coef_obj);

     sub->writeLp("minimizationProblem");
     sub->branchAndBound();

     cout << "********************************"<<endl;
     cout << "Solving minimization problem" << endl;
     cout << "********************************"<<endl;

     const double  objective_value2 = sub->getObjValue();
     const double* solution2 = sub->getColSolution();

     cout << "\nThe integer optimal solution is:" << endl
               << "  a0 = " << solution2[0] << endl
               << "  a1 = " << solution2[1] << endl
               << "  a2 = " << solution2[2] << endl
               << "  a3 = " << solution2[3] << endl
               << "  objective value = " << objective_value2 << endl;

     return 0;
}