1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the HiGHS linear optimization suite */ 4 /* */ 5 /* Written and engineered 2008-2021 at the University of Edinburgh */ 6 /* */ 7 /* Available as open-source under the MIT License */ 8 /* */ 9 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 10 /**@file test/DevKkt.h 11 * @brief 12 * @author Julian Hall, Ivet Galabova, Qi Huangfu and Michael Feldmeier 13 */ 14 #ifndef TEST_DEV_KKT_H_ 15 #define TEST_DEV_KKT_H_ 16 17 #include <map> 18 #include <vector> 19 20 #include "lp_data/HConst.h" 21 22 namespace presolve { 23 namespace dev_kkt_check { 24 25 struct State { StateState26 State(const int numCol_, const int numRow_, const std::vector<int>& Astart_, 27 const std::vector<int>& Aend_, const std::vector<int>& Aindex_, 28 const std::vector<double>& Avalue_, const std::vector<int>& ARstart_, 29 const std::vector<int>& ARindex_, const std::vector<double>& ARvalue_, 30 const std::vector<double>& colCost_, 31 const std::vector<double>& colLower_, 32 const std::vector<double>& colUpper_, 33 const std::vector<double>& rowLower_, 34 const std::vector<double>& rowUpper_, const std::vector<int>& flagCol_, 35 const std::vector<int>& flagRow_, const std::vector<double>& colValue_, 36 const std::vector<double>& colDual_, 37 const std::vector<double>& rowValue_, 38 const std::vector<double>& rowDual_, 39 const std::vector<HighsBasisStatus>& col_status_, 40 const std::vector<HighsBasisStatus>& row_status_) 41 : numCol(numCol_), 42 numRow(numRow_), 43 Astart(Astart_), 44 Aend(Aend_), 45 Aindex(Aindex_), 46 Avalue(Avalue_), 47 ARstart(ARstart_), 48 ARindex(ARindex_), 49 ARvalue(ARvalue_), 50 colCost(colCost_), 51 colLower(colLower_), 52 colUpper(colUpper_), 53 rowLower(rowLower_), 54 rowUpper(rowUpper_), 55 flagCol(flagCol_), 56 flagRow(flagRow_), 57 colValue(colValue_), 58 colDual(colDual_), 59 rowValue(rowValue_), 60 rowDual(rowDual_), 61 col_status(col_status_), 62 row_status(row_status_) {} 63 64 const int numCol; 65 const int numRow; 66 67 const std::vector<int>& Astart; 68 const std::vector<int>& Aend; 69 const std::vector<int>& Aindex; 70 const std::vector<double>& Avalue; 71 72 const std::vector<int>& ARstart; 73 const std::vector<int>& ARindex; 74 const std::vector<double>& ARvalue; 75 76 const std::vector<double>& colCost; 77 const std::vector<double>& colLower; 78 const std::vector<double>& colUpper; 79 const std::vector<double>& rowLower; 80 const std::vector<double>& rowUpper; 81 82 const std::vector<int>& flagCol; 83 const std::vector<int>& flagRow; 84 85 // solution 86 const std::vector<double>& colValue; 87 const std::vector<double>& colDual; 88 const std::vector<double>& rowValue; 89 const std::vector<double>& rowDual; 90 91 // basis 92 const std::vector<HighsBasisStatus>& col_status; 93 const std::vector<HighsBasisStatus>& row_status; 94 }; 95 96 enum class KktCondition { 97 kColBounds, 98 kPrimalFeasibility, 99 kDualFeasibility, 100 kComplementarySlackness, 101 kStationarityOfLagrangian, 102 kBasicFeasibleSolution, 103 kUnset, 104 }; 105 106 struct KktConditionDetails { KktConditionDetailsKktConditionDetails107 KktConditionDetails() {} KktConditionDetailsKktConditionDetails108 KktConditionDetails(KktCondition type_) : type(type_) {} 109 110 KktCondition type = KktCondition::kUnset; 111 double max_violation = 0.0; 112 double sum_violation_2 = 0.0; 113 int checked = 0; 114 int violated = 0; 115 }; 116 117 struct KktInfo { 118 std::map<KktCondition, KktConditionDetails> rules; 119 bool pass_col_bounds = false; 120 bool pass_primal_feas_matrix = false; 121 bool pass_dual_feas = false; 122 bool pass_st_of_L = false; 123 bool pass_comp_slackness = false; 124 bool pass_bfs = false; 125 }; 126 127 KktInfo initInfo(); 128 129 bool checkKkt(const State& state, KktInfo info); 130 131 void checkPrimalBounds(const State& state, KktConditionDetails& details); 132 void checkPrimalFeasMatrix(const State& state, KktConditionDetails& details); 133 void checkDualFeasibility(const State& state, KktConditionDetails& details); 134 void checkComplementarySlackness(const State& state, 135 KktConditionDetails& details); 136 void checkStationarityOfLagrangian(const State& state, 137 KktConditionDetails& details); 138 void checkBasicFeasibleSolution(const State& state, 139 KktConditionDetails& details); 140 141 } // namespace dev_kkt_check 142 } // namespace presolve 143 144 #endif /* TEST_KKTCHSTEP_H_ */ 145