Custom Query (508 matches)
Results (10  12 of 508)
Ticket  Resolution  Summary  Owner  Reporter 

#606  fixed  StaticDigraph copy constructor  
Description 
While using 

#605  invalid  Overflow in Optimal Cost  
Description 
Motivation ========== Please consider the following simple class of problems (which I will refer to as the primal MRF problem [1]):
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. 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 primaldual 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. Properties of MCF Instances ===========================
defined by A, with the addition of an opposite arc with negative cost for every oriented arc in A.
condition must still be enforced.
negative. Current Issue with Lemon: ========================= 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. Once compiled it can be run as follows (assuming a linux environment with a BASH shell) to reproduce the issue.
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:
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. We came across this issue by modifying some NETGEN instances to have the properties of the MCF dual problem we expect. 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. Thank you in advance, Matt [1] Kolmogorov, Vladimir. "Primaldual algorithm for convex Markov random fields." Microsoft Research MSRTR2005117 (2005). 

#604  done  Faster MaxMatching implementation  
Description 
From Joran van Apeldoorn:
