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

[John J Forrest]

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 --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20060714/a429594c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/octet-stream
Size: 6001 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20060714/a429594c/attachment.obj>