Decomp.h

Go to the documentation of this file.
00001 //===========================================================================//
00002 // This file is part of the DIP Solver Framework.                            //
00003 //                                                                           //
00004 // DIP is distributed under the Eclipse Public License as part of the        //
00005 // COIN-OR repository (http://www.coin-or.org).                              //
00006 //                                                                           //
00007 // Author: Matthew Galati, SAS Institute Inc. (matthew.galati@sas.com)       //
00008 //                                                                           //
00009 // Conceptual Design: Matthew Galati, SAS Institute Inc.                     //
00010 //                    Ted Ralphs, Lehigh University                          //
00011 //                                                                           //
00012 // Copyright (C) 2002-2015, Lehigh University, Matthew Galati, Ted Ralphs    //
00013 // All Rights Reserved.                                                      //
00014 //===========================================================================//
00015 
00016 //===========================================================================//
00017 #ifndef Decomp_h_
00018 #define Decomp_h_
00019 
00020 //===========================================================================//
00021 // Standard Headers                                                          //
00022 //===========================================================================//
00023 //---
00024 //--- include the necessary standard libs
00025 //---
00026 #include <cstdio>
00027 #include <cassert>
00028 #include <vector>
00029 #include <list>
00030 #include <iostream>
00031 #include <fstream>
00032 #include <iomanip>
00033 #include <numeric>
00034 #include <sstream>
00035 #include <algorithm>
00036 #include <functional>
00037 #include <string>
00038 #include <map>
00039 #include <limits>
00040 #include <cmath>
00041 
00042 #include "DecompConfig.h"
00043 
00044 //===========================================================================//
00045 // DECOMP Enums, Constants and Typedefs                                      //
00046 //===========================================================================//
00047 
00048 //===========================================================================//
00049 //---
00050 //--- DECOMP typedefs
00051 //---
00052 class DecompVar;
00053 class DecompCut;
00054 typedef std::list<DecompVar*> DecompVarList;
00055 typedef std::list<DecompCut*> DecompCutList;
00056 
00057 //===========================================================================//
00058 //---
00059 //--- DECOMP constants
00060 //---
00061 const double DecompBigNum   = 1.0e21;
00062 const double DecompEpsilon  = 1.0e-6;
00063 const double DecompZero     = 1.0e-14;
00064 
00065 //===========================================================================//
00066 //---
00067 //--- DECOMP enums (for algorithms)
00068 //---
00069 
00070 
00071 struct DecompMainParam {
00072    bool doCut;
00073    bool doPriceCut;
00074    bool doDirect;
00075    double timeSetupCpu ;
00076    double timeSetupReal;
00077    double timeSolveCpu ;
00078    double timeSolveReal ;
00079    double bestLB;
00080    double bestUB;
00081 };
00082 
00083 
00084 
00085 enum DecompAlgoType {
00086    CUT,
00087    PRICE_AND_CUT,
00088    RELAX_AND_CUT,
00089    VOL_AND_CUT,
00090    DECOMP
00091 };
00092 const std::string DecompAlgoStr[5] = {
00093    "CUT",
00094    "PRICE_AND_CUT",
00095    "RELAX_AND_CUT",
00096    "VOL_AND_CUT",
00097    "DECOMP"
00098 };
00099 
00100 //---
00101 //--- node stopping criteria
00102 //---
00103 enum DecompAlgoStop {
00104    DecompStopNo,
00105    DecompStopGap,
00106    DecompStopTailOff,
00107    DecompStopInfeasible,
00108    DecompStopBound,
00109    DecompStopTime,
00110    DecompStopIterLimit
00111 };
00112 const std::string DecompAlgoStopStr[7] = {
00113    "DecompStopNo",
00114    "DecompStopGap",
00115    "DecompStopTailOff",
00116    "DecompStopInfeasible",
00117    "DecompStopBound",
00118    "DecompStopTime",
00119    "DecompStopIterLimit"
00120 };
00121 
00122 
00123 //===========================================================================//
00124 //---
00125 //--- DECOMP enums (for phases)
00126 //---
00127 enum DecompPhase {
00128    PHASE_PRICE1,
00129    PHASE_PRICE2,
00130    PHASE_CUT,
00131    PHASE_DONE,
00132    PHASE_UNKNOWN
00133 };
00134 const std::string DecompPhaseStr[6] = {
00135    "PHASE_PRICE1",
00136    "PHASE_PRICE2",
00137    "PHASE_CUT",
00138    "PHASE_DONE",
00139    "PHASE_UNKNOWN"
00140 };
00141 
00142 //===========================================================================//
00143 //---
00144 //--- DECOMP enums (for status)
00145 //---
00146 enum DecompStatus {
00147    STAT_FEASIBLE,
00148    STAT_IP_FEASIBLE,
00149    STAT_INFEASIBLE,
00150    STAT_UNKNOWN
00151 };
00152 const std::string DecompStatusStr[3] = {
00153    "STAT_FEASIBLE",
00154    "STAT_INFEASIBLE",
00155    "STAT_UNKNOWN"
00156 };
00157 
00158 enum DecompPriceCutStrategy {
00159    Default,
00160    FavorPrice,
00161    FavorCut
00162 };
00163 const std::string DecompPriceCutStrategyStr[3] = {
00164    "Default",
00165    "Favor Price",
00166    "Favor Cut"
00167 };
00168 
00169 //===========================================================================//
00170 enum DecompSolverStatus {
00171    DecompSolStatError,
00172    DecompSolStatOptimal,
00173    DecompSolStatFeasible,
00174    DecompSolStatInfeasible,
00175    DecompSolStatNoSolution
00176 };
00177 
00178 //===========================================================================//
00179 enum DecompGenericStatus {
00180    DecompStatOk          = 0,
00181    DecompStatError       = 1,
00182    DecompStatOutOfMemory = 2
00183 };
00184 
00185 enum DecompSolverType {
00186    DecompDualSimplex = 0,
00187    DecompPrimSimplex = 1,
00188    DecompBarrier     = 2
00189 };
00190 
00191 enum DecompRoundRobin {
00192    RoundRobinRotate    = 0,
00193    RoundRobinMostNegRC = 1
00194 };
00195 
00196 //===========================================================================//
00197 enum DecompFunction {
00198    DecompFuncGeneric          = 0,
00199    DecompFuncGenerateInitVars = 1
00200 };
00201 
00202 enum DecompSubProbParallelType {
00203    SubProbScheduleStatic,
00204    SubProbScheduleDynamic,
00205    SubProbScheduleGuided,
00206    SubProbScheduleRuntime
00207 };
00208 
00209 
00210 
00211 //===========================================================================//
00212 enum DecompRowType {
00213    //original row
00214    DecompRow_Original,
00215    //branching row
00216    DecompRow_Branch,
00217    //convexity constraint
00218    DecompRow_Convex,
00219    //row which is a cut
00220    DecompRow_Cut
00221 };
00222 const std::string DecompRowTypeStr[4] = {
00223    "DecompRow_Original",
00224    "DecompRow_Branch",
00225    "DecompRow_Convex",
00226    "DecompRow_Cut"
00227 };
00228 
00229 //===========================================================================//
00230 //Corresponding to the class DecompVar
00231 enum DecompVarType {
00232    // points generated from bounded subproblem
00233    DecompVar_Point,
00234    // rays generated from unbounded subproblem
00235    DecompVar_Ray
00236 };
00237 
00238 
00239 
00240 //===========================================================================//
00241 enum DecompColType {
00242    //structural column
00243    DecompCol_Structural,
00244    //structural column (which should never be deleted)
00245    DecompCol_Structural_NoDelete,
00246    //master-only column
00247    DecompCol_MasterOnly,
00248    //artifical column for original row (L for <=)
00249    DecompCol_ArtForRowL,
00250    //artifical column for original row (G for >=)
00251    DecompCol_ArtForRowG,
00252    //artifical column for branching row (L for <=)
00253    DecompCol_ArtForBranchL,
00254    //artifical column for branching row (G for >=)
00255    DecompCol_ArtForBranchG,
00256    //artifical column for convexity row (L for <=)
00257    DecompCol_ArtForConvexL,
00258    //artifical column for convexity row (G for >=)
00259    DecompCol_ArtForConvexG,
00260    //artifical column for cut (L for <=)
00261    DecompCol_ArtForCutL,
00262    //artifical column for cutG(L for >=)
00263    DecompCol_ArtForCutG,
00264    //marker used for deletion
00265    DecompCol_ToBeDeleted
00266 };
00267 const std::string DecompColTypeStr[12] = {
00268    "DecompCol_Structural",
00269    "DecompCol_Structural_NoDelete",
00270    "DecompCol_MasterOnly",
00271    "DecompCol_ArtForRowL",
00272    "DecompCol_ArtForRowG",
00273    "DecompCol_ArtForBranchL",
00274    "DecompCol_ArtForBranchG",
00275    "DecompCol_ArtForConvexL",
00276    "DecompCol_ArtForConvexG",
00277    "DecompCol_ArtForCutL",
00278    "DecompCol_ArtForCutG",
00279    "DecompCol_ToBeDeleted"
00280 };
00281 
00282 enum DecompBranchingImplementation {
00283    DecompBranchInSubproblem,
00284    DecompBranchInMaster
00285 };
00286 /*
00287 enum DecompNumericErrorType {
00288 
00289 
00290 
00291 };
00292 */
00293 
00294 //===========================================================================//
00295 // COIN Headers                                                              //
00296 //===========================================================================//
00297 //---
00298 //--- include some standard COIN headers (depending on LP solver)
00299 //---   depending on LP solver, set:
00300 //---      OsiLp, OsiIp, and DecompInf
00301 //---
00302 #include "CoinError.hpp"
00303 #include "CoinFinite.hpp"
00304 #include "CoinPackedVector.hpp"
00305 #include "CoinPackedMatrix.hpp"
00306 
00307 #ifdef __DECOMP_LP_CLP__
00308 #include "OsiClpSolverInterface.hpp"
00309 typedef OsiClpSolverInterface OsiLpSolverInterface;
00310 const double DecompInf = OsiClpInfinity;
00311 #endif
00312 
00313 #ifdef __DECOMP_LP_CPX__
00314 #include "cplex.h"
00315 #include "OsiCpxSolverInterface.hpp"
00316 typedef OsiCpxSolverInterface OsiLpSolverInterface;
00317 const double DecompInf = CPX_INFBOUND;
00318 #endif
00319 
00320 #ifdef __DECOMP_IP_CBC__
00321 #include "OsiCbcSolverInterface.hpp"
00322 //confusing, since we use CbcModel/Main, we need OsiClp here
00323 typedef OsiClpSolverInterface OsiIpSolverInterface;
00324 //typedef OsiCbcSolverInterface OsiIpSolverInterface;
00325 #endif
00326 
00327 #ifdef __DECOMP_IP_CPX__
00328 #include "cplex.h"
00329 #include "OsiCpxSolverInterface.hpp"
00330 typedef OsiCpxSolverInterface OsiIpSolverInterface;
00331 #endif
00332 
00333 #ifdef __DECOMP_IP_SYMPHONY__
00334 #include "symphony.h"
00335 #include "OsiSymSolverInterface.hpp"
00336 typedef OsiSymSolverInterface OsiIpSolverInterface;
00337 #endif
00338 
00339 
00340 //---
00341 //--- COIN vectors can do some extra checking if this is true,
00342 //---   but, it is expensive, so turn off when in optimized mode
00343 //---
00344 #ifdef NDEBUG
00345 #define DECOMP_TEST_DUPINDEX false
00346 #else
00347 #define DECOMP_TEST_DUPINDEX true
00348 #endif
00349 
00350 #endif

Generated on 5 Apr 2015 for Dip-All by  doxygen 1.6.1