Location: LEMON/LEMON-official/lemon/lp_skeleton.cc - annotation
Load file history
Support negative costs and bounds in NetworkSimplex (#270)
* The interface is reworked to support negative costs and bounds.
- ProblemType and problemType() are renamed to
SupplyType and supplyType(), see also #234.
- ProblemType type is introduced similarly to the LP interface.
- 'bool run()' is replaced by 'ProblemType run()' to handle
unbounded problem instances, as well.
- Add INF public member constant similarly to the LP interface.
* Remove capacityMap() and boundMaps(), see also #266.
* Update the problem definition in the MCF module.
* Remove the usage of Circulation (and adaptors) for checking feasibility.
Check feasibility by examining the artifical arcs instead (after solving
the problem).
* Additional check for unbounded negative cycles found during the
algorithm (it is possible now, since negative costs are allowed).
* Fix in the constructor (the value types needn't be integer any more),
see also #254.
* Improve and extend the doc.
* Rework the test file and add test cases for negative costs and bounds.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 | r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r482:ed54c0d13df0 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r482:ed54c0d13df0 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r481:7afc121e0689 r481:7afc121e0689 r623:745e182d0139 r623:745e182d0139 r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r482:ed54c0d13df0 r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r482:ed54c0d13df0 r481:7afc121e0689 r587:9db62975c32b r482:ed54c0d13df0 r481:7afc121e0689 r587:9db62975c32b r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r482:ed54c0d13df0 r481:7afc121e0689 r587:9db62975c32b r482:ed54c0d13df0 r481:7afc121e0689 r587:9db62975c32b r482:ed54c0d13df0 r481:7afc121e0689 r482:ed54c0d13df0 r481:7afc121e0689 r481:7afc121e0689 r481:7afc121e0689 | /* -*- mode: C++; indent-tabs-mode: nil; -*-
*
* This file is a part of LEMON, a generic C++ optimization library.
*
* Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
*
* Permission to use, modify and distribute this software is granted
* provided that this copyright notice appears in all copies. For
* precise terms see the accompanying LICENSE file.
*
* This software is provided "AS IS" with no warranty of any kind,
* express or implied, and with no claim as to its suitability for any
* purpose.
*
*/
#include <lemon/lp_skeleton.h>
///\file
///\brief A skeleton file to implement LP solver interfaces
namespace lemon {
int SkeletonSolverBase::_addCol()
{
return ++col_num;
}
int SkeletonSolverBase::_addRow()
{
return ++row_num;
}
void SkeletonSolverBase::_eraseCol(int) {}
void SkeletonSolverBase::_eraseRow(int) {}
void SkeletonSolverBase::_getColName(int, std::string &) const {}
void SkeletonSolverBase::_setColName(int, const std::string &) {}
int SkeletonSolverBase::_colByName(const std::string&) const { return -1; }
void SkeletonSolverBase::_getRowName(int, std::string &) const {}
void SkeletonSolverBase::_setRowName(int, const std::string &) {}
int SkeletonSolverBase::_rowByName(const std::string&) const { return -1; }
void SkeletonSolverBase::_setRowCoeffs(int, ExprIterator, ExprIterator) {}
void SkeletonSolverBase::_getRowCoeffs(int, InsertIterator) const {}
void SkeletonSolverBase::_setColCoeffs(int, ExprIterator, ExprIterator) {}
void SkeletonSolverBase::_getColCoeffs(int, InsertIterator) const {}
void SkeletonSolverBase::_setCoeff(int, int, Value) {}
SkeletonSolverBase::Value SkeletonSolverBase::_getCoeff(int, int) const
{ return 0; }
void SkeletonSolverBase::_setColLowerBound(int, Value) {}
SkeletonSolverBase::Value SkeletonSolverBase::_getColLowerBound(int) const
{ return 0; }
void SkeletonSolverBase::_setColUpperBound(int, Value) {}
SkeletonSolverBase::Value SkeletonSolverBase::_getColUpperBound(int) const
{ return 0; }
void SkeletonSolverBase::_setRowLowerBound(int, Value) {}
SkeletonSolverBase::Value SkeletonSolverBase::_getRowLowerBound(int) const
{ return 0; }
void SkeletonSolverBase::_setRowUpperBound(int, Value) {}
SkeletonSolverBase::Value SkeletonSolverBase::_getRowUpperBound(int) const
{ return 0; }
void SkeletonSolverBase::_setObjCoeffs(ExprIterator, ExprIterator) {}
void SkeletonSolverBase::_getObjCoeffs(InsertIterator) const {};
void SkeletonSolverBase::_setObjCoeff(int, Value) {}
SkeletonSolverBase::Value SkeletonSolverBase::_getObjCoeff(int) const
{ return 0; }
void SkeletonSolverBase::_setSense(Sense) {}
SkeletonSolverBase::Sense SkeletonSolverBase::_getSense() const
{ return MIN; }
void SkeletonSolverBase::_clear() {
row_num = col_num = 0;
}
void SkeletonSolverBase::_messageLevel(MessageLevel) {}
LpSkeleton::SolveExitStatus LpSkeleton::_solve() { return SOLVED; }
LpSkeleton::Value LpSkeleton::_getPrimal(int) const { return 0; }
LpSkeleton::Value LpSkeleton::_getDual(int) const { return 0; }
LpSkeleton::Value LpSkeleton::_getPrimalValue() const { return 0; }
LpSkeleton::Value LpSkeleton::_getPrimalRay(int) const { return 0; }
LpSkeleton::Value LpSkeleton::_getDualRay(int) const { return 0; }
LpSkeleton::ProblemType LpSkeleton::_getPrimalType() const
{ return UNDEFINED; }
LpSkeleton::ProblemType LpSkeleton::_getDualType() const
{ return UNDEFINED; }
LpSkeleton::VarStatus LpSkeleton::_getColStatus(int) const
{ return BASIC; }
LpSkeleton::VarStatus LpSkeleton::_getRowStatus(int) const
{ return BASIC; }
LpSkeleton* LpSkeleton::newSolver() const
{ return static_cast<LpSkeleton*>(0); }
LpSkeleton* LpSkeleton::cloneSolver() const
{ return static_cast<LpSkeleton*>(0); }
const char* LpSkeleton::_solverName() const { return "LpSkeleton"; }
MipSkeleton::SolveExitStatus MipSkeleton::_solve()
{ return SOLVED; }
MipSkeleton::Value MipSkeleton::_getSol(int) const { return 0; }
MipSkeleton::Value MipSkeleton::_getSolValue() const { return 0; }
MipSkeleton::ProblemType MipSkeleton::_getType() const
{ return UNDEFINED; }
MipSkeleton* MipSkeleton::newSolver() const
{ return static_cast<MipSkeleton*>(0); }
MipSkeleton* MipSkeleton::cloneSolver() const
{ return static_cast<MipSkeleton*>(0); }
const char* MipSkeleton::_solverName() const { return "MipSkeleton"; }
} //namespace lemon
|