LEMON/LEMON-official Changeset - r981:cbf32bf95954

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r981:cbf32bf95954

« 924:520514
« 978:e26ad3

985:f63fd2 »

r981:cbf32bf95954

Mon, 03 May 2010 10:24:52

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge bugfix #368 to branch 1.2

0 1 0

merge 1.2

1 file changed with 2 insertions and 2 deletions:

lemon/network_simplex.h

↑ Collapse diff ↑

lemon/network_simplex.h

Show inline comments

@@ -1056,49 +1056,49 @@

      // Remove non-zero lower bounds
      if (_have_lower) {
        for (int i = 0; i != _arc_num; ++i) {
          Value c = _lower[i];
          if (c >= 0) {
            _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
          } else {
            _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
          }
          _supply[_source[i]] -= c;
          _supply[_target[i]] += c;
        }
      } else {
        for (int i = 0; i != _arc_num; ++i) {
          _cap[i] = _upper[i];
        }
      }

      // Initialize artifical cost
      Cost ART_COST;
      if (std::numeric_limits<Cost>::is_exact) {
        ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
      } else {
        ART_COST = std::numeric_limits<Cost>::min();
        ART_COST = 0;
        for (int i = 0; i != _arc_num; ++i) {
          if (_cost[i] > ART_COST) ART_COST = _cost[i];
        }
        ART_COST = (ART_COST + 1) * _node_num;
      }

      // Initialize arc maps
      for (int i = 0; i != _arc_num; ++i) {
        _flow[i] = 0;
        _state[i] = STATE_LOWER;
      }

      // Set data for the artificial root node
      _root = _node_num;
      _parent[_root] = -1;
      _pred[_root] = -1;
      _thread[_root] = 0;
      _rev_thread[0] = _root;
      _succ_num[_root] = _node_num + 1;
      _last_succ[_root] = _root - 1;
      _supply[_root] = -_sum_supply;
      _pi[_root] = 0;

      // Add artificial arcs and initialize the spanning tree data structure
@@ -1568,49 +1568,49 @@
        }
      }

      // Check feasibility
      for (int e = _search_arc_num; e != _all_arc_num; ++e) {
        if (_flow[e] != 0) return INFEASIBLE;
      }

      // Transform the solution and the supply map to the original form
      if (_have_lower) {
        for (int i = 0; i != _arc_num; ++i) {
          Value c = _lower[i];
          if (c != 0) {
            _flow[i] += c;
            _supply[_source[i]] += c;
            _supply[_target[i]] -= c;
          }
        }
      }

      // Shift potentials to meet the requirements of the GEQ/LEQ type
      // optimality conditions
      if (_sum_supply == 0) {
        if (_stype == GEQ) {
          Cost max_pot = std::numeric_limits<Cost>::min();
          Cost max_pot = -std::numeric_limits<Cost>::max();
          for (int i = 0; i != _node_num; ++i) {
            if (_pi[i] > max_pot) max_pot = _pi[i];
          }
          if (max_pot > 0) {
            for (int i = 0; i != _node_num; ++i)
              _pi[i] -= max_pot;
          }
        } else {
          Cost min_pot = std::numeric_limits<Cost>::max();
          for (int i = 0; i != _node_num; ++i) {
            if (_pi[i] < min_pot) min_pot = _pi[i];
          }
          if (min_pot < 0) {
            for (int i = 0; i != _node_num; ++i)
              _pi[i] -= min_pot;
          }
        }
      }

      return OPTIMAL;
    }

  }; //class NetworkSimplex


0 comments (0 inline)

...	...	@@ -1056,49 +1056,49 @@
1056	1056
1057	1057	// Remove non-zero lower bounds
1058	1058	if (_have_lower) {
1059	1059	for (int i = 0; i != _arc_num; ++i) {
1060	1060	Value c = _lower[i];
1061	1061	if (c >= 0) {
1062	1062	_cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
1063	1063	} else {
1064	1064	_cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
1065	1065	}
1066	1066	_supply[_source[i]] -= c;
1067	1067	_supply[_target[i]] += c;
1068	1068	}
1069	1069	} else {
1070	1070	for (int i = 0; i != _arc_num; ++i) {
1071	1071	_cap[i] = _upper[i];
1072	1072	}
1073	1073	}
1074	1074
1075	1075	// Initialize artifical cost
1076	1076	Cost ART_COST;
1077	1077	if (std::numeric_limits<Cost>::is_exact) {
1078	1078	ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
1079	1079	} else {
1080		ART_COST = ~~std::numeric_limits<Cost>::min()~~;
	1080	ART_COST = 0;
1081	1081	for (int i = 0; i != _arc_num; ++i) {
1082	1082	if (_cost[i] > ART_COST) ART_COST = _cost[i];
1083	1083	}
1084	1084	ART_COST = (ART_COST + 1) * _node_num;
1085	1085	}
1086	1086
1087	1087	// Initialize arc maps
1088	1088	for (int i = 0; i != _arc_num; ++i) {
1089	1089	_flow[i] = 0;
1090	1090	_state[i] = STATE_LOWER;
1091	1091	}
1092	1092
1093	1093	// Set data for the artificial root node
1094	1094	_root = _node_num;
1095	1095	_parent[_root] = -1;
1096	1096	_pred[_root] = -1;
1097	1097	_thread[_root] = 0;
1098	1098	_rev_thread[0] = _root;
1099	1099	_succ_num[_root] = _node_num + 1;
1100	1100	_last_succ[_root] = _root - 1;
1101	1101	_supply[_root] = -_sum_supply;
1102	1102	_pi[_root] = 0;
1103	1103
1104	1104	// Add artificial arcs and initialize the spanning tree data structure
...	...	@@ -1568,49 +1568,49 @@
1568	1568	}
1569	1569	}
1570	1570
1571	1571	// Check feasibility
1572	1572	for (int e = _search_arc_num; e != _all_arc_num; ++e) {
1573	1573	if (_flow[e] != 0) return INFEASIBLE;
1574	1574	}
1575	1575
1576	1576	// Transform the solution and the supply map to the original form
1577	1577	if (_have_lower) {
1578	1578	for (int i = 0; i != _arc_num; ++i) {
1579	1579	Value c = _lower[i];
1580	1580	if (c != 0) {
1581	1581	_flow[i] += c;
1582	1582	_supply[_source[i]] += c;
1583	1583	_supply[_target[i]] -= c;
1584	1584	}
1585	1585	}
1586	1586	}
1587	1587
1588	1588	// Shift potentials to meet the requirements of the GEQ/LEQ type
1589	1589	// optimality conditions
1590	1590	if (_sum_supply == 0) {
1591	1591	if (_stype == GEQ) {
1592		Cost max_pot = std::numeric_limits<Cost>::~~min~~();
	1592	Cost max_pot = -std::numeric_limits<Cost>::max();
1593	1593	for (int i = 0; i != _node_num; ++i) {
1594	1594	if (_pi[i] > max_pot) max_pot = _pi[i];
1595	1595	}
1596	1596	if (max_pot > 0) {
1597	1597	for (int i = 0; i != _node_num; ++i)
1598	1598	_pi[i] -= max_pot;
1599	1599	}
1600	1600	} else {
1601	1601	Cost min_pot = std::numeric_limits<Cost>::max();
1602	1602	for (int i = 0; i != _node_num; ++i) {
1603	1603	if (_pi[i] < min_pot) min_pot = _pi[i];
1604	1604	}
1605	1605	if (min_pot < 0) {
1606	1606	for (int i = 0; i != _node_num; ++i)
1607	1607	_pi[i] -= min_pot;
1608	1608	}
1609	1609	}
1610	1610	}
1611	1611
1612	1612	return OPTIMAL;
1613	1613	}
1614	1614
1615	1615	}; //class NetworkSimplex
1616	1616

RhodeCode

Login to your account