Possible bug when calling SolveMCF()

[lucasparada20]

Hello Antonio,

I am trying to implement your code however I arrive at the following bug when calling:

mcf = new MCFSOLVER();
mcf->LoadNet( 1000000 , 1000000 , tn, tm, tU , tC , tDfct , tStartn , tEndn );		
mcf->SolveMCF();

The bug is triggered upon calling the solve method. Here is some gdb output:

scenario:0 tn:66525 tm:103570
Program received signal SIGSEGV, Segmentation fault.
0x000055555562cd64 in MCFClass_di_unipi_it::MCFSimplex::PrimalSimplex (this=0x55555f2ed180) at ../MCFSimplex/MCFSimplex.C:2595
2595 if( arc->tail == k2 ) {
(gdb) bt
#0 0x000055555562cd64 in MCFClass_di_unipi_it::MCFSimplex::PrimalSimplex (this=0x55555f2ed180) at ../MCFSimplex/MCFSimplex.C:2595
#1 0x0000555555627fdb in MCFClass_di_unipi_it::MCFSimplex::SolveMCF (this=0x55555f2ed180) at ../MCFSimplex/MCFSimplex.C:587
#2 0x000055555561451c in MinCostFlow::SolveScenario (this=0x7fffffffdf10, e=0) at MinCostFlow.cpp:31 // mcf->SolveMCF();
#3 0x0000555555614408 in MinCostFlow::Solve (this=0x7fffffffdf10, _prob=0x7fffffffdf60) at MinCostFlow.cpp:20
#4 0x00005555556323a2 in main (arg=3, argv=0x7fffffffe298) at main_ex_sbrpod.cpp:50
(gdb)

I have tried different 'MCFSOLVER()' however there always is the error albeit at different lines inside the solve() call.

Do you have any idea as to what could it be? Is there a method to print the net to check if the arrays are being loaded correctly i.e. a net.Show() maybe?

Many thanks for your time,

Lucas Parada

[frangio68]

Hi.

Thanks for reaching to me.

I would guess there is something wrong in the data you pass to LoadNet(), since it's weird you get a problem in every solver. The easy way to check is to use WriteMCF() to have the instance written back as soon as LoadNet() finishes.

I may also suggest to compile with

-fsanitize=undefined -fsanitize=address

which might catch memory errors.

Finally, let me mention that you may find it more convenient to work with

https://gitlab.com/smspp/mcfblock

but that's another story.

Let me know if any of these helps.

[lucasparada20]

Hello Antonio,

Many thanks for the reply and the tip! Indeed with WriteMCF() I could print the net, however it was not the primary bug. Apparently the primary bug is when creating arcs with negative cost. Specifically, I am trying to solve a min cost flow problem where some arcs are a reward (i.e. have a negative cost), can the solvers handle such a case?

I ask because even though the documentation doesn't specify it ( "pC is the m-vector of the arc costs; costs must be finite (< C_INF); passing pC == 0 means that all costs must be 0." ), when using the Simplex solver it produces a bug and the RelaxIV solvers seems to be stuck in a never ending loop.

Many thanks for your time,

Lucas Parada

[frangio68]

Yes, in principle arcs with negative costs are supported. However, if you have a negative cost cycle with unbounded capacities this may make the problem unbounded below. This is also in principle supported, but I guess less tested.
Yet: are you managing the accuracies? If not you may want to give a look to kEpsFlw, kEpsDfct and kEpsCst. Unfortunately the code uses absolute accuracies, which means that if you have either vary large or very small (or, worse, both) arc costs the default ones may not work. You should set them to something like the maximum absolute value of the involved quantities (costs, capacities, ...) times a reasonable relative accuracy, say not smaller than 1e-12.

[lucasparada20]

Thanks Antonio, I adjusted the accuracies but it also wasn't that. I think I found it though.

In the LoadDMX() there is this:

if( ( tStartn[ i ] < 1 ) || ( tStartn[ i ] > tn ) )
{ printf("tStartn[ %d ]:%d\n",i,tStartn[ i ]); throw( MCFException( "LoadDMX: invalid start node" ) ); } // I added the printf when debugging.
if( ( tEndn[ i ] < 1 ) || ( tEndn[ i ] > tn ) )
throw( MCFException( "LoadDMX: invalid end node" ) );

Does it mean that no start, end node can never be "0"? I found that after printing the network to a file and then calling the LoadDMX() to see if it work. For example I was creating the network arrays by previously populating arrays of "node" and "arc" objects, and them simply passing them as follows:

for(int i=0;i<tn;i++)
	tDfct[i]=nodes[i].deficit;
for(int i=0;i<tm;i++)
{
	tU[i]=arcs[i].cap;
	tStartn[i]=arcs[i].from; 
	tEndn[i]=arcs[i].to;
	tC[i]=arcs[i].cost;
}

leading to this output for my data:

p min 14 6
n 1 -10000
n 2 10000
a 0 2 0 19 0
a 9 1 0 19 0
a 2 7 0 19 0
a 7 8 0 19 0
a 8 9 0 19 0
a 0 3 0 19 0

Then, you see, either the exception is raised or the Seg Fault produced depending on whether I load the network or just create the arrays.

[frangio68]

Hi.

Well, yes. Sorry, this is checked in LoadDMX() so that LoadNet() does not repeat the check, which it probably should. Whether the first node name is 0 or 1 is controlled by a macro setting in MCFClass.C; see below. I'm aware it's not a very C++-ish way of doing things but this code is 30 years old and things were different at the time.

Hope this clarifies.

Antonio

/-------------------------------- USENAME0 --------------------------------/
/** Decides if 0 or 1 is the "name" of the first node.

• If USENAME0 == 1, (warning: it has to be exactly 1), then the node
• names go from 0 to n - 1, otherwise from 1 to n. Note that this does not
• affect the position of the deficit in the deficit vectors, i.e., the
• deficit of the i-th node - be its "name" i' or i - 1' - is always in
• the i-th position of the vector. */

#define USENAME0 0