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