Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
20 #include<lemon/lp_soplex.h>
22 #include <soplex/soplex.h>
26 ///\brief Implementation of the LEMON-SOPLEX lp solver interface.
29 LpSoplex::LpSoplex() : LpSolverBase() {
30 rows.setIdHandler(relocateIdHandler);
31 cols.setIdHandler(relocateIdHandler);
32 soplex = new soplex::SoPlex;
36 LpSoplex::~LpSoplex() {
40 LpSolverBase &LpSoplex::_newLp() {
41 LpSoplex* newlp = new LpSoplex();
45 LpSolverBase &LpSoplex::_copyLp() {
46 LpSoplex* newlp = new LpSoplex();
47 (*static_cast<soplex::SPxLP*>(newlp->soplex)) = *soplex;
51 int LpSoplex::_addCol() {
53 c.setLower(-soplex::infinity);
54 c.setUpper(soplex::infinity);
57 colNames.push_back(std::string());
58 primal_value.push_back(0.0);
61 return soplex->nCols() - 1;
64 int LpSoplex::_addRow() {
66 r.setLhs(-soplex::infinity);
67 r.setRhs(soplex::infinity);
70 dual_value.push_back(0.0);
73 return soplex->nRows() - 1;
77 void LpSoplex::_eraseCol(int i) {
79 invColNames.erase(colNames[i]);
80 colNames[i] = colNames.back();
81 invColNames[colNames.back()] = i;
83 primal_value[i] = primal_value.back();
84 primal_value.pop_back();
88 void LpSoplex::_eraseRow(int i) {
90 dual_value[i] = dual_value.back();
91 dual_value.pop_back();
95 void LpSoplex::_getColName(int c, std::string &name) const {
99 void LpSoplex::_setColName(int c, const std::string &name) {
100 invColNames.erase(colNames[c]);
103 invColNames.insert(std::make_pair(name, c));
107 int LpSoplex::_colByName(const std::string& name) const {
108 std::map<std::string, int>::const_iterator it =
109 invColNames.find(name);
110 if (it != invColNames.end()) {
118 void LpSoplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e) {
119 for (int j = 0; j < soplex->nCols(); ++j) {
120 soplex->changeElement(i, j, 0.0);
122 for(ConstRowIterator it = b; it != e; ++it) {
123 soplex->changeElement(i, it->first, it->second);
128 void LpSoplex::_getRowCoeffs(int i, RowIterator b) const {
129 const soplex::SVector& vec = soplex->rowVector(i);
130 for (int k = 0; k < vec.size(); ++k) {
131 *b = std::make_pair(vec.index(k), vec.value(k));
136 void LpSoplex::_setColCoeffs(int j, ConstColIterator b, ConstColIterator e) {
137 for (int i = 0; i < soplex->nRows(); ++i) {
138 soplex->changeElement(i, j, 0.0);
140 for(ConstColIterator it = b; it != e; ++it) {
141 soplex->changeElement(it->first, j, it->second);
146 void LpSoplex::_getColCoeffs(int i, ColIterator b) const {
147 const soplex::SVector& vec = soplex->colVector(i);
148 for (int k = 0; k < vec.size(); ++k) {
149 *b = std::make_pair(vec.index(k), vec.value(k));
154 void LpSoplex::_setCoeff(int i, int j, Value value) {
155 soplex->changeElement(i, j, value);
159 LpSoplex::Value LpSoplex::_getCoeff(int i, int j) const {
160 return soplex->rowVector(i)[j];
163 void LpSoplex::_setColLowerBound(int i, Value value) {
164 soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
168 LpSoplex::Value LpSoplex::_getColLowerBound(int i) const {
169 double value = soplex->lower(i);
170 return value != -soplex::infinity ? value : -INF;
173 void LpSoplex::_setColUpperBound(int i, Value value) {
174 soplex->changeUpper(i, value != INF ? value : soplex::infinity);
178 LpSoplex::Value LpSoplex::_getColUpperBound(int i) const {
179 double value = soplex->upper(i);
180 return value != soplex::infinity ? value : INF;
183 void LpSoplex::_setRowBounds(int i, Value lb, Value ub) {
184 soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity,
185 ub != INF ? ub : soplex::infinity);
188 void LpSoplex::_getRowBounds(int i, Value &lower, Value &upper) const {
189 lower = soplex->lhs(i);
190 if (lower == -soplex::infinity) lower = -INF;
191 upper = soplex->rhs(i);
192 if (upper == -soplex::infinity) upper = INF;
195 void LpSoplex::_setObjCoeff(int i, Value obj_coef) {
196 soplex->changeObj(i, obj_coef);
200 LpSoplex::Value LpSoplex::_getObjCoeff(int i) const {
201 return soplex->obj(i);
204 void LpSoplex::_clearObj() {
205 for (int i = 0; i < soplex->nCols(); ++i) {
206 soplex->changeObj(i, 0.0);
211 LpSoplex::SolveExitStatus LpSoplex::_solve() {
212 soplex::SPxSolver::Status status = soplex->solve();
214 soplex::Vector pv(primal_value.size(), &primal_value[0]);
215 soplex->getPrimal(pv);
217 soplex::Vector dv(dual_value.size(), &dual_value[0]);
221 case soplex::SPxSolver::OPTIMAL:
222 case soplex::SPxSolver::INFEASIBLE:
223 case soplex::SPxSolver::UNBOUNDED:
231 LpSoplex::Value LpSoplex::_getPrimal(int i) const {
232 return primal_value[i];
235 LpSoplex::Value LpSoplex::_getDual(int i) const {
236 return dual_value[i];
239 LpSoplex::Value LpSoplex::_getPrimalValue() const {
240 return soplex->objValue();
243 bool LpSoplex::_isBasicCol(int i) const {
244 return soplex->getBasisColStatus(i) == soplex::SPxSolver::BASIC;
247 LpSoplex::SolutionStatus LpSoplex::_getPrimalStatus() const {
248 if (!solved) return UNDEFINED;
249 switch (soplex->status()) {
250 case soplex::SPxSolver::OPTIMAL:
252 case soplex::SPxSolver::UNBOUNDED:
254 case soplex::SPxSolver::INFEASIBLE:
261 LpSoplex::SolutionStatus LpSoplex::_getDualStatus() const {
262 if (!solved) return UNDEFINED;
263 switch (soplex->status()) {
264 case soplex::SPxSolver::OPTIMAL:
266 case soplex::SPxSolver::UNBOUNDED:
273 LpSoplex::ProblemTypes LpSoplex::_getProblemType() const {
274 if (!solved) return UNKNOWN;
275 switch (soplex->status()) {
276 case soplex::SPxSolver::OPTIMAL:
277 return PRIMAL_DUAL_FEASIBLE;
278 case soplex::SPxSolver::UNBOUNDED:
279 return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
285 void LpSoplex::_setMax() {
286 soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
289 void LpSoplex::_setMin() {
290 soplex->changeSense(soplex::SPxSolver::MINIMIZE);
293 bool LpSoplex::_isMax() const {
294 return soplex->spxSense() == soplex::SPxSolver::MAXIMIZE;