Linear_Program.cpp 6.71 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
}

43
std::pair<SCIP*, std::unordered_map<Variable*, SCIP_VAR*> > Linear_Program::computational_model(){
jonasseidel's avatar
jonasseidel committed
44
  SCIP* scip;
jonasseidel's avatar
jonasseidel committed
45
  SCIP_CALL_ABORT( SCIPcreate(&scip));
jonasseidel's avatar
jonasseidel committed
46 47
  SCIPincludeDefaultPlugins(scip);

jonasseidel's avatar
jonasseidel committed
48 49 50

  SCIP_CALL_ABORT( SCIPcreateProb(scip, this->description().c_str(), NULL, NULL,
                             NULL, NULL, NULL, NULL, NULL));
jonasseidel's avatar
jonasseidel committed
51
  if(this->is_maximum()){
jonasseidel's avatar
jonasseidel committed
52
    SCIP_CALL_ABORT( SCIPsetObjsense(scip, SCIP_OBJSENSE_MAXIMIZE));
jonasseidel's avatar
jonasseidel committed
53
  }else{
jonasseidel's avatar
jonasseidel committed
54
    SCIP_CALL_ABORT( SCIPsetObjsense(scip, SCIP_OBJSENSE_MINIMIZE));
jonasseidel's avatar
jonasseidel committed
55 56 57 58 59 60
  }
  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));
61

jonasseidel's avatar
jonasseidel committed
62
    variable_lookup.insert({pair.left, computational_var});
jonasseidel's avatar
jonasseidel committed
63
    SCIP_CALL_ABORT( SCIPaddVar(scip, computational_var));
jonasseidel's avatar
jonasseidel committed
64 65 66
  }
  for(Constraint con : this->_polyeder.constraints()){
    SCIP_CONS* computational_con = con.computational_con(scip, variable_lookup);
jonasseidel's avatar
jonasseidel committed
67 68
    SCIP_CALL_ABORT( SCIPaddCons(scip, computational_con));
    SCIP_CALL_ABORT( SCIPreleaseCons(scip, &computational_con));
jonasseidel's avatar
jonasseidel committed
69
  }
70

71
  return {scip, variable_lookup};
72 73
}

74 75 76 77 78 79 80 81 82
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);
83
  lp._direction = std::unordered_map<Variable*, Coefficient>();
84
  this->_polyeder = std::move(lp._polyeder);
85
  lp._polyeder = Polyeder();
86 87
}

Jonas Seidel's avatar
Jonas Seidel committed
88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
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
106
  std::unordered_map<Variable*, Coefficient> direction;
Jonas Seidel's avatar
Jonas Seidel committed
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122

  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
123
    std::unordered_map<Variable*, Coefficient> lhs;
Jonas Seidel's avatar
Jonas Seidel committed
124
    for(size_t index = 0; index < this->polyeder().number_of_constraints(); ++index){
125
      lhs.insert({variables.unwrap().right.find(index)->second, {-this->polyeder().constraint(index).lhs_coefficient(curr_variable.left)}});
Jonas Seidel's avatar
Jonas Seidel committed
126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
    }


    // 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);

142
        lhs.insert({upper_bound_var, {-1}});
Jonas Seidel's avatar
Jonas Seidel committed
143 144 145 146 147 148 149 150 151 152 153 154 155 156
        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);

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

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

  os << linear_program.polyeder() << "\n";
  os << "End";
204 205
  return os;
}