Linear_Program.cpp 6.49 KB
Newer Older
1
2
#include "Linear_Program.h"

3
4
5
6
7
8
9
10
11
12
Linear_Program::Linear_Program(Linear_Program& lp){
  *this = lp;
}

Linear_Program::Linear_Program(Linear_Program&& lp){
  *this = std::move(lp);
}

Linear_Program::Linear_Program(bool maximum) : _maximum(maximum) {}

jonasseidel's avatar
jonasseidel committed
13
Linear_Program::Linear_Program(bool maximum, std::unordered_map<Variable*, Coefficient> direction, Polyeder polyeder)
Jonas Seidel's avatar
Jonas Seidel committed
14
  : _maximum(std::move(maximum)), _direction(std::move(direction)), _polyeder(std::move(polyeder)) {}
15

jonasseidel's avatar
jonasseidel committed
16
17
18
19
20
std::string Linear_Program::description(){
  // TODO: implement names
  return "";
}

21
22
23
24
bool Linear_Program::is_maximum(){
  return this->_maximum;
}

jonasseidel's avatar
jonasseidel committed
25
std::unordered_map<Variable*, Coefficient> Linear_Program::direction(){
Jonas Seidel's avatar
Jonas Seidel committed
26
  return this->_direction;
27
28
}

29
void Linear_Program::add_direction_coefficient(std::pair<Variable*, Coefficient> summand){
Jonas Seidel's avatar
Jonas Seidel committed
30
  this->_direction.insert(summand);
31
32
}

33
Coefficient Linear_Program::direction_coefficient(Variable* var){
Jonas Seidel's avatar
Jonas Seidel committed
34
  auto search_result = this->_direction.find(var);
35
  if(search_result == this->_direction.end()) return {0};
Jonas Seidel's avatar
Jonas Seidel committed
36
  return search_result->second;
Jonas Seidel's avatar
Jonas Seidel committed
37
38
}

Jonas Seidel's avatar
Jonas Seidel committed
39
40
Polyeder& Linear_Program::polyeder(){
  return this->_polyeder;
Jonas Seidel's avatar
Jonas Seidel committed
41
42
}

jonasseidel's avatar
jonasseidel committed
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
SCIP* Linear_Program::computational_model(){
  SCIP* scip;
  SCIPcreate(&scip);
  SCIPincludeDefaultPlugins(scip);

  SCIPcreateProb(scip, this->description().c_str(), NULL, NULL,
                             NULL, NULL, NULL, NULL, NULL);
  if(this->is_maximum()){
    SCIPsetObjsense(scip, SCIP_OBJSENSE_MAXIMIZE);
  }else{
    SCIPsetObjsense(scip, SCIP_OBJSENSE_MINIMIZE);
  }
  std::cout << "generating variables" << std::endl;
  std::unordered_map<Variable*, SCIP_VAR*> variable_lookup;
  for(auto pair : this->_polyeder.variables()){

    auto search = this->_direction.find(pair.left);

    SCIP_VAR* computational_var = pair.left->computational_var(scip, (search != this->_direction.end() ? search->second.value() : 0));
    variable_lookup.insert({pair.left, computational_var});
    SCIPaddVar(scip, computational_var);
  }
  std::cout << "generating constraints" << std::endl;
  for(Constraint con : this->_polyeder.constraints()){
    SCIP_CONS* computational_con = con.computational_con(scip, variable_lookup);
    SCIPaddCons(scip, computational_con);
  }
70

jonasseidel's avatar
jonasseidel committed
71
  return scip;
72
73
}

74
75
76
77
78
79
80
81
82
83
84
85
void Linear_Program::operator=(Linear_Program& lp){
  this->_maximum = lp._maximum;
  this->_direction = lp._direction;
  this->_polyeder = lp._polyeder;
}

void Linear_Program::operator=(Linear_Program&& lp){
  this->_maximum = lp._maximum;
  this->_direction = std::move(lp._direction);
  this->_polyeder = std::move(lp._polyeder);
}

Jonas Seidel's avatar
Jonas Seidel committed
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
Linear_Program Linear_Program::relaxation_dual(){
  std::vector<Constraint> constraints;
  constraints.reserve(this->polyeder().vs_dim());

  class bimap_counter{
    boost::bimap<Variable*, size_t> _bimap;
    size_t _counter;
  public:
    bimap_counter() : _counter(0) {}
    void insert(Variable* var){
      _bimap.insert({var, _counter});
      _counter++;
    }
    boost::bimap<Variable*, size_t>& unwrap(){
      return _bimap;
    }
  } variables;

jonasseidel's avatar
jonasseidel committed
104
  std::unordered_map<Variable*, Coefficient> direction;
Jonas Seidel's avatar
Jonas Seidel committed
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

  for(size_t index = 0; index < this->polyeder().number_of_constraints(); ++index){
    std::stringstream name;
    name << "dual_" << this->polyeder().constraint(index).description();


    if(this->polyeder().constraint(index).is_equality()){
      variables.insert({new Variable(name.str(), Continuous)});
    }else{
      variables.insert(new Variable(name.str(), Continuous, {true, 0}));
    }
  }

  // we introduce one constraint per primal variable
  for(auto curr_variable : this->polyeder().variables()){
    // gather lhs_coefficient
jonasseidel's avatar
jonasseidel committed
121
    std::unordered_map<Variable*, Coefficient> lhs;
Jonas Seidel's avatar
Jonas Seidel committed
122
    for(size_t index = 0; index < this->polyeder().number_of_constraints(); ++index){
123
      lhs.insert({variables.unwrap().right.find(index)->second, {-this->polyeder().constraint(index).lhs_coefficient(curr_variable.left)}});
Jonas Seidel's avatar
Jonas Seidel committed
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
    }


    // name of new constraint
    std::stringstream name;
    name << "dual_" << curr_variable.left->description();

    // generate contraint where inequality / equality property is based in existance of 0 <= x_curr_var bound
    {
      // if upper bound ex. generate new var and add to lhs
      if(curr_variable.left->upper_bound().first == true){
        std::stringstream ub_name;
        ub_name << "upper_bound_" << curr_variable.left->description();
        Variable* upper_bound_var = new Variable(ub_name.str(), Continuous, {true, 0});
        variables.insert(upper_bound_var);

140
        lhs.insert({upper_bound_var, {-1}});
Jonas Seidel's avatar
Jonas Seidel committed
141
142
143
144
145
146
147
148
149
150
151
152
153
154
        direction.insert({upper_bound_var, curr_variable.left->upper_bound().second});
      }
    }

    {
      if(curr_variable.left->lower_bound().first == true){
        if(curr_variable.left->lower_bound().second == 0){
          constraints.push_back(Constraint(name.str(), Inequality, lhs, -this->direction_coefficient(curr_variable.left)));
        }else{
          std::stringstream lb_name;
          lb_name << "lower_bound_" << curr_variable.left->description();
          Variable* lower_bound_var = new Variable(lb_name.str(), Continuous, {true, 0});
          variables.insert(lower_bound_var);

155
          lhs.insert({lower_bound_var, {1}});
Jonas Seidel's avatar
Jonas Seidel committed
156
          constraints.push_back(Constraint(name.str(), Equality, lhs, -this->direction_coefficient(curr_variable.left)));
157
          direction.insert({lower_bound_var, {-1}});
Jonas Seidel's avatar
Jonas Seidel committed
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
        }
      }else{
        constraints.push_back(Constraint(name.str(), Equality, lhs, -this->direction_coefficient(curr_variable.left)));
      }
    }
  }

  Polyeder polyeder (constraints, variables.unwrap());

  for(size_t index = 0; index < this->polyeder().number_of_constraints(); ++index){
    direction.insert({variables.unwrap().right.find(index)->second, this->polyeder().constraint(index).rhs()});
  }

  return Linear_Program(!this->is_maximum(), direction, polyeder);
}

174
175
176
177
178
179
180
std::ostream& operator<<(std::ostream& os, Linear_Program& linear_program){
  if(linear_program.is_maximum()){
    os << "Maximize\n";
  }else{
    os << "Minimize\n";
  }
  os << "\tobj: ";
Jonas Seidel's avatar
Jonas Seidel committed
181
182
183
  bool empty = true;
  if(linear_program.direction().size() > 0){
    bool add_plus = false;
184
185
    for(std::pair<Variable*, Coefficient> direction_summand : linear_program.direction()){
      if(direction_summand.second.is_non_zero()){
Jonas Seidel's avatar
Jonas Seidel committed
186
        empty = false;
187
        if(add_plus && !Coefficient::always_add_sign){
Jonas Seidel's avatar
Jonas Seidel committed
188
189
190
          os << " + ";
        }
        add_plus = true;
191
        os << direction_summand.second << direction_summand.first->description();
Jonas Seidel's avatar
Jonas Seidel committed
192
193
194
195
196
      }
    }
  }
  if(empty){
    os << "0";
197
  }
Jonas Seidel's avatar
Jonas Seidel committed
198
199
200
201
  os << "\n";

  os << linear_program.polyeder() << "\n";
  os << "End";
202
203
  return os;
}