1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the HiGHS linear optimization suite */ 4 /* */ 5 /* Written and engineered 2008-2020 at the University of Edinburgh */ 6 /* */ 7 /* Available as open-source under the MIT License */ 8 /* */ 9 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 10 /**@file lp_data/SimplexConst.h 11 * @brief Constants for HiGHS simplex solvers 12 * @author Julian Hall, Ivet Galabova, Qi Huangfu and Michael Feldmeier 13 */ 14 #ifndef SIMPLEX_SIMPLEXCONST_H_ 15 #define SIMPLEX_SIMPLEXCONST_H_ 16 17 enum class SimplexSolutionStatus { 18 UNSET = -1, 19 OPTIMAL, 20 PRIMAL_FEASIBLE, 21 DUAL_FEASIBLE, 22 INFEASIBLE, 23 UNBOUNDED, 24 SINGULAR, 25 FAILED, 26 REACHED_DUAL_OBJECTIVE_VALUE_UPPER_BOUND, 27 OUT_OF_TIME 28 }; 29 30 enum class SimplexAlgorithm { PRIMAL = 0, DUAL }; 31 32 enum SimplexStrategy { 33 SIMPLEX_STRATEGY_MIN = 0, 34 SIMPLEX_STRATEGY_CHOOSE = SIMPLEX_STRATEGY_MIN, 35 SIMPLEX_STRATEGY_DUAL, 36 SIMPLEX_STRATEGY_DUAL_PLAIN = SIMPLEX_STRATEGY_DUAL, 37 SIMPLEX_STRATEGY_DUAL_TASKS, 38 SIMPLEX_STRATEGY_DUAL_MULTI, 39 SIMPLEX_STRATEGY_PRIMAL, 40 SIMPLEX_STRATEGY_MAX = SIMPLEX_STRATEGY_PRIMAL, 41 SIMPLEX_STRATEGY_NUM 42 }; 43 44 enum SimplexSolvePhase { 45 SOLVE_PHASE_MIN = -3, 46 SOLVE_PHASE_ERROR = SOLVE_PHASE_MIN, // -3 47 SOLVE_PHASE_EXIT, // -2, 48 SOLVE_PHASE_UNKNOWN, // -1 49 SOLVE_PHASE_OPTIMAL, // 0 50 SOLVE_PHASE_1, // 1 51 SOLVE_PHASE_2, // 2 52 SOLVE_PHASE_CLEANUP = 4, 53 SOLVE_PHASE_MAX = SOLVE_PHASE_CLEANUP 54 }; 55 56 enum DualSimplexCleanupStrategy { 57 DUAL_SIMPLEX_CLEANUP_STRATEGY_MIN = 0, 58 DUAL_SIMPLEX_CLEANUP_STRATEGY_NONE = DUAL_SIMPLEX_CLEANUP_STRATEGY_MIN, 59 DUAL_SIMPLEX_CLEANUP_STRATEGY_HPRIMAL, 60 DUAL_SIMPLEX_CLEANUP_STRATEGY_HQPRIMAL, 61 DUAL_SIMPLEX_CLEANUP_STRATEGY_MAX = DUAL_SIMPLEX_CLEANUP_STRATEGY_HQPRIMAL 62 }; 63 64 enum SimplexScaleStrategy { 65 SIMPLEX_SCALE_STRATEGY_MIN = 0, 66 SIMPLEX_SCALE_STRATEGY_OFF = SIMPLEX_SCALE_STRATEGY_MIN, 67 SIMPLEX_SCALE_STRATEGY_HIGHS, 68 SIMPLEX_SCALE_STRATEGY_HIGHS_FORCED, 69 SIMPLEX_SCALE_STRATEGY_015, 70 SIMPLEX_SCALE_STRATEGY_0157, 71 SIMPLEX_SCALE_STRATEGY_MAX = SIMPLEX_SCALE_STRATEGY_0157 72 }; 73 74 enum SimplexCrashStrategy { 75 SIMPLEX_CRASH_STRATEGY_MIN = 0, 76 SIMPLEX_CRASH_STRATEGY_OFF = SIMPLEX_CRASH_STRATEGY_MIN, 77 SIMPLEX_CRASH_STRATEGY_LTSSF_K, 78 SIMPLEX_CRASH_STRATEGY_LTSSF = SIMPLEX_CRASH_STRATEGY_LTSSF_K, 79 SIMPLEX_CRASH_STRATEGY_BIXBY, 80 SIMPLEX_CRASH_STRATEGY_LTSSF_PRI, 81 SIMPLEX_CRASH_STRATEGY_LTSF_K, 82 SIMPLEX_CRASH_STRATEGY_LTSF_PRI, 83 SIMPLEX_CRASH_STRATEGY_LTSF, 84 SIMPLEX_CRASH_STRATEGY_BIXBY_NO_NONZERO_COL_COSTS, 85 SIMPLEX_CRASH_STRATEGY_BASIC, 86 SIMPLEX_CRASH_STRATEGY_TEST_SING, 87 SIMPLEX_CRASH_STRATEGY_MAX = SIMPLEX_CRASH_STRATEGY_TEST_SING 88 }; 89 90 enum SimplexDualEdgeWeightStrategy { 91 SIMPLEX_DUAL_EDGE_WEIGHT_STRATEGY_MIN = -1, 92 SIMPLEX_DUAL_EDGE_WEIGHT_STRATEGY_CHOOSE = 93 SIMPLEX_DUAL_EDGE_WEIGHT_STRATEGY_MIN, 94 SIMPLEX_DUAL_EDGE_WEIGHT_STRATEGY_DANTZIG, 95 SIMPLEX_DUAL_EDGE_WEIGHT_STRATEGY_DEVEX, 96 SIMPLEX_DUAL_EDGE_WEIGHT_STRATEGY_STEEPEST_EDGE, 97 SIMPLEX_DUAL_EDGE_WEIGHT_STRATEGY_STEEPEST_EDGE_UNIT_INITIAL, 98 SIMPLEX_DUAL_EDGE_WEIGHT_STRATEGY_MAX = 99 SIMPLEX_DUAL_EDGE_WEIGHT_STRATEGY_STEEPEST_EDGE_UNIT_INITIAL 100 }; 101 102 enum SimplexPrimalEdgeWeightStrategy { 103 SIMPLEX_PRIMAL_EDGE_WEIGHT_STRATEGY_MIN = -1, 104 SIMPLEX_PRIMAL_EDGE_WEIGHT_STRATEGY_CHOOSE = 105 SIMPLEX_PRIMAL_EDGE_WEIGHT_STRATEGY_MIN, 106 SIMPLEX_PRIMAL_EDGE_WEIGHT_STRATEGY_DANTZIG, 107 SIMPLEX_PRIMAL_EDGE_WEIGHT_STRATEGY_DEVEX, 108 SIMPLEX_PRIMAL_EDGE_WEIGHT_STRATEGY_MAX = 109 SIMPLEX_PRIMAL_EDGE_WEIGHT_STRATEGY_DEVEX 110 }; 111 112 enum SimplexPriceStrategy { 113 SIMPLEX_PRICE_STRATEGY_MIN = 0, 114 SIMPLEX_PRICE_STRATEGY_COL = SIMPLEX_PRICE_STRATEGY_MIN, 115 SIMPLEX_PRICE_STRATEGY_ROW, 116 SIMPLEX_PRICE_STRATEGY_ROW_SWITCH, 117 SIMPLEX_PRICE_STRATEGY_ROW_SWITCH_COL_SWITCH, 118 SIMPLEX_PRICE_STRATEGY_MAX = SIMPLEX_PRICE_STRATEGY_ROW_SWITCH_COL_SWITCH 119 }; 120 121 enum SimplexDualChuzcStrategy { 122 SIMPLEX_DUAL_CHUZC_STRATEGY_MIN = 0, 123 SIMPLEX_DUAL_CHUZC_STRATEGY_CHOOSE = SIMPLEX_DUAL_CHUZC_STRATEGY_MIN, 124 SIMPLEX_DUAL_CHUZC_STRATEGY_QUAD, 125 SIMPLEX_DUAL_CHUZC_STRATEGY_HEAP, 126 SIMPLEX_DUAL_CHUZC_STRATEGY_BOTH, 127 SIMPLEX_DUAL_CHUZC_STRATEGY_MAX = SIMPLEX_DUAL_CHUZC_STRATEGY_BOTH 128 }; 129 130 // Not an enum class since invert_hint is used in so many places 131 enum InvertHint { 132 INVERT_HINT_NO = 0, 133 INVERT_HINT_UPDATE_LIMIT_REACHED, 134 INVERT_HINT_SYNTHETIC_CLOCK_SAYS_INVERT, 135 INVERT_HINT_POSSIBLY_OPTIMAL, 136 INVERT_HINT_POSSIBLY_PRIMAL_UNBOUNDED, 137 INVERT_HINT_POSSIBLY_DUAL_UNBOUNDED, 138 INVERT_HINT_POSSIBLY_SINGULAR_BASIS, 139 INVERT_HINT_PRIMAL_INFEASIBLE_IN_PRIMAL_SIMPLEX, 140 INVERT_HINT_CHOOSE_COLUMN_FAIL, 141 INVERT_HINT_Count 142 }; 143 144 enum class DualEdgeWeightMode { DANTZIG = 0, DEVEX, STEEPEST_EDGE, Count }; 145 146 enum class PriceMode { ROW = 0, COL }; 147 148 const int PARALLEL_THREADS_DEFAULT = 8; 149 const int DUAL_TASKS_MIN_THREADS = 3; 150 const int DUAL_MULTI_MIN_THREADS = 1; // 2; 151 152 // TODO: Set this false tactically to make mip interface more 153 // efficient by preventing reinversion on optimality in phase 1 or 154 // phase 2 155 const bool invert_if_row_out_negative = true; 156 157 /** Simplex nonbasicFlag status for columns and rows. Don't use enum 158 class since they are used as int to replace conditional statements 159 by multiplication */ 160 const int NONBASIC_FLAG_TRUE = 1; // Nonbasic 161 const int NONBASIC_FLAG_FALSE = 0; // Basic 162 163 /** Simplex nonbasicMove status for columns and rows. Don't use enum 164 class since they are used in conditional statements */ 165 const int NONBASIC_MOVE_UP = 1; // Free to move (only) up 166 const int NONBASIC_MOVE_DN = -1; // Free to move (only) down 167 const int NONBASIC_MOVE_ZE = 0; // Fixed or free to move up and down 168 // 169 // Relation between HiGHS basis and Simplex basis 170 // 171 // Data structures 172 // =============== 173 // 174 // HiGHS basis consists of vectors 175 // 176 // * col_status[numCol] 177 // * row_status[numRow] 178 // 179 // Simplex basis consists of vectors 180 // 181 // * nonbasicMove[numTot] 182 // * basicIndex[numRow] 183 // * nonbasicFlag[numTot] 184 // 185 // where nonbasicFlag is duplicate information but is used to identify 186 // whether a particular variable is basic or nonbasic. 187 // 188 // Basic variables 189 // =============== 190 // 191 // Highs: *_status value of BASIC 192 // 193 // <=> 194 // 195 // Simplex: nonbasicFlag value of NONBASIC_FLAG_FALSE 196 // 197 // Nonbasic variables 198 // ================== 199 // 200 // Relations complicated by the fact that 201 // 202 // * HiGHS rows have bounds [ l, u] 203 // * Simplex rows have bounds [-u, -l] 204 // 205 // Nonbasic columns 206 // ================ 207 // 208 // Highs: col_status value of LOWER - at lower bound 209 // <=> 210 // Simplex: nonbasicMove value of NONBASIC_MOVE_UP - [l, Inf] column free to 211 // move up and negative dual 212 // 213 // Highs: col_status value of ZERO - at zero 214 // => 215 // Simplex: nonbasicMove value of NONBASIC_MOVE_ZE - free variable treated 216 // specially in simplex 217 // 218 // Highs: col_status value of UPPER - at upper bound 219 // => 220 // Simplex: Either 221 // * nonbasicMove value of NONBASIC_MOVE_DN - [-Inf, u] column free to move down 222 // and positive dual 223 // * nonbasicMove value of NONBASIC_MOVE_ZE - [ l, u] column ?? and free dual 224 // 225 // Simplex: nonbasicMove value of NONBASIC_MOVE_DN - [-Inf, u] column free to 226 // move down and positive dual 227 // => 228 // Highs: col_status value of UPPER - at upper bound 229 // 230 // Simplex: nonbasicMove value of NONBASIC_MOVE_ZE - [l, u] column ?? and free 231 // dual 232 // => 233 // Highs: Either 234 // * col_status value of UPPER - at upper bound 235 // * col_status value of ZERO - at zero 236 // 237 // Nonbasic rows 238 // ============= 239 // 240 #endif /* SIMPLEX_SIMPLEXCONST_H_ */ 241