LEMON: Ticket #605: Overflow in Optimal Cost
https://lemon.cs.elte.hu/trac/lemon/ticket/605
<p>
Motivation
==========
</p>
<p>
Please consider the following simple class of problems (which I will refer to
as the primal MRF problem <a class="changeset" href="https://lemon.cs.elte.hu/trac/lemon/changeset/1/lemon" title="Autotools based build system.">[1]</a>):
</p>
<blockquote>
<p>
max_{x,r} c' r
</p>
</blockquote>
<blockquote>
<p>
wrt
</p>
<blockquote>
<p>
r = |Ax - b|
</p>
</blockquote>
</blockquote>
<p>
where A is a network/graph matrix (the rows define the oriented edges, the
matrix is Totally Unimodular), and c >= 0, b are integral vectors. The dual of
this problem is an instance of an MCF problem defined on a graph represented
by the network matrix A with b as the costs of the edges and c as the
capacities. Strong duality holds here.
</p>
<p>
In our work, we are interested in examining and evaluating different approaches
to solving either the MRF or MCF problem using either primal, dual or
primal-dual methods. The context we have in mind is application to image
processing tasks, in particular we are interested in the phase unwrapping
problem in InSAR.
</p>
<p>
Properties of MCF Instances
===========================
</p>
<ol><li>The MCF dual problem of the MRF problem is defined on the same graph as
</li></ol><p>
defined by A, with the addition of an opposite arc with negative cost for every
oriented arc in A.
</p>
<ol start="2"><li>The MCF dual problem has no node imbalances by definition. The network flow
</li></ol><p>
condition must still be enforced.
</p>
<ol start="3"><li>By corollary of 1 & 2, the optimal values for the MCF dual problem must be
</li></ol><p>
negative.
</p>
<p>
Current Issue with Lemon:
=========================
</p>
<p>
Please consider the attached code that was tested with Lemon version 1.3.1. It
should be self contained and compilable with the make command if the LEMON_HOME
directory is correctly set in the Makefile.
</p>
<p>
Once compiled it can be run as follows (assuming a linux environment with a
BASH shell) to reproduce the issue.
</p>
<blockquote>
<p>
for scale in $(seq .1 .1 .4); do ./lemon_mcf_solver netgen_8_08a.txt $scale; done > output.txt
</p>
</blockquote>
<p>
In output.txt we should see that as we scale the costs b by a factor of .1 - .4
smoothly we get a negative optimal value initially, but when we reach .4 we
obtain a positive optimal value:
</p>
<blockquote>
<p>
grep "simplex cost:\|scaling costs" output.txt
</p>
</blockquote>
<blockquote>
<p>
INFO: scaling costs by 0.100000
INFO: network simplex cost: -575280232
INFO: scaling costs by 0.200000
INFO: network simplex cost: -1154018674
INFO: scaling costs by 0.300000
INFO: network simplex cost: -1732004546
INFO: scaling costs by 0.400000
INFO: network simplex cost: 1984124216
</p>
</blockquote>
<p>
Given property 3 of these MCF instances we know that positive cost solution is
impossible to these MCF instances. In fact, we've verified that the solution is
correct up to scale .3 (by comparing with other solvers) and around the
scale of .4 is when we hit this issue.
</p>
<p>
We came across this issue by modifying some NETGEN instances to have the
properties of the MCF dual problem we expect.
</p>
<p>
Please let us know if this is an issue with how we are using the Lemon library,
or perhaps if this is a bug in the Lemon library that can be addressed.
</p>
<p>
Thank you in advance,
Matt
</p>
<p>
<a class="changeset" href="https://lemon.cs.elte.hu/trac/lemon/changeset/1/lemon" title="Autotools based build system.">[1]</a> Kolmogorov, Vladimir. "Primal-dual algorithm for convex Markov random
fields." Microsoft Research MSR-TR-2005-117 (2005).
</p>
en-usLEMONhttps://lemon.cs.elte.hu/trac/lemon/chrome/site/lemon-logo.gif
https://lemon.cs.elte.hu/trac/lemon/ticket/605
Trac 1.2.3mgaraFri, 26 Aug 2016 21:35:07 GMTattachment set
https://lemon.cs.elte.hu/trac/lemon/ticket/605
https://lemon.cs.elte.hu/trac/lemon/ticket/605
<ul>
<li><strong>attachment</strong>
set to <em>lemon_issue.tar.gz</em>
</li>
</ul>
<p>
Reproducible Code Example
</p>
TicketAlpar JuttnerMon, 29 Aug 2016 06:48:33 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/605#comment:1
https://lemon.cs.elte.hu/trac/lemon/ticket/605#comment:1
<p>
Having just a short look at the code, I believe it is not a bug, but indeed just a simple integer overflow.
</p>
<p>
You use <code>long long int</code> weights and costs, but use the default settings of solvers which are <code>int</code>s.
Try to use
<code>CapacityScaling<lemon::ListDigraph, long long int></code>,
<code>lemon::CostScaling<lemon::ListDigraph, long long int></code> and
<code>lemon::NetworkSimplex<lemon::ListDigraph, long long int></code>
</p>
<p>
Note that
</p>
<ol><li>The above MCF implementations even allow using different data types for the capacity and for the cost calculation (see the doc).
</li><li>Using <code>long long int</code> type for the capacity and (even more importantly) for the costs makes sense even if the input consists of 32bit integers only. During the calculations capacity values are added together, and the cost values are multiplied with capacity values and added together, which can easily cause integer overflow.
</li></ol>
TicketPeter KovacsMon, 29 Aug 2016 09:22:12 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/605#comment:2
https://lemon.cs.elte.hu/trac/lemon/ticket/605#comment:2
<p>
I agree. You should use <code>long long int</code> type as described above.
</p>
<p>
Furthermore, note that the total flow cost may not fit in the data type used for internal calculations of the algorithm. That's why the <code>totalCost()</code> method has its own template argument. You can use it like this:
</p>
<pre class="wiki">long long int totalCost1 = ns.totalCost();
double totalCost2 = ns.totalCost<double>();
</pre><p>
See the documentation here:
<a href="http://lemon.cs.elte.hu/pub/doc/1.3.1/a00276.html#a4e1efd04a6b234645d1ca18d2635d57e">http://lemon.cs.elte.hu/pub/doc/1.3.1/a00276.html#a4e1efd04a6b234645d1ca18d2635d57e</a>
</p>
TicketAlpar JuttnerMon, 12 Sep 2016 12:47:09 GMTstatus changed; resolution set
https://lemon.cs.elte.hu/trac/lemon/ticket/605#comment:3
https://lemon.cs.elte.hu/trac/lemon/ticket/605#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>invalid</em>
</li>
</ul>
TicketmgaraMon, 12 Sep 2016 19:57:14 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/605#comment:4
https://lemon.cs.elte.hu/trac/lemon/ticket/605#comment:4
<p>
Thank you for the information; we've tested that this actually fixes things and so we are continuing our benchmarking and testing. Thanks again and sorry for the mix-up.
</p>
Ticket