-
Notifications
You must be signed in to change notification settings - Fork 9
/
Copy pathRelaxIV_8h.html
155 lines (154 loc) · 11.6 KB
/
RelaxIV_8h.html
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-US">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
<meta name="generator" content="Doxygen 1.9.7"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>The MCFClass Project: RelaxIV.h File Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js", "TeX/AMSmath.js"],
jax: ["input/TeX","output/HTML-CSS"],
});
</script>
<script type="text/javascript" async="async" src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr id="projectrow">
<td id="projectalign">
<div id="projectname">The MCFClass Project
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.9.7 -->
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() {
initMenu('',false,false,'search.php','Search');
});
/* @license-end */
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(document).ready(function(){initNavTree('RelaxIV_8h.html',''); initResizable(); });
/* @license-end */
</script>
<div id="doc-content">
<div class="header">
<div class="summary">
<a href="#nested-classes">Classes</a> |
<a href="#namespaces">Namespaces</a> |
<a href="#define-members">Macros</a> </div>
<div class="headertitle"><div class="title">RelaxIV.h File Reference</div></div>
</div><!--header-->
<div class="contents">
<p>Linear Min Cost Flow problems solver, based on the RELAXIV code by D.
<a href="#details">More...</a></p>
<div class="textblock"><code>#include "<a class="el" href="MCFClass_8h.html">MCFClass.h</a>"</code><br />
</div><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a id="nested-classes" name="nested-classes"></a>
Classes</h2></td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">class  </td><td class="memItemRight" valign="bottom"><a class="el" href="classMCFClass__di__unipi__it_1_1RelaxIV.html">RelaxIV</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft"> </td><td class="mdescRight">The <a class="el" href="classMCFClass__di__unipi__it_1_1RelaxIV.html" title="The RelaxIV class derives from the abstract base class MCFClass, thus sharing its (standard) interfac...">RelaxIV</a> class derives from the abstract base class <a class="el" href="classMCFClass__di__unipi__it_1_1MCFClass.html" title="This abstract base class defines a standard interface for (linear or convex quadartic separable) Min ...">MCFClass</a>, thus sharing its (standard) interface, and implements a Relaxation algorithm for solving (Linear) Min Cost Flow problems. <a href="classMCFClass__di__unipi__it_1_1RelaxIV.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a id="namespaces" name="namespaces"></a>
Namespaces</h2></td></tr>
<tr class="memitem:namespaceMCFClass__di__unipi__it"><td class="memItemLeft" align="right" valign="top">namespace  </td><td class="memItemRight" valign="bottom"><a class="el" href="namespaceMCFClass__di__unipi__it.html">MCFClass_di_unipi_it</a></td></tr>
<tr class="memdesc:namespaceMCFClass__di__unipi__it"><td class="mdescLeft"> </td><td class="mdescRight">The namespace <a class="el" href="namespaceMCFClass__di__unipi__it.html" title="The namespace MCFClass_di_unipi_it is defined to hold the MCFClass class and all the relative stuff.">MCFClass_di_unipi_it</a> is defined to hold the <a class="el" href="classMCFClass__di__unipi__it_1_1MCFClass.html" title="This abstract base class defines a standard interface for (linear or convex quadartic separable) Min ...">MCFClass</a> class and all the relative stuff. <br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a id="define-members" name="define-members"></a>
Macros</h2></td></tr>
<tr class="memitem:ga3b63fe7f4beec71fa40afff6858f5d56"><td class="memItemLeft" align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="group__RELAXIV__MACROS.html#ga3b63fe7f4beec71fa40afff6858f5d56">DYNMC_MCF_RIV</a>   3</td></tr>
<tr class="memdesc:ga3b63fe7f4beec71fa40afff6858f5d56"><td class="mdescLeft"> </td><td class="mdescRight">Decides if the graph topology (arcs, nodes) can be changed. <br /></td></tr>
<tr class="separator:ga3b63fe7f4beec71fa40afff6858f5d56"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ga068502598143c198df29df94602aae0b"><td class="memItemLeft" align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="group__RELAXIV__MACROS.html#ga068502598143c198df29df94602aae0b">AUCTION</a>   0</td></tr>
<tr class="memdesc:ga068502598143c198df29df94602aae0b"><td class="mdescLeft"> </td><td class="mdescRight">Decides if the auction/shortest paths inizialization procedure is used. <br /></td></tr>
<tr class="separator:ga068502598143c198df29df94602aae0b"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ga48834f5e7df3d1bc4d337c0a43f4f196"><td class="memItemLeft" align="right" valign="top">
#define </td><td class="memItemRight" valign="bottom"><b>RELAXIV_STATISTICS</b>   0</td></tr>
<tr class="memdesc:ga48834f5e7df3d1bc4d337c0a43f4f196"><td class="mdescLeft"> </td><td class="mdescRight">If RELAXIV_STATISTICS > 0, then statistic information about the behaviour of the Relaxation algorithm is computed. <br /></td></tr>
<tr class="separator:ga48834f5e7df3d1bc4d337c0a43f4f196"><td class="memSeparator" colspan="2"> </td></tr>
</table>
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
<div class="textblock"><p>Linear Min Cost Flow problems solver, based on the RELAXIV code by D. </p>
<p>Bertsekas and P. Tseng, as described in</p>
<p>Bertsekas, Dimitri P., and Paul Tseng. "RELAX-IV: A faster version of the RELAX code for solving minimum
cost flow problems." (1994), Report LIDS-P-2276, MIT.</p>
<p>Conforms to the standard (MCF) interface defined in <a class="el" href="MCFClass_8h.html" title="Header file for the abstract base class MCFClass, which defines a standard interface for (linear or c...">MCFClass.h</a>.</p>
<p>RelaxIV is based on a primal-dual algorithm which essentially operates as follows: a pseudoflow (a flow vector which satisfies bound and non-negativity constraints but not necessarily flow conservation constraints) is kept which satisfies complementarity slackness conditions with the current vector of potentials; that is, only the flow on arcs whose reduced cost </p><p class="formulaDsp">
\[
RC[ i , j ] = C[ i , j ] - Pi[ j ] + Pi[ i ]
\]
</p>
<p> is zero can be chosen to any value between 0 and the capacity, while arcs with reduced cost < 0 are saturated (fixed to their capacity) and arcs with reduced cost > 0 are empty (fixed to 0).</p>
<p>The algorithm attempts to convert the pseudoflow into a flow (i.e., to satisfy the flow conservation constraints) by essentially running a max-flow algorithm of the augmenting path type. If the flow is found then this is an optimal solution of the problem and the algorithm is stopped. Otherwise, a saturated cut is identified which separates the origins (nodes not yet producing enough flow) to the destinations (nodes not yet consuming enough flow); this cut is used to modify the potentials, thereby creating new arcs with zero reduced cost, which can be used to push further flow from the origins to the destinations. If no such arcs can be created the problem is declared unfeasible. Much care is devoted to stop the max-flow computation as soon as a proof that the set of potentials is not optimal, in order to reach as soon as possible a dual optimal solution, and to re-use all available information to "warm start" the max-flow computation after a change in the potentials.</p>
<dl class="section warning"><dt>Warning</dt><dd>The original code has been written for integer data only. By properly setting the flow and cost tolerances [see SetEps****() in <a class="el" href="MCFClass_8h.html" title="Header file for the abstract base class MCFClass, which defines a standard interface for (linear or c...">MCFClass.h</a>] we have always been able to solve any MCF that we could throw at the solver, but in principle this kind of algorithm may fail to converge with nonintegral data, so consider yourselves warned.</dd>
<dd>
A private type SIndex is defined which is intended to hold arc and node indices "with a sign", used to represent orientation. This has to be "in sync" with Index, in the sense that for every unsigned index value in Index, the two signed values should be feasible in SIndex. In other words, either Index is not using at least half of its feasible values, or SIndex has to be a "bigger" data type than Index. The default value for SIndex is int.</dd></dl>
<dl class="section author"><dt>Author</dt><dd><b>(original FORTRAN code)</b> <br />
Dimitri P. Bertsekas <br />
Lab. for Information and Decision Systems <br />
Massachusetts Institute of Technology <br />
</dd>
<dd>
<b>(original FORTRAN code)</b> <br />
Paul Tseng <br />
Department of Mathematics <br />
University of Washington \m</dd>
<dd>
<b>(C++ porting and polishing)</b> <br />
Antonio Frangioni <br />
Dipartimento di Informatica <br />
Universita' di Pisa <br />
</dd>
<dd>
<b>(C++ porting and polishing)</b> <br />
Claudio Gentile <br />
Istituto di Analisi di Sistemi e Informatica <br />
Consiglio Nazionale delle Ricerche <br />
</dd></dl>
<dl class="section copyright"><dt>Copyright</dt><dd>© by Antonio Frangioni </dd></dl>
</div></div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="navelem"><a class="el" href="dir_05331364be8e8aaaa1e20f74dcaccc8b.html">RelaxIV</a></li><li class="navelem"><a class="el" href="RelaxIV_8h.html">RelaxIV.h</a></li>
<li class="footer">Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.9.7 </li>
</ul>
</div>
</body>
</html>