[Cbc] branchAndBound() malfunction

[John Forrest]

Alessio,

I would not use OsiCbc.

To avoid Cbc getting confused, it is probably best to create a clean 
CbcModel from the master CoinModel each time - that way bounds won't be 
preset.

John Forrest
On 10/06/15 19:49, Alessio Melosi wrote:
> Hello, I have some problem with my c++ code for the resolution of the 
> capacitated facility location problem (CFL) with the Benders method. 
> It is an iterative method that at each step has to solve a continuous 
> subproblem, generate a new constraint for the master problem (which 
> has one continuous variable and m-1 binary variables), solve the 
> master problem and use the master solution to update the 
> righthandsides of the subproblem for the next iteration. Here is the 
> pseudo-code of my algorithm:
>
> *****************************************************************
> BEGIN
> read the input;
> create a model for the master problem using CoinModel;
> add variables and rows to the master CoinModel according to the input;
> create a model for the subproblem using CoinModel;
> add variables and rows to the subproblem CoinModel according to the input;
> create the solver for the master problem using OsiCbcSolverInterface;
> create the solver for the subproblem using OsiClpSolverInterface;
> FOR( iter = 0 ; iter < maxiter ; iter++)
>   load the subproblem CoinModel into the OsiClpSolverInterface;
>   solve the subproblem with initialSolve() and update the LB;
>   IF( UB - LB < eps ) break;
>   get the new constraint and add it to the master CoinModel;
>   load the master CoinModel into the OsiCbcSolverInterface;
>   solve the master problem with branchAndBound() and update the UB;
>   update the righthandsides of the subproblem CoinModel;
> ENDFOR
> END
> ******************************************************************
>
> Initially the master problem has no rows. At the first iteration the 
> first row is added to the master problem and so on. The problem is the 
> following: at the first iteration branchAndBound() solves the master, 
> but at the second iteration it doesn't, in the sense that at the 
> second iteration the binary variables are blocked to the values of the 
> previous iteration, and the solver works only with the (only one) 
> continuous variable. Because of it the program makes only two 
> iterations. Before running branchAndBound in the second iteration, a 
> simple instance of the CFL gives the following master problem in lp 
> format:
>
> \Problem name:
>
> Minimize
> obj: 1500 x0 + 1500 x1 + x2
> Subject To
> cons0:  1000000 x0 + 1000000 x1 >= 500000
> cons1:  40000 x1 + x2 >= 25000
> Bounds
>  0 <= x0 <= 1
>  0 <= x1 <= 1
> Integers
> x0 x1
> End
>
>
> clearly the opt. solution is x0=0, x1=1, x2=0, but branchAndBound() 
> x0=1, x1=0, x2=25000. At the first iteration the constraint cons1 
> wasn't there, and branchAndBound() in that case gave the right 
> opt.solution x0=1, x1=0, x2=0. As I said before It seems that the 
> binary variables are blocked at the values of the first iteration, 
> even if the lp file says 0 <= x0 <= 1 & 0 <= x1 <= 1.
> Gdb says that during the call to branchAndBound() in the second 
> iteration, the program receives signal of
> SIGTRAP, Trace/breakpoint trap
> 0x08089194 in CbcModel::setPointers(OsiSolverInterface const*) ()
>
>
> and Valgrind in that point gives an invalid read:
>
>
> ==3989== Invalid read of size 4
> ==3989==    at 0x8089194: CbcModel::setPointers(OsiSolverInterface const*)
> (in /home/alessio/Documenti/CWL/cwl8/cwl8)
> ==3989==    by 0x80AE664: CbcModel::branchAndBound(int) (in
> /home/alessio/Documenti/CWL/cwl8/cwl8)
> ==3989==    by 0x80800EF: OsiCbcSolverInterface::branchAndBound() (in
> /home/alessio/Documenti/CWL/cwl8/cwl8)
> ==3989==    by 0x8051AB4: main (cwl8.cpp:657)
> ==3989==  Address 0x4a17570 is 40 bytes inside a block of size 52 free'd
> ==3989==    at 0x402D7B8: operator delete(void*) (in
> /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
> ==3989==    by 0x82C2986: OsiSolverInterface::~OsiSolverInterface() (in
> /home/alessio/Documenti/CWL/cwl8/cwl8)
> ==3989==    by 0x80712FD: OsiClpSolverInterface::~OsiClpSolverInterface()
> (in /home/alessio/Documenti/CWL/cwl8/cwl8)
> ==3989==    by 0x80AE64B: CbcModel::branchAndBound(int) (in
> /home/alessio/Documenti/CWL/cwl8/cwl8)
> ==3989==    by 0x80800EF: OsiCbcSolverInterface::branchAndBound() (in
> /home/alessio/Documenti/CWL/cwl8/cwl8)
> ==3989==    by 0x8051AB4: main (cwl8.cpp:657)
>
>
> what can i do? Thanks in advance for your help,
>
> Alessio  
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20150611/04fbc82b/attachment.html>