lemon/lp_skeleton.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 806 fa6f37d7a25b
parent 576 745e182d0139
child 877 141f9c0db4a3
permissions -rw-r--r--
Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.
deba@458
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@458
     2
 *
deba@458
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@458
     4
 *
deba@458
     5
 * Copyright (C) 2003-2008
deba@458
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@458
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@458
     8
 *
deba@458
     9
 * Permission to use, modify and distribute this software is granted
deba@458
    10
 * provided that this copyright notice appears in all copies. For
deba@458
    11
 * precise terms see the accompanying LICENSE file.
deba@458
    12
 *
deba@458
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@458
    14
 * express or implied, and with no claim as to its suitability for any
deba@458
    15
 * purpose.
deba@458
    16
 *
deba@458
    17
 */
deba@458
    18
deba@458
    19
#include <lemon/lp_skeleton.h>
deba@458
    20
deba@458
    21
///\file
deba@458
    22
///\brief A skeleton file to implement LP solver interfaces
deba@458
    23
namespace lemon {
deba@458
    24
deba@459
    25
  int SkeletonSolverBase::_addCol()
deba@458
    26
  {
deba@458
    27
    return ++col_num;
deba@458
    28
  }
deba@458
    29
deba@459
    30
  int SkeletonSolverBase::_addRow()
deba@458
    31
  {
deba@458
    32
    return ++row_num;
deba@458
    33
  }
deba@458
    34
deba@746
    35
  int SkeletonSolverBase::_addRow(Value, ExprIterator, ExprIterator, Value)
deba@746
    36
  {
deba@746
    37
    return ++row_num;
deba@746
    38
  }
deba@746
    39
deba@459
    40
  void SkeletonSolverBase::_eraseCol(int) {}
deba@459
    41
  void SkeletonSolverBase::_eraseRow(int) {}
deba@459
    42
deba@459
    43
  void SkeletonSolverBase::_getColName(int, std::string &) const {}
deba@459
    44
  void SkeletonSolverBase::_setColName(int, const std::string &) {}
deba@459
    45
  int SkeletonSolverBase::_colByName(const std::string&) const { return -1; }
deba@459
    46
deba@459
    47
  void SkeletonSolverBase::_getRowName(int, std::string &) const {}
deba@459
    48
  void SkeletonSolverBase::_setRowName(int, const std::string &) {}
deba@459
    49
  int SkeletonSolverBase::_rowByName(const std::string&) const { return -1; }
deba@459
    50
deba@459
    51
  void SkeletonSolverBase::_setRowCoeffs(int, ExprIterator, ExprIterator) {}
deba@459
    52
  void SkeletonSolverBase::_getRowCoeffs(int, InsertIterator) const {}
deba@459
    53
deba@459
    54
  void SkeletonSolverBase::_setColCoeffs(int, ExprIterator, ExprIterator) {}
deba@459
    55
  void SkeletonSolverBase::_getColCoeffs(int, InsertIterator) const {}
deba@459
    56
deba@459
    57
  void SkeletonSolverBase::_setCoeff(int, int, Value) {}
deba@459
    58
  SkeletonSolverBase::Value SkeletonSolverBase::_getCoeff(int, int) const
deba@459
    59
  { return 0; }
deba@459
    60
deba@459
    61
  void SkeletonSolverBase::_setColLowerBound(int, Value) {}
deba@459
    62
  SkeletonSolverBase::Value SkeletonSolverBase::_getColLowerBound(int) const
deba@459
    63
  {  return 0; }
deba@459
    64
deba@459
    65
  void SkeletonSolverBase::_setColUpperBound(int, Value) {}
deba@459
    66
  SkeletonSolverBase::Value SkeletonSolverBase::_getColUpperBound(int) const
deba@459
    67
  {  return 0; }
deba@459
    68
deba@459
    69
  void SkeletonSolverBase::_setRowLowerBound(int, Value) {}
deba@459
    70
  SkeletonSolverBase::Value SkeletonSolverBase::_getRowLowerBound(int) const
deba@459
    71
  {  return 0; }
deba@459
    72
deba@459
    73
  void SkeletonSolverBase::_setRowUpperBound(int, Value) {}
deba@459
    74
  SkeletonSolverBase::Value SkeletonSolverBase::_getRowUpperBound(int) const
deba@459
    75
  {  return 0; }
deba@459
    76
deba@459
    77
  void SkeletonSolverBase::_setObjCoeffs(ExprIterator, ExprIterator) {}
deba@459
    78
  void SkeletonSolverBase::_getObjCoeffs(InsertIterator) const {};
deba@459
    79
deba@459
    80
  void SkeletonSolverBase::_setObjCoeff(int, Value) {}
deba@459
    81
  SkeletonSolverBase::Value SkeletonSolverBase::_getObjCoeff(int) const
deba@459
    82
  {  return 0; }
deba@459
    83
deba@459
    84
  void SkeletonSolverBase::_setSense(Sense) {}
deba@459
    85
  SkeletonSolverBase::Sense SkeletonSolverBase::_getSense() const
deba@459
    86
  { return MIN; }
deba@459
    87
deba@459
    88
  void SkeletonSolverBase::_clear() {
deba@459
    89
    row_num = col_num = 0;
deba@458
    90
  }
deba@458
    91
deba@576
    92
  void SkeletonSolverBase::_messageLevel(MessageLevel) {}
deba@576
    93
deba@459
    94
  LpSkeleton::SolveExitStatus LpSkeleton::_solve() { return SOLVED; }
deba@458
    95
deba@459
    96
  LpSkeleton::Value LpSkeleton::_getPrimal(int) const { return 0; }
deba@459
    97
  LpSkeleton::Value LpSkeleton::_getDual(int) const { return 0; }
deba@459
    98
  LpSkeleton::Value LpSkeleton::_getPrimalValue() const { return 0; }
deba@458
    99
deba@459
   100
  LpSkeleton::Value LpSkeleton::_getPrimalRay(int) const { return 0; }
deba@459
   101
  LpSkeleton::Value LpSkeleton::_getDualRay(int) const { return 0; }
deba@458
   102
deba@459
   103
  LpSkeleton::ProblemType LpSkeleton::_getPrimalType() const
deba@459
   104
  { return UNDEFINED; }
deba@458
   105
deba@459
   106
  LpSkeleton::ProblemType LpSkeleton::_getDualType() const
deba@459
   107
  { return UNDEFINED; }
deba@458
   108
deba@459
   109
  LpSkeleton::VarStatus LpSkeleton::_getColStatus(int) const
deba@459
   110
  { return BASIC; }
deba@458
   111
deba@459
   112
  LpSkeleton::VarStatus LpSkeleton::_getRowStatus(int) const
deba@459
   113
  { return BASIC; }
deba@458
   114
alpar@540
   115
  LpSkeleton* LpSkeleton::newSolver() const
deba@459
   116
  { return static_cast<LpSkeleton*>(0); }
deba@458
   117
alpar@540
   118
  LpSkeleton* LpSkeleton::cloneSolver() const
deba@459
   119
  { return static_cast<LpSkeleton*>(0); }
deba@458
   120
deba@459
   121
  const char* LpSkeleton::_solverName() const { return "LpSkeleton"; }
deba@458
   122
deba@459
   123
  MipSkeleton::SolveExitStatus MipSkeleton::_solve()
deba@459
   124
  { return SOLVED; }
deba@458
   125
deba@459
   126
  MipSkeleton::Value MipSkeleton::_getSol(int) const { return 0; }
deba@459
   127
  MipSkeleton::Value MipSkeleton::_getSolValue() const { return 0; }
deba@458
   128
deba@459
   129
  MipSkeleton::ProblemType MipSkeleton::_getType() const
deba@459
   130
  { return UNDEFINED; }
deba@458
   131
alpar@540
   132
  MipSkeleton* MipSkeleton::newSolver() const
deba@459
   133
  { return static_cast<MipSkeleton*>(0); }
deba@458
   134
alpar@540
   135
  MipSkeleton* MipSkeleton::cloneSolver() const
deba@459
   136
  { return static_cast<MipSkeleton*>(0); }
deba@458
   137
deba@459
   138
  const char* MipSkeleton::_solverName() const { return "MipSkeleton"; }
deba@458
   139
deba@458
   140
} //namespace lemon
deba@458
   141