COIN-OR::LEMON - Graph Library

source: lemon/lemon/soplex.cc @ 888:f903263902f6

Last change on this file since 888:f903263902f6 was 793:e4554cd6b2bf, checked in by Balazs Dezso <deba@…>, 14 years ago

Faster add row operation (#203)

One virtual function call instead of more

File size: 11.7 KB
RevLine 
[484]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <iostream>
20#include <lemon/soplex.h>
21
[586]22#include <soplex.h>
[623]23#include <spxout.h>
[484]24
25
26///\file
27///\brief Implementation of the LEMON-SOPLEX lp solver interface.
28namespace lemon {
29
[485]30  SoplexLp::SoplexLp() {
[484]31    soplex = new soplex::SoPlex;
[623]32    messageLevel(MESSAGE_NOTHING);
[484]33  }
34
[485]35  SoplexLp::~SoplexLp() {
[484]36    delete soplex;
37  }
38
[485]39  SoplexLp::SoplexLp(const SoplexLp& lp) {
[484]40    rows = lp.rows;
41    cols = lp.cols;
42
43    soplex = new soplex::SoPlex;
44    (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
45
46    _col_names = lp._col_names;
47    _col_names_ref = lp._col_names_ref;
48
49    _row_names = lp._row_names;
50    _row_names_ref = lp._row_names_ref;
51
[623]52    messageLevel(MESSAGE_NOTHING);
[484]53  }
54
[485]55  void SoplexLp::_clear_temporals() {
[484]56    _primal_values.clear();
57    _dual_values.clear();
58  }
59
[587]60  SoplexLp* SoplexLp::newSolver() const {
[485]61    SoplexLp* newlp = new SoplexLp();
[484]62    return newlp;
63  }
64
[587]65  SoplexLp* SoplexLp::cloneSolver() const {
[485]66    SoplexLp* newlp = new SoplexLp(*this);
[484]67    return newlp;
68  }
69
[485]70  const char* SoplexLp::_solverName() const { return "SoplexLp"; }
[484]71
[485]72  int SoplexLp::_addCol() {
[484]73    soplex::LPCol c;
74    c.setLower(-soplex::infinity);
75    c.setUpper(soplex::infinity);
76    soplex->addCol(c);
77
78    _col_names.push_back(std::string());
79
80    return soplex->nCols() - 1;
81  }
82
[485]83  int SoplexLp::_addRow() {
[484]84    soplex::LPRow r;
85    r.setLhs(-soplex::infinity);
86    r.setRhs(soplex::infinity);
87    soplex->addRow(r);
88
89    _row_names.push_back(std::string());
90
91    return soplex->nRows() - 1;
92  }
93
[793]94  int SoplexLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
95    soplex::DSVector v;
96    for (ExprIterator it = b; it != e; ++it) {
97      v.add(it->first, it->second);
98    }
99    soplex::LPRow r(l, v, u);
100    soplex->addRow(r);
101
102    _row_names.push_back(std::string());
103
104    return soplex->nRows() - 1;
105  }
106
[484]107
[485]108  void SoplexLp::_eraseCol(int i) {
[484]109    soplex->removeCol(i);
110    _col_names_ref.erase(_col_names[i]);
111    _col_names[i] = _col_names.back();
112    _col_names_ref[_col_names.back()] = i;
113    _col_names.pop_back();
114  }
115
[485]116  void SoplexLp::_eraseRow(int i) {
[484]117    soplex->removeRow(i);
118    _row_names_ref.erase(_row_names[i]);
119    _row_names[i] = _row_names.back();
120    _row_names_ref[_row_names.back()] = i;
121    _row_names.pop_back();
122  }
123
[485]124  void SoplexLp::_eraseColId(int i) {
[484]125    cols.eraseIndex(i);
126    cols.relocateIndex(i, cols.maxIndex());
127  }
[485]128  void SoplexLp::_eraseRowId(int i) {
[484]129    rows.eraseIndex(i);
130    rows.relocateIndex(i, rows.maxIndex());
131  }
132
[485]133  void SoplexLp::_getColName(int c, std::string &name) const {
[484]134    name = _col_names[c];
135  }
136
[485]137  void SoplexLp::_setColName(int c, const std::string &name) {
[484]138    _col_names_ref.erase(_col_names[c]);
139    _col_names[c] = name;
140    if (!name.empty()) {
141      _col_names_ref.insert(std::make_pair(name, c));
142    }
143  }
144
[485]145  int SoplexLp::_colByName(const std::string& name) const {
[484]146    std::map<std::string, int>::const_iterator it =
147      _col_names_ref.find(name);
148    if (it != _col_names_ref.end()) {
149      return it->second;
150    } else {
151      return -1;
152    }
153  }
154
[485]155  void SoplexLp::_getRowName(int r, std::string &name) const {
[484]156    name = _row_names[r];
157  }
158
[485]159  void SoplexLp::_setRowName(int r, const std::string &name) {
[484]160    _row_names_ref.erase(_row_names[r]);
161    _row_names[r] = name;
162    if (!name.empty()) {
163      _row_names_ref.insert(std::make_pair(name, r));
164    }
165  }
166
[485]167  int SoplexLp::_rowByName(const std::string& name) const {
[484]168    std::map<std::string, int>::const_iterator it =
169      _row_names_ref.find(name);
170    if (it != _row_names_ref.end()) {
171      return it->second;
172    } else {
173      return -1;
174    }
175  }
176
177
[485]178  void SoplexLp::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
[484]179    for (int j = 0; j < soplex->nCols(); ++j) {
180      soplex->changeElement(i, j, 0.0);
181    }
182    for(ExprIterator it = b; it != e; ++it) {
183      soplex->changeElement(i, it->first, it->second);
184    }
185  }
186
[485]187  void SoplexLp::_getRowCoeffs(int i, InsertIterator b) const {
[484]188    const soplex::SVector& vec = soplex->rowVector(i);
189    for (int k = 0; k < vec.size(); ++k) {
190      *b = std::make_pair(vec.index(k), vec.value(k));
191      ++b;
192    }
193  }
194
[485]195  void SoplexLp::_setColCoeffs(int j, ExprIterator b, ExprIterator e) {
[484]196    for (int i = 0; i < soplex->nRows(); ++i) {
197      soplex->changeElement(i, j, 0.0);
198    }
199    for(ExprIterator it = b; it != e; ++it) {
200      soplex->changeElement(it->first, j, it->second);
201    }
202  }
203
[485]204  void SoplexLp::_getColCoeffs(int i, InsertIterator b) const {
[484]205    const soplex::SVector& vec = soplex->colVector(i);
206    for (int k = 0; k < vec.size(); ++k) {
207      *b = std::make_pair(vec.index(k), vec.value(k));
208      ++b;
209    }
210  }
211
[485]212  void SoplexLp::_setCoeff(int i, int j, Value value) {
[484]213    soplex->changeElement(i, j, value);
214  }
215
[485]216  SoplexLp::Value SoplexLp::_getCoeff(int i, int j) const {
[484]217    return soplex->rowVector(i)[j];
218  }
219
[485]220  void SoplexLp::_setColLowerBound(int i, Value value) {
[484]221    LEMON_ASSERT(value != INF, "Invalid bound");
222    soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
223  }
224
[485]225  SoplexLp::Value SoplexLp::_getColLowerBound(int i) const {
[484]226    double value = soplex->lower(i);
227    return value != -soplex::infinity ? value : -INF;
228  }
229
[485]230  void SoplexLp::_setColUpperBound(int i, Value value) {
[484]231    LEMON_ASSERT(value != -INF, "Invalid bound");
232    soplex->changeUpper(i, value != INF ? value : soplex::infinity);
233  }
234
[485]235  SoplexLp::Value SoplexLp::_getColUpperBound(int i) const {
[484]236    double value = soplex->upper(i);
237    return value != soplex::infinity ? value : INF;
238  }
239
[485]240  void SoplexLp::_setRowLowerBound(int i, Value lb) {
[484]241    LEMON_ASSERT(lb != INF, "Invalid bound");
242    soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i));
243  }
244
[485]245  SoplexLp::Value SoplexLp::_getRowLowerBound(int i) const {
[484]246    double res = soplex->lhs(i);
247    return res == -soplex::infinity ? -INF : res;
248  }
249
[485]250  void SoplexLp::_setRowUpperBound(int i, Value ub) {
[484]251    LEMON_ASSERT(ub != -INF, "Invalid bound");
252    soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity);
253  }
254
[485]255  SoplexLp::Value SoplexLp::_getRowUpperBound(int i) const {
[484]256    double res = soplex->rhs(i);
257    return res == soplex::infinity ? INF : res;
258  }
259
[485]260  void SoplexLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
[484]261    for (int j = 0; j < soplex->nCols(); ++j) {
262      soplex->changeObj(j, 0.0);
263    }
264    for (ExprIterator it = b; it != e; ++it) {
265      soplex->changeObj(it->first, it->second);
266    }
267  }
268
[485]269  void SoplexLp::_getObjCoeffs(InsertIterator b) const {
[484]270    for (int j = 0; j < soplex->nCols(); ++j) {
271      Value coef = soplex->obj(j);
272      if (coef != 0.0) {
273        *b = std::make_pair(j, coef);
274        ++b;
275      }
276    }
277  }
278
[485]279  void SoplexLp::_setObjCoeff(int i, Value obj_coef) {
[484]280    soplex->changeObj(i, obj_coef);
281  }
282
[485]283  SoplexLp::Value SoplexLp::_getObjCoeff(int i) const {
[484]284    return soplex->obj(i);
285  }
286
[485]287  SoplexLp::SolveExitStatus SoplexLp::_solve() {
[484]288
289    _clear_temporals();
[623]290   
291    _applyMessageLevel();
[484]292
293    soplex::SPxSolver::Status status = soplex->solve();
294
295    switch (status) {
296    case soplex::SPxSolver::OPTIMAL:
297    case soplex::SPxSolver::INFEASIBLE:
298    case soplex::SPxSolver::UNBOUNDED:
299      return SOLVED;
300    default:
301      return UNSOLVED;
302    }
303  }
304
[485]305  SoplexLp::Value SoplexLp::_getPrimal(int i) const {
[484]306    if (_primal_values.empty()) {
307      _primal_values.resize(soplex->nCols());
308      soplex::Vector pv(_primal_values.size(), &_primal_values.front());
309      soplex->getPrimal(pv);
310    }
311    return _primal_values[i];
312  }
313
[485]314  SoplexLp::Value SoplexLp::_getDual(int i) const {
[484]315    if (_dual_values.empty()) {
316      _dual_values.resize(soplex->nRows());
317      soplex::Vector dv(_dual_values.size(), &_dual_values.front());
318      soplex->getDual(dv);
319    }
320    return _dual_values[i];
321  }
322
[485]323  SoplexLp::Value SoplexLp::_getPrimalValue() const {
[484]324    return soplex->objValue();
325  }
326
[485]327  SoplexLp::VarStatus SoplexLp::_getColStatus(int i) const {
[484]328    switch (soplex->getBasisColStatus(i)) {
329    case soplex::SPxSolver::BASIC:
330      return BASIC;
331    case soplex::SPxSolver::ON_UPPER:
332      return UPPER;
333    case soplex::SPxSolver::ON_LOWER:
334      return LOWER;
335    case soplex::SPxSolver::FIXED:
336      return FIXED;
337    case soplex::SPxSolver::ZERO:
338      return FREE;
339    default:
340      LEMON_ASSERT(false, "Wrong column status");
341      return VarStatus();
342    }
343  }
344
[485]345  SoplexLp::VarStatus SoplexLp::_getRowStatus(int i) const {
[484]346    switch (soplex->getBasisRowStatus(i)) {
347    case soplex::SPxSolver::BASIC:
348      return BASIC;
349    case soplex::SPxSolver::ON_UPPER:
350      return UPPER;
351    case soplex::SPxSolver::ON_LOWER:
352      return LOWER;
353    case soplex::SPxSolver::FIXED:
354      return FIXED;
355    case soplex::SPxSolver::ZERO:
356      return FREE;
357    default:
358      LEMON_ASSERT(false, "Wrong row status");
359      return VarStatus();
360    }
361  }
362
[485]363  SoplexLp::Value SoplexLp::_getPrimalRay(int i) const {
[484]364    if (_primal_ray.empty()) {
365      _primal_ray.resize(soplex->nCols());
366      soplex::Vector pv(_primal_ray.size(), &_primal_ray.front());
367      soplex->getDualfarkas(pv);
368    }
369    return _primal_ray[i];
370  }
371
[485]372  SoplexLp::Value SoplexLp::_getDualRay(int i) const {
[484]373    if (_dual_ray.empty()) {
374      _dual_ray.resize(soplex->nRows());
375      soplex::Vector dv(_dual_ray.size(), &_dual_ray.front());
376      soplex->getDualfarkas(dv);
377    }
378    return _dual_ray[i];
379  }
380
[485]381  SoplexLp::ProblemType SoplexLp::_getPrimalType() const {
[484]382    switch (soplex->status()) {
383    case soplex::SPxSolver::OPTIMAL:
384      return OPTIMAL;
385    case soplex::SPxSolver::UNBOUNDED:
386      return UNBOUNDED;
387    case soplex::SPxSolver::INFEASIBLE:
388      return INFEASIBLE;
389    default:
390      return UNDEFINED;
391    }
392  }
393
[485]394  SoplexLp::ProblemType SoplexLp::_getDualType() const {
[484]395    switch (soplex->status()) {
396    case soplex::SPxSolver::OPTIMAL:
397      return OPTIMAL;
398    case soplex::SPxSolver::UNBOUNDED:
399      return UNBOUNDED;
400    case soplex::SPxSolver::INFEASIBLE:
401      return INFEASIBLE;
402    default:
403      return UNDEFINED;
404    }
405  }
406
[485]407  void SoplexLp::_setSense(Sense sense) {
[484]408    switch (sense) {
409    case MIN:
410      soplex->changeSense(soplex::SPxSolver::MINIMIZE);
411      break;
412    case MAX:
413      soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
414    }
415  }
416
[485]417  SoplexLp::Sense SoplexLp::_getSense() const {
[484]418    switch (soplex->spxSense()) {
419    case soplex::SPxSolver::MAXIMIZE:
420      return MAX;
421    case soplex::SPxSolver::MINIMIZE:
422      return MIN;
423    default:
424      LEMON_ASSERT(false, "Wrong sense.");
[485]425      return SoplexLp::Sense();
[484]426    }
427  }
428
[485]429  void SoplexLp::_clear() {
[484]430    soplex->clear();
431    _col_names.clear();
432    _col_names_ref.clear();
433    _row_names.clear();
434    _row_names_ref.clear();
435    cols.clear();
436    rows.clear();
437    _clear_temporals();
438  }
439
[623]440  void SoplexLp::_messageLevel(MessageLevel level) {
441    switch (level) {
442    case MESSAGE_NOTHING:
443      _message_level = -1;
444      break;
445    case MESSAGE_ERROR:
446      _message_level = soplex::SPxOut::ERROR;
447      break;
448    case MESSAGE_WARNING:
449      _message_level = soplex::SPxOut::WARNING;
450      break;
451    case MESSAGE_NORMAL:
452      _message_level = soplex::SPxOut::INFO2;
453      break;
454    case MESSAGE_VERBOSE:
455      _message_level = soplex::SPxOut::DEBUG;
456      break;
457    }
458  }
459
460  void SoplexLp::_applyMessageLevel() {
461    soplex::Param::setVerbose(_message_level);
462  }
463
[484]464} //namespace lemon
465
Note: See TracBrowser for help on using the repository browser.