lemon/mip_glpk.cc
author Balazs Dezso <deba@inf.elte.hu>
Tue, 02 Dec 2008 21:40:33 +0100
changeset 458 7afc121e0689
permissions -rw-r--r--
Port LP and MIP solvers from SVN -r3509 (#44)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\file
    20 ///\brief Implementation of the LEMON-GLPK mip solver interface.
    21 
    22 #include <lemon/mip_glpk.h>
    23 
    24 extern "C" {
    25 #include <glpk.h>
    26 }
    27 
    28 #if GLP_MAJOR_VERSION > 4 || (GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION > 15)
    29 #define LEMON_glp(func) (glp_##func)
    30 #define LEMON_lpx(func) (lpx_##func)
    31 
    32 #define LEMON_GLP(def) (GLP_##def)
    33 #define LEMON_LPX(def) (LPX_##def)
    34 
    35 #else
    36 
    37 #define LEMON_glp(func) (lpx_##func)
    38 #define LEMON_lpx(func) (lpx_##func)
    39 
    40 #define LEMON_GLP(def) (LPX_##def)
    41 #define LEMON_LPX(def) (LPX_##def)
    42 
    43 #endif
    44 
    45 namespace lemon {
    46 
    47   MipGlpk::MipGlpk() {
    48 #if !(GLP_MAJOR_VERSION > 4 || \
    49       (GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION > 15))
    50     LEMON_lpx(set_class)(lp,LEMON_GLP(MIP));
    51 #endif
    52   }
    53 
    54   void MipGlpk::_colType(int i, MipGlpk::ColTypes col_type){
    55     switch (col_type){
    56       case INT:
    57         LEMON_glp(set_col_kind)(lp,i,LEMON_GLP(IV));
    58         break;
    59       case REAL:
    60         LEMON_glp(set_col_kind)(lp,i,LEMON_GLP(CV));
    61         break;
    62     default:;
    63         //FIXME problem
    64     }
    65   }
    66 
    67   MipGlpk::ColTypes MipGlpk::_colType(int i) const {
    68     switch (LEMON_glp(get_col_kind)(lp,i)){
    69     case LEMON_GLP(IV):
    70       return INT;//Or binary
    71     case LEMON_GLP(CV):
    72       return REAL;
    73     default:
    74       return REAL;//Error!
    75     }
    76 
    77   }
    78 
    79   LpGlpk::SolveExitStatus MipGlpk::_solve() {
    80     int result = LEMON_lpx(simplex)(lp);
    81 
    82     // hack: mip does not contain integer variable
    83 #if GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION == 16
    84     int tmp = -1;
    85     if (LEMON_glp(get_num_int(lp)) == 0) {
    86       tmp = LEMON_lpx(add_cols)(lp, 1);
    87       LEMON_glp(set_col_bnds)(lp, tmp, LEMON_GLP(FX), 0.0, 0.0);
    88       LEMON_glp(set_col_kind)(lp, tmp, LEMON_GLP(IV));
    89     }
    90 #endif
    91 
    92     if (LEMON_lpx(get_status)(lp)==LEMON_LPX(OPT)) {
    93       //Maybe we could try the routine lpx_intopt(lp), a revised
    94       //version of lpx_integer
    95 
    96       result = LEMON_lpx(integer)(lp);
    97       switch (result){
    98       case LEMON_LPX(E_OK):
    99         solved = true;
   100         break;
   101       default:
   102         solved = false;
   103       }
   104     } else {
   105       solved = false;
   106     }
   107 #if GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION == 16
   108     if (tmp != -1) {
   109       int tmpa[2];
   110       tmpa[1] = tmp;
   111       LEMON_lpx(del_cols)(lp, 1, tmpa);
   112     }
   113 #endif
   114     return solved ? SOLVED : UNSOLVED;
   115   }
   116 
   117 
   118   LpGlpk::SolutionStatus MipGlpk::_getMipStatus() const {
   119 
   120     if (LEMON_lpx(get_status)(lp)==LEMON_LPX(OPT)){
   121       //Meg kell nezni: ha az LP is infinite, akkor ez is, ha az is
   122       //infeasible, akkor ez is, de ez lehet maskepp is infeasible.
   123       int stat= LEMON_lpx(mip_status)(lp);
   124 
   125       switch (stat) {
   126       case LEMON_LPX(I_UNDEF)://Undefined (no solve has been run yet)
   127         return UNDEFINED;
   128       case LEMON_LPX(I_NOFEAS)://There is no feasible integral solution
   129         return INFEASIBLE;
   130         //     case LEMON_LPX(UNBND)://Unbounded
   131         //       return INFINITE;
   132       case LEMON_LPX(I_FEAS)://Feasible
   133         return FEASIBLE;
   134       case LEMON_LPX(I_OPT)://Feasible
   135         return OPTIMAL;
   136       default:
   137         return UNDEFINED; //to avoid gcc warning
   138       //FIXME error
   139       }
   140     }
   141     else
   142       return UNDEFINED; //Maybe we could refine this: what does the LP
   143                         //relaxation look like
   144 
   145   }
   146 
   147   MipGlpk::Value MipGlpk::_getPrimal(int i) const {
   148     return LEMON_glp(mip_col_val)(lp,i);
   149   }
   150 
   151   MipGlpk::Value MipGlpk::_getPrimalValue() const {
   152     return LEMON_glp(mip_obj_val)(lp);
   153   }
   154 } //END OF NAMESPACE LEMON