lemon/lp_skeleton.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 458 7afc121e0689
child 540 9db62975c32b
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
     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 <lemon/lp_skeleton.h>
    20 
    21 ///\file
    22 ///\brief A skeleton file to implement LP solver interfaces
    23 namespace lemon {
    24 
    25   int SkeletonSolverBase::_addCol()
    26   {
    27     return ++col_num;
    28   }
    29 
    30   int SkeletonSolverBase::_addRow()
    31   {
    32     return ++row_num;
    33   }
    34 
    35   void SkeletonSolverBase::_eraseCol(int) {}
    36   void SkeletonSolverBase::_eraseRow(int) {}
    37 
    38   void SkeletonSolverBase::_getColName(int, std::string &) const {}
    39   void SkeletonSolverBase::_setColName(int, const std::string &) {}
    40   int SkeletonSolverBase::_colByName(const std::string&) const { return -1; }
    41 
    42   void SkeletonSolverBase::_getRowName(int, std::string &) const {}
    43   void SkeletonSolverBase::_setRowName(int, const std::string &) {}
    44   int SkeletonSolverBase::_rowByName(const std::string&) const { return -1; }
    45 
    46   void SkeletonSolverBase::_setRowCoeffs(int, ExprIterator, ExprIterator) {}
    47   void SkeletonSolverBase::_getRowCoeffs(int, InsertIterator) const {}
    48 
    49   void SkeletonSolverBase::_setColCoeffs(int, ExprIterator, ExprIterator) {}
    50   void SkeletonSolverBase::_getColCoeffs(int, InsertIterator) const {}
    51 
    52   void SkeletonSolverBase::_setCoeff(int, int, Value) {}
    53   SkeletonSolverBase::Value SkeletonSolverBase::_getCoeff(int, int) const
    54   { return 0; }
    55 
    56   void SkeletonSolverBase::_setColLowerBound(int, Value) {}
    57   SkeletonSolverBase::Value SkeletonSolverBase::_getColLowerBound(int) const
    58   {  return 0; }
    59 
    60   void SkeletonSolverBase::_setColUpperBound(int, Value) {}
    61   SkeletonSolverBase::Value SkeletonSolverBase::_getColUpperBound(int) const
    62   {  return 0; }
    63 
    64   void SkeletonSolverBase::_setRowLowerBound(int, Value) {}
    65   SkeletonSolverBase::Value SkeletonSolverBase::_getRowLowerBound(int) const
    66   {  return 0; }
    67 
    68   void SkeletonSolverBase::_setRowUpperBound(int, Value) {}
    69   SkeletonSolverBase::Value SkeletonSolverBase::_getRowUpperBound(int) const
    70   {  return 0; }
    71 
    72   void SkeletonSolverBase::_setObjCoeffs(ExprIterator, ExprIterator) {}
    73   void SkeletonSolverBase::_getObjCoeffs(InsertIterator) const {};
    74 
    75   void SkeletonSolverBase::_setObjCoeff(int, Value) {}
    76   SkeletonSolverBase::Value SkeletonSolverBase::_getObjCoeff(int) const
    77   {  return 0; }
    78 
    79   void SkeletonSolverBase::_setSense(Sense) {}
    80   SkeletonSolverBase::Sense SkeletonSolverBase::_getSense() const
    81   { return MIN; }
    82 
    83   void SkeletonSolverBase::_clear() {
    84     row_num = col_num = 0;
    85   }
    86 
    87   LpSkeleton::SolveExitStatus LpSkeleton::_solve() { return SOLVED; }
    88 
    89   LpSkeleton::Value LpSkeleton::_getPrimal(int) const { return 0; }
    90   LpSkeleton::Value LpSkeleton::_getDual(int) const { return 0; }
    91   LpSkeleton::Value LpSkeleton::_getPrimalValue() const { return 0; }
    92 
    93   LpSkeleton::Value LpSkeleton::_getPrimalRay(int) const { return 0; }
    94   LpSkeleton::Value LpSkeleton::_getDualRay(int) const { return 0; }
    95 
    96   LpSkeleton::ProblemType LpSkeleton::_getPrimalType() const
    97   { return UNDEFINED; }
    98 
    99   LpSkeleton::ProblemType LpSkeleton::_getDualType() const
   100   { return UNDEFINED; }
   101 
   102   LpSkeleton::VarStatus LpSkeleton::_getColStatus(int) const
   103   { return BASIC; }
   104 
   105   LpSkeleton::VarStatus LpSkeleton::_getRowStatus(int) const
   106   { return BASIC; }
   107 
   108   LpSkeleton* LpSkeleton::_newSolver() const
   109   { return static_cast<LpSkeleton*>(0); }
   110 
   111   LpSkeleton* LpSkeleton::_cloneSolver() const
   112   { return static_cast<LpSkeleton*>(0); }
   113 
   114   const char* LpSkeleton::_solverName() const { return "LpSkeleton"; }
   115 
   116   MipSkeleton::SolveExitStatus MipSkeleton::_solve()
   117   { return SOLVED; }
   118 
   119   MipSkeleton::Value MipSkeleton::_getSol(int) const { return 0; }
   120   MipSkeleton::Value MipSkeleton::_getSolValue() const { return 0; }
   121 
   122   MipSkeleton::ProblemType MipSkeleton::_getType() const
   123   { return UNDEFINED; }
   124 
   125   MipSkeleton* MipSkeleton::_newSolver() const
   126   { return static_cast<MipSkeleton*>(0); }
   127 
   128   MipSkeleton* MipSkeleton::_cloneSolver() const
   129   { return static_cast<MipSkeleton*>(0); }
   130 
   131   const char* MipSkeleton::_solverName() const { return "MipSkeleton"; }
   132 
   133 } //namespace lemon
   134