COIN-OR::LEMON - Graph Library

Changeset 1542:0219ee65ffcc in lemon-0.x


Ignore:
Timestamp:
07/07/05 17:00:04 (14 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2037
Message:

Some testing of the LP interface: bugs got fixed.

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/lp_base.h

    r1536 r1542  
    139139    };
    140140
    141       ///\e The type of the investigated LP problem
    142       enum ProblemTypes {
    143           ///Primal-dual feasible
    144           PRIMAL_DUAL_FEASIBLE = 0,
    145           ///Primal feasible dual infeasible
    146           PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1,
    147           ///Primal infeasible dual feasible
    148           PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2,
    149           ///Primal-dual infeasible
    150           PRIMAL_DUAL_INFEASIBLE = 3,
    151           ///Could not determine so far
    152           UNKNOWN = 4
    153       };
     141    ///\e The type of the investigated LP problem
     142    enum ProblemTypes {
     143      ///Primal-dual feasible
     144      PRIMAL_DUAL_FEASIBLE = 0,
     145      ///Primal feasible dual infeasible
     146      PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1,
     147      ///Primal infeasible dual feasible
     148      PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2,
     149      ///Primal-dual infeasible
     150      PRIMAL_DUAL_INFEASIBLE = 3,
     151      ///Could not determine so far
     152      UNKNOWN = 4
     153    };
    154154
    155155    ///The floating point type used by the solver
     
    553553    virtual int _addCol() = 0;
    554554    virtual int _addRow() = 0;
     555    virtual void _eraseCol(int col) = 0;
     556    virtual void _eraseRow(int row) = 0;
    555557    virtual void _setRowCoeffs(int i,
    556558                               int length,
     
    681683    ///\param c is the column to be modified
    682684    ///\param e is a dual linear expression (see \ref DualExpr)
    683     ///\bug This is a temportary function. The interface will change to
     685    ///\bug This is a temporary function. The interface will change to
    684686    ///a better one.
    685687    void setCol(Col c,const DualExpr &e) {
     
    718720    Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
    719721
    720     ///\brief Adds several new row
    721     ///(i.e a variables) at once
     722    ///\brief Add several new rows
     723    ///(i.e a constraints) at once
    722724    ///
    723725    ///This magic function takes a container as its argument
     
    844846      return r;
    845847    }
     848    ///Erase a coloumn (i.e a variable) from the LP
     849
     850    ///\param c is the coloumn to be deleted
     851    ///\todo Please check this
     852    void eraseCol(Col c) {
     853      _eraseCol(cols.floatingId(c.id));
     854      cols.erase(c.id);
     855    }
     856    ///Erase a  row (i.e a constraint) from the LP
     857
     858    ///\param r is the row to be deleted
     859    ///\todo Please check this
     860    void eraseRow(Row r) {
     861      _eraseRow(rows.floatingId(r.id));
     862      rows.erase(r.id);
     863    }
    846864
    847865    ///Set an element of the coefficient matrix of the LP
  • lemon/lp_cplex.cc

    r1508 r1542  
    243243    //CPX_PARAM_LPMETHOD
    244244    status = CPXlpopt(env, lp);
     245    //status = CPXprimopt(env, lp);
    245246    if (status == 0){
    246247      //We want to exclude some cases
     
    328329// ??case CPX_ABORT_CROSSOVER             
    329330// ??case CPX_INForUNBD                   
    330 // ??case CPX_PIVOT                       
     331// ??case CPX_PIVOT             
     332         
     333//Some more interesting stuff:
     334
     335// CPX_PARAM_LPMETHOD  1062  int  LPMETHOD
     336// 0 Automatic
     337// 1 Primal Simplex
     338// 2 Dual Simplex
     339// 3 Network Simplex
     340// 4 Standard Barrier
     341// Default: 0
     342// Description: Method for linear optimization.
     343// Determines which algorithm is used when CPXlpopt() (or "optimize" in the Interactive Optimizer) is called. Currently the behavior of the "Automatic" setting is that CPLEX simply invokes the dual simplex method, but this capability may be expanded in the future so that CPLEX chooses the method based on problem characteristics
     344  //Hulye cplex
     345  void statusSwitch(CPXENVptr env,int& stat){
     346    int lpmethod;
     347    CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
     348    if (lpmethod==2){
     349      if (stat==CPX_UNBOUNDED){
     350        stat=CPX_INFEASIBLE;
     351      }
     352      else{
     353        if (stat==CPX_INFEASIBLE)
     354          stat=CPX_UNBOUNDED;
     355      }
     356    }
     357  }
    331358
    332359  LpCplex::SolutionStatus LpCplex::_getPrimalStatus()
    333360  {
     361   
    334362    int stat = CPXgetstat(env, lp);
     363    statusSwitch(env,stat);
     364    //CPXgetstat(env, lp);
    335365    //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
    336366    switch (stat) {
     
    340370      return OPTIMAL;
    341371    case CPX_UNBOUNDED://Unbounded
    342       return INFINITE;
     372      return INFEASIBLE;//In case of dual simplex
     373      //return INFINITE;
    343374    case CPX_INFEASIBLE://Infeasible
    344375 //    case CPX_IT_LIM_INFEAS:
     
    349380//     case CPX_ABORT_PRIM_INFEAS:           
    350381//     case CPX_ABORT_PRIM_DUAL_INFEAS:     
    351       return INFEASIBLE;
     382      return INFINITE;//In case of dual simplex
     383      //return INFEASIBLE;
    352384//     case CPX_OBJ_LIM:                   
    353385//     case CPX_IT_LIM_FEAS:             
     
    384416  {
    385417    int stat = CPXgetstat(env, lp);
     418    statusSwitch(env,stat);
    386419    switch (stat) {
    387420    case 0:
  • test/lp_test.cc

    r1508 r1542  
    11#include<lemon/lp_skeleton.h>
    22#include "test_tools.h"
     3
    34
    45#ifdef HAVE_CONFIG_H
     
    183184}
    184185
     186void solveAndCheck(LpSolverBase& lp, LpSolverBase::SolutionStatus stat,
     187                   double exp_opt){
     188  lp.solve();
     189  //int decimal,sign;
     190  std::string buf1;
     191  //  itoa(stat,buf1, 10);
     192  check(lp.primalStatus()==stat,"Primalstatus should be "+buf1);
     193   
     194  if (stat ==  LpSolverBase::OPTIMAL){
     195    check(std::abs(lp.primalValue()-exp_opt)<1e-3,
     196          "Wrong optimal value: the right optimum is ");
     197    //+ecvt(exp_opt,2)
     198  }
     199}
     200 
    185201void aTest(LpSolverBase & lp)
    186202{
    187203  typedef LpSolverBase LP;
    188204
    189  //The following example is taken from the book by Gáspár and Temesi, page 39.
     205 //The following example is very simple
    190206
    191207  typedef LpSolverBase::Row Row;
     
    198214
    199215  //Constraints
    200   lp.addRow(3*x1+2*x2 >=6); 
    201   lp.addRow(-1*x1+x2<=4); 
    202   lp.addRow(5*x1+8*x2<=40); 
    203   lp.addRow(x1-2*x2<=4); 
     216  Row upright=lp.addRow(x1+x2 <=1); 
     217  lp.addRow(x1+x2 >=-1); 
     218  lp.addRow(x1-x2 <=1); 
     219  lp.addRow(x1-x2 >=-1); 
    204220  //Nonnegativity of the variables
    205221  lp.colLowerBound(x1, 0);
    206222  lp.colLowerBound(x2, 0);
    207223  //Objective function
    208   lp.setObj(2*x1+x2);
     224  lp.setObj(x1+x2);
    209225
    210226  lp.max();
    211   lp.solve();
    212 
    213   double opt=122.0/9.0;
    214  
    215   if (lp.primalStatus()==LpSolverBase::OPTIMAL){
    216     std::cout<< "Z = "<<lp.primalValue()
    217              << " (error = " << lp.primalValue()-opt
    218              << "); x1 = "<<lp.primal(x1)
    219              << "; x2 = "<<lp.primal(x2)
    220              <<std::endl;
    221    
    222   }
    223   else{
    224     std::cout<<"Optimal solution not found!"<<std::endl;
    225   }
    226 
    227   check(lp.primalStatus()==LpSolverBase::OPTIMAL,"Primalstatus should be OPTIMAL");
    228 
    229   check(std::abs(lp.primalValue()-opt)<1e-3,
    230         "Wrong optimal value: the right optimum is 122/9 (13.555555...)");
    231 
     227
     228  //Maximization of x1+x2
     229  //over the triangle with vertices (0,0) (0,1) (1,0)
     230  double expected_opt=1;
     231  solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
     232 
     233  //Minimization
     234  lp.min();
     235  expected_opt=0;
     236  solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
     237 
     238  //Vertex (-1,0) instead of (0,0)
     239  lp.colLowerBound(x1, -LpSolverBase::INF);
     240  expected_opt=-1;
     241  solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
     242
     243  //Erase one constraint and return to maximization
     244  lp.eraseRow(upright);
     245  lp.max();
     246  expected_opt=LpSolverBase::INF;
     247  solveAndCheck(lp, LpSolverBase::INFINITE, expected_opt);
     248
     249  //Infeasibilty
     250  lp.addRow(x1+x2 <=-2); 
     251  solveAndCheck(lp, LpSolverBase::INFEASIBLE, expected_opt);
     252
     253  //Change problem and forget to solve
     254  lp.min();
     255  check(lp.primalStatus()==LpSolverBase::UNDEFINED,"Primalstatus should be UNDEFINED");
     256
     257//   lp.solve();
     258//   if (lp.primalStatus()==LpSolverBase::OPTIMAL){
     259//     std::cout<< "Z = "<<lp.primalValue()
     260//           << " (error = " << lp.primalValue()-expected_opt
     261//           << "); x1 = "<<lp.primal(x1)
     262//           << "; x2 = "<<lp.primal(x2)
     263//           <<std::endl;
     264   
     265//   }
     266//   else{
     267//     std::cout<<lp.primalStatus()<<std::endl;
     268//     std::cout<<"Optimal solution not found!"<<std::endl;
     269//   }
     270
     271 
    232272
    233273}
Note: See TracChangeset for help on using the changeset viewer.