[Coin-discuss] Solving ILP within B&B framework

Tue Jul 18 07:49:18 EDT 2006

Hi everyone,

has anyone encountered the following problem when using branchAndBound to solve an ILP: it always starts solving the ILP giving output

Clp0006I 0 Obj -183 Primal inf 1535 (1535)
Clp0006I 200 Obj -167 Primal inf 578 (578)

but then it terminates saying

This application has requested the Runtime to terminate it in an unusual way. Please contact the application's support team for more information.

this problem occurs after looping for about 250 000 or 300 000 times in which the ILP is solved around 15 000 times. The following two functions (next to others) are called in the loop:

int ILPformulation::setupModel(bool inLoop)

{

// Setup the model. Specify how Branch and Bound should work.

solver1=getModelForILP();

solver1.initialSolve();

if(inLoop==true)

{

delete model;

}

model = new CbcModel(solver1);

// Settings Branch and Bound

int iRow, iColumn;

int numberColumns = solver1.getNumCols();

int numberRows = solver1.getNumRows();

Branch = new CbcBranchUserDecision;

model->setBranchingMethod(Branch);

// Node comparison - Select the node with the best objective

Comparison = new CbcCompareDefault; //Default,Objective,Depth

model->setNodeComparison(Comparison);

delete []Branch, Comparison;

return status;

}

int ILPformulation::BranchAndBound()

{

// Actual Branch and Bound

model->branchAndBound();

return 0;

}

I guess that it is some memory leak problem, but I have no clue where to search for it....
does anyone of you have an idea?
Kirsten...

________________________________

From: coin-discuss-bounces at list.coin-or.org on behalf of Wiebe Kirsten (Stud. FdEWB)
Sent: Fri 7/14/2006 23:31
To: Discussions about open source software for Operations Research
Subject: RE: [Coin-discuss] Solving ILP within B&B framework

Thanks John,
it seems to work without the cut generators :-)
Greetz
Kirsten

________________________________

From: coin-discuss-bounces at list.coin-or.org on behalf of John J Forrest
Sent: Fri 7/14/2006 18:52
To: Discussions about open source software for Operations Research
Subject: Re: [Coin-discuss] Solving ILP within B&B framework

Kirsten, 

It is fairly obvious that you would get the first "access violation reading location".  Without knowing more about your driver I can't say much about the second one. 

Fixing many variables could easily allow CglProbing to find that the problem is infeasible and then this can happen.  I have modified code in branches/devel to trap this before error message. 

Try with no cut generators at all. 

John Forrest 

"Wiebe Kirsten (Stud. FdEWB)" <K.Wiebe at Student.Unimaas.NL> 
Sent by: coin-discuss-bounces at list.coin-or.org 

07/14/2006 08:04 AM 
Please respond to
Discussions about open source software for Operations Research        <coin-discuss at list.coin-or.org>

To
"Discussions about open source software for Operations Research" <coin-discuss at list.coin-or.org> 
cc
Subject
[Coin-discuss] Solving ILP within B&B framework	

Hello everyone,
I'm currently writing my master thesis in operations research about rankings in tournaments using the linear ordering polytope. My idea is to find all Slater solutions for that tournament with the help of a branch and bound, where, in each node of the b&b tree, the ILP of the linear ordering polytope is solved to optimality. For that I start with solving the ILP once to optimality and then "going up" in the tree fixing all variables above the currently processed node to what they were before (in the current solution of the ILP) and the variable that is branched on in that node to its complement, i.e. to (1 - (what is was before)). I implemented a function that detects 3-cycles, i.e. infeasibility if the transitivity is not satisfied; but it seems that there is still something going wrong. For a little instance where there are 4 participants for the tournament and hence 6 variables representing the binary relations the algorithm, that until now is simply supposed to go up in the b&b tree once, is working ok. In a larger instance, with 40 participants and hence 780 binary relations, I get that error message about "Access violation reaing location ..." after 33 iterations and my output says:

Clp6002E 192 bad bound pairs or bad objectives were found - first at R9884
Clp0004I Stopped due to errors - objective value 0
Cgl0000I Cut generators found to be infeasible!

The error message occurs where "model" is defined (model is the object with which I can define the branching method and node comparison and add cuts:

solver1=getModelForILP();
// Use Preprocessing of Coin
solver1.initialSolve();
solver2=&solver1;
solver2=PreProcess.preProcess(solver1,true,5);
model = new CbcModel(*solver2); <-- HERE IS THE ERROR

Does that mean that I cannot use the CoinOR cuts here, or is already something wrong with using the preprocessing?

I think it is about the preprocessing, because when I include

if(solver2 == NULL)
{
   cout << "Preprocessing did not work, node skipped\n";
   return 1;
}

before "model = new CbCModel(*solver2);" and hence return to main to continue without processing the node, the algorithm continues until iteration 95, but then there is again the error message about "access violation reading location..." when the program tries to access the column solution of column 423 (the variable that is branched on there). When debugging and looking until which column there are solutions I get that there are only solutions until column 218. In the beginning I had that problem already at iteration 33 and iteration 91, but that is not the case anymore and I just don't get why...

Greetz
Kirsten
_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss

-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/ms-tnef
Size: 12040 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20060718/28d3c9c9/attachment.bin>