Changeset 1318:ce1533650f7d in lemon

Ignore:
Timestamp:
07/07/14 15:40:12 (4 years ago)
Branch:
default
Children:
1319:11de70cf8550, 1322:1552352f9798
Parents:
1315:07cd9a2d20e0 (diff), 1317:b40c2bbb8da5 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge bugfix #474

Files:
4 edited

Unmodified
Added
Removed
• lemon/network_simplex.h

 r1298 _node_id[n] = i; } if (_arc_mixing) { if (_arc_mixing && _node_num > 1) { // Store the arcs in a mixed order const int skip = std::max(_arc_num / _node_num, 3);
• lemon/network_simplex.h

 r1317 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2010 * Copyright (C) 2003-2013 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \ref NetworkSimplex implements the primal Network Simplex algorithm /// for finding a \ref min_cost_flow "minimum cost flow" /// \ref amo93networkflows, \ref dantzig63linearprog, /// \ref kellyoneill91netsimplex. /// \cite amo93networkflows, \cite dantzig63linearprog, /// \cite kellyoneill91netsimplex. /// This algorithm is a highly efficient specialized version of the /// linear programming simplex method directly for the minimum cost /// flow problem. /// /// In general, %NetworkSimplex is the fastest implementation available /// in LEMON for this problem. /// Moreover, it supports both directions of the supply/demand inequality /// constraints. For more information, see \ref SupplyType. /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest /// implementations available in LEMON for solving this problem. /// (For more information, see \ref min_cost_flow_algs "the module page".) /// Furthermore, this class supports both directions of the supply/demand /// inequality constraints. For more information, see \ref SupplyType. /// /// Most of the parameters of the problem (except for the digraph) /// algorithm. By default, it is the same as \c V. /// /// \warning Both number types must be signed and all input data must /// \warning Both \c V and \c C must be signed number types. /// \warning All input data (capacities, supply values, and costs) must /// be integer. /// /// the \ref run() function. /// /// \ref NetworkSimplex provides five different pivot rule /// implementations that significantly affect the running time /// \ref NetworkSimplex provides five different implementations for /// the pivot strategy that significantly affects the running time /// of the algorithm. /// By default, \ref BLOCK_SEARCH "Block Search" is used, which /// proved to be the most efficient and the most robust on various /// test inputs. /// However, another pivot rule can be selected using the \ref run() /// function with the proper parameter. /// According to experimental tests conducted on various problem /// instances, \ref BLOCK_SEARCH "Block Search" and /// \ref ALTERING_LIST "Altering Candidate List" rules turned out /// to be the most efficient. /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that /// seemed to be slightly more robust, it is used by default. /// However, another pivot rule can easily be selected using the /// \ref run() function with the proper parameter. enum PivotRule { /// The \e Altering \e Candidate \e List pivot rule. /// It is a modified version of the Candidate List method. /// It keeps only the several best eligible arcs from the former /// It keeps only a few of the best eligible arcs from the former /// candidate list and extends this list in every iteration. ALTERING_LIST typedef std::vector CostVector; typedef std::vector CharVector; // Note: vector is used instead of vector and // Note: vector is used instead of vector and // vector for efficiency reasons // Parameters of the problem bool _have_lower; bool _has_lower; SupplyType _stype; Value _sum_supply; SortFunc(const CostVector &map) : _map(map) {} bool operator()(int left, int right) { return _map[left] > _map[right]; return _map[left] < _map[right]; } }; const double BLOCK_SIZE_FACTOR = 1.0; const int MIN_BLOCK_SIZE = 10; const double HEAD_LENGTH_FACTOR = 0.1; const double HEAD_LENGTH_FACTOR = 0.01; const int MIN_HEAD_LENGTH = 3; } for (e = 0; e != _next_arc; ++e) { _cand_cost[e] = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); if (_cand_cost[e] < 0) { c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); if (c < 0) { _cand_cost[e] = c; _candidates[_curr_length++] = e; } search_end: // Make heap of the candidate list (approximating a partial sort) make_heap( _candidates.begin(), _candidates.begin() + _curr_length, _sort_func ); // Pop the first element of the heap // Perform partial sort operation on the candidate list int new_length = std::min(_head_length + 1, _curr_length); std::partial_sort(_candidates.begin(), _candidates.begin() + new_length, _candidates.begin() + _curr_length, _sort_func); // Select the entering arc and remove it from the list _in_arc = _candidates[0]; _next_arc = e; pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, _sort_func ); _curr_length = std::min(_head_length, _curr_length - 1); _candidates[0] = _candidates[new_length - 1]; _curr_length = new_length - 1; return true; } template NetworkSimplex& lowerMap(const LowerMap& map) { _have_lower = true; _has_lower = true; for (ArcIt a(_graph); a != INVALID; ++a) { _lower[_arc_id[a]] = map[a]; /// /// \return (*this) /// /// \sa supplyType() template NetworkSimplex& supplyMap(const SupplyMap& map) { /// /// Using this function has the same effect as using \ref supplyMap() /// with such a map in which \c k is assigned to \c s, \c -k is /// with a map in which \c k is assigned to \c s, \c -k is /// assigned to \c t and all other nodes have zero supply value. /// _cost[i] = 1; } _have_lower = false; _has_lower = false; _stype = GEQ; return *this; /// /// This function returns the total cost of the found flow. /// Its complexity is O(e). /// Its complexity is O(m). /// /// \note The return type of the function can be specified as a } /// \brief Return the flow map (the primal solution). /// \brief Copy the flow values (the primal solution) into the /// given map. /// /// This function copies the flow value on each arc into the given } /// \brief Return the potential map (the dual solution). /// \brief Copy the potential values (the dual solution) into the /// given map. /// /// This function copies the potential (dual value) of each node (_stype == LEQ && _sum_supply >= 0)) ) return false; // Check lower and upper bounds LEMON_DEBUG(checkBoundMaps(), "Upper bounds must be greater or equal to the lower bounds"); // Remove non-zero lower bounds if (_have_lower) { if (_has_lower) { for (int i = 0; i != _arc_num; ++i) { Value c = _lower[i]; } // Check if the upper bound is greater than or equal to the lower bound // on each arc. bool checkBoundMaps() { for (int j = 0; j != _arc_num; ++j) { if (_upper[j] < _lower[j]) return false; } return true; } // Find the join node void findJoinNode() { } } else { // Find the min. cost incomming arc for each demand node // Find the min. cost incoming arc for each demand node for (int i = 0; i != int(demand_nodes.size()); ++i) { Node v = demand_nodes[i]; // Transform the solution and the supply map to the original form if (_have_lower) { if (_has_lower) { for (int i = 0; i != _arc_num; ++i) { Value c = _lower[i];
• test/min_cost_flow_test.cc

 r1270 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, mcf3.OPTIMAL, true,     -300, test_str + "-18", GEQ); // Tests for empty graph Digraph gr0; MCF mcf0(gr0); mcf0.run(param); check(mcf0.totalCost() == 0, "Wrong total cost"); }
• test/min_cost_flow_test.cc

 r1317 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2010 * Copyright (C) 2003-2013 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES).
Note: See TracChangeset for help on using the changeset viewer.