idol
A C++ Framework for Optimization
Loading...
Searching...
No Matches
KKT.h
1//
2// Created by henri on 21.11.24.
3//
4
5#ifndef IDOL_KKT_H
6#define IDOL_KKT_H
7
8#include <vector>
9#include <variant>
10#include <cassert>
11#include "idol/mixed-integer/modeling/models/Model.h"
12#include "idol/mixed-integer/modeling/variables/Var.h"
13#include "idol/mixed-integer/modeling/constraints/Ctr.h"
14#include "idol/mixed-integer/modeling/constraints/QCtr.h"
15#include "idol/mixed-integer/modeling/expressions/QuadExpr.h"
16
17namespace idol {
18 namespace Reformulators {
19 class KKT;
20 }
21 class Model;
22
23 namespace Bilevel {
24 class Description;
25 }
26}
27
29 const Model& m_primal;
30 const QuadExpr<Var, double>& m_primal_objective;
31 std::string m_prefix;
32
33 std::function<bool(const Var&)> m_primal_variable_indicator;
34 std::function<bool(const Ctr&)> m_primal_constraint_indicator;
35 std::function<bool(const QCtr&)> m_primal_qconstraint_indicator;
36
37 QuadExpr<Var, double> m_dual_objective;
38 std::vector<std::optional<Var>> m_dual_variables_for_constraints; // constraint index <-> dual variable
39 std::vector<std::optional<Var>> m_dual_variables_for_qconstraints; // qconstraint index <-> dual variable
40 std::vector<std::optional<Var>> m_dual_variables_for_lower_bounds; // variable index <-> dual variable
41 std::vector<std::optional<Var>> m_dual_variables_for_upper_bounds; // variable index <-> dual variable
42 std::vector<std::optional<std::variant<Ctr, QCtr>>> m_dual_constraints; // variable index <-> dual constraint
43
44 [[nodiscard]] bool primal_is_a_linear_problem() const;
45 [[nodiscard]] bool is_linear(const QuadExpr<Var, double>& t_expr) const;
46 void create_dual_variables();
47 [[nodiscard]] std::pair<double, double> bounds_for_dual_variable(idol::CtrType t_type) const;
48 void create_dual_constraints();
49public:
50 class BoundProvider;
51
52 KKT(const Model& t_parent,
53 const QuadExpr<Var, double>& t_primal_objective,
54 const std::function<bool(const Var&)>& t_primal_variable_indicator = [](const Var&) { return true; },
55 const std::function<bool(const Ctr&)>& t_primal_constraint_indicator = [](const Ctr&) { return true; },
56 const std::function<bool(const QCtr&)>& t_primal_qconstraint_indicator = [](const QCtr&) { return true; });
57
58 explicit KKT(const Model& t_parent,
59 const std::function<bool(const Var&)>& t_primal_variable_indicator = [](const Var&) { return true; },
60 const std::function<bool(const Ctr&)>& t_primal_constraint_indicator = [](const Ctr&) { return true; },
61 const std::function<bool(const QCtr&)>& t_primal_qconstraint_indicator = [](const QCtr&) { return true; });
62
63 KKT(const Model& t_high_point_relaxation, const Bilevel::Description& t_bilevel_description);
64
65 void set_prefix(std::string t_prefix) { m_prefix = std::move(t_prefix); }
66
67 [[nodiscard]] const QuadExpr<Var, double>& get_dual_obj_expr() const { return m_dual_objective; }
68
73 void add_coupling(Model& t_destination);
74 void add_coupling_variables(Model& t_destination);
75 void add_coupling_constraints(Model& t_destination);
76
83 void add_dual(Model& t_destination, bool t_add_objective = true);
84 void add_dual_variables(Model& t_destination);
85 void add_dual_constraints(Model& t_destination);
86 void add_dual_objective(Model& t_destination);
87
93 void add_primal(Model& t_destination, bool t_add_objective = true);
94 void add_primal_variables(idol::Model &t_destination);
95 void add_primal_constraints(idol::Model &t_destination);
96 void add_primal_objective(idol::Model &t_destination);
97
104
110 void add_kkt_reformulation(idol::Model &t_destination, bool t_use_sos1 = false);
111
112 void add_kkt_reformulation(idol::Model &t_destination, BoundProvider& t_bound_provider);
113
114 void add_bounds_on_dual_variables(idol::Model &t_destination, BoundProvider& t_bound_provider);
115
116 [[nodiscard]] const Var& get_dual_var(const Ctr& t_ctr) const;
117 [[nodiscard]] const Var& get_dual_var_lb(const Var& t_var) const;
118 [[nodiscard]] const Var& get_dual_var_ub(const Var& t_var) const;
119 const std::variant<Ctr, QCtr>& get_dual_ctr(const Var& t_var) const;
120};
121
123 const Model* m_model = nullptr;
124public:
125 virtual ~BoundProvider() = default;
126
127 [[nodiscard]] const Model& model() const { return *m_model; }
128
129 virtual double get_ctr_dual_lb(const Ctr& t_ctr) = 0;
130 virtual double get_ctr_dual_ub(const Ctr& t_ctr) = 0;
131 virtual double get_ctr_slack_lb(const Ctr& t_ctr) = 0;
132 virtual double get_ctr_slack_ub(const Ctr& t_ctr) = 0;
133 virtual double get_var_lb_dual_ub(const Var& t_var) = 0;
134 virtual double get_var_ub_dual_lb(const Var& t_var) = 0;
135 virtual double get_var_lb(const Var& t_var) { assert(m_model); return m_model->get_var_lb(t_var); }
136 virtual double get_var_ub(const Var& t_var) { assert(m_model); return m_model->get_var_ub(t_var); }
137
138 [[nodiscard]] virtual BoundProvider* clone() const = 0;
139
140 friend class idol::Reformulators::KKT;
141};
142
143#endif //IDOL_KKT_H
void add_primal(Model &t_destination, bool t_add_objective=true)
void add_strong_duality_reformulation(Model &t_destination)
void add_kkt_reformulation(idol::Model &t_destination, bool t_use_sos1=false)
void add_dual(Model &t_destination, bool t_add_objective=true)
void add_coupling(Model &t_destination)