[BCP] Variant of the BAC example
Erez Buchnik
erez.buchnik at gmail.com
Wed Apr 6 05:08:55 EDT 2011
Hello,
First of all, I am new to this subject, so I hope I'm sending this to the
right place - I'd appreciate it if you could redirect me if I'm not...
I've been experimenting with the BAC example for some time, trying to apply
the following ILP problem that is similar to the original one (formulated
for 15 binary variables X0,...X14):
Minimize:
obj = X0 + X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 + X10 + X11 + X12 +
X13 + X14
such that:
X0 + X2 >= 1
X0 + X4 >= 1
X0 + X6 >= 1
X5 + X8 >= 1
X9 + X4 >= 1
X9 + X6 >= 1
X9 + X6 + X12 + X14 >= 1
X1 == 1
X3 == 1
X5 == 1
X7 == 1
X3 + X10 >= 1
X5 == 1
X5 + X11 + X13 >= 1
A brute-force algorithm reveals that out of all the possible 32768 values
there are 768 that satisfy all the constraints, and only one that reaches
the minimum objective function value, which is 6.
This solution is as follows:
[ X0=1 ], [ X1=1 ], X2=0, [ X3=1 ], X4=0, [ X5=1 ], X6=0, [ X7=1 ], X8=0, [
X9=1 ], X10=0, X11=0, X12=0, X13=0, X14=0
I've applied programatically the problem coefficients to the desc structure
and tried to run it, but the algorithm finds no feasible solution. Attached
are two files, one with the dump of the successful run of the original BAC
example on the same code that I use (for reference), and one with the dump
for my problem. I've also added in the code dumps of the core and indexed
matrices.
NOTE: Since the constraints are generated automatically in my code, they may
be duplicated - removing the duplicates did not solve my problem, so I
assume this is not an issue.
Please help...
Thanks a lot,
Erez
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/bcp/attachments/20110406/b774949e/attachment.html
-------------- next part --------------
Compilation flags:
Problem created in memory
CORE:
Dumping matrix...
colordered: 0
major: 10 minor: 10
vec 0 has length 2 with entries:
0 1.0000000000000000000000000
1 1.0000000000000000000000000
vec 1 has length 2 with entries:
1 1.0000000000000000000000000
2 1.0000000000000000000000000
vec 2 has length 2 with entries:
2 1.0000000000000000000000000
3 1.0000000000000000000000000
vec 3 has length 2 with entries:
3 1.0000000000000000000000000
4 1.0000000000000000000000000
vec 4 has length 2 with entries:
4 1.0000000000000000000000000
5 1.0000000000000000000000000
vec 5 has length 2 with entries:
5 1.0000000000000000000000000
6 1.0000000000000000000000000
vec 6 has length 2 with entries:
6 1.0000000000000000000000000
7 1.0000000000000000000000000
vec 7 has length 2 with entries:
7 1.0000000000000000000000000
8 1.0000000000000000000000000
vec 8 has length 2 with entries:
8 1.0000000000000000000000000
9 1.0000000000000000000000000
vec 9 has length 2 with entries:
9 1.0000000000000000000000000
0 1.0000000000000000000000000
Finished dumping matrix
INDEXED:
Dumping matrix...
colordered: 0
major: 6 minor: 10
vec 0 has length 3 with entries:
9 1.0000000000000000000000000
1 1.0000000000000000000000000
3 1.0000000000000000000000000
vec 1 has length 3 with entries:
0 1.0000000000000000000000000
2 1.0000000000000000000000000
4 1.0000000000000000000000000
vec 2 has length 3 with entries:
0 1.0000000000000000000000000
3 1.0000000000000000000000000
7 1.0000000000000000000000000
vec 3 has length 3 with entries:
1 1.0000000000000000000000000
4 1.0000000000000000000000000
5 1.0000000000000000000000000
vec 4 has length 3 with entries:
5 1.0000000000000000000000000
6 1.0000000000000000000000000
7 1.0000000000000000000000000
vec 5 has length 3 with entries:
0 1.0000000000000000000000000
6 1.0000000000000000000000000
8 1.0000000000000000000000000
Finished dumping matrix
##########################################################
TM: Starting phase 0
##########################################################
TM: Default init_new_phase() executed.
LP: **** Processing NODE 0 on LEVEL 0 (from TM) ****
LP: Default purge_slack_pool() executed.
LP: *** Starting iteration 1 ***
LP node written in file lpnode.lp
LP: Matrix size: 10 vars x 10 cuts
LP: Solution value: -5.0000 / 2 , 10
LP: Default display_lp_solution() executed.
LP : Displaying LP solution (RelaxedSolution) :
LP : Displaying solution :
Core var (internal index: 1 ) at 1.0000
Core var (internal index: 3 ) at 1.0000
Core var (internal index: 5 ) at 1.0000
Core var (internal index: 7 ) at 1.0000
Core var (internal index: 9 ) at 1.0000
LP: Row effectiveness: rownum: 10 ineffective: 0
LP: Number of leftover cuts: 0
generate_cuts_in_lp(): found 4 indexed cuts
generate_cuts_in_lp(): found 5 algorithmic cuts
LP: Number of cuts generated in the LP process: 9
LP: Non-violated (hence removed): 0
LP: Number of cuts received from CG: 0
LP: Total number of cuts in local pool: 9
LP: Number of leftover vars: 0
LP: Default generate_vars_in_lp() executed.
LP: Number of vars received from VG: 0
LP: Total number of vars in local pool: 0
LP: In iteration 1 BCP generated 9 cuts , 0 vars before calling branch()
LP: Default select_branching_candidates() executed.
LP: In iteration 1 BCP added 9 cuts, 0 vars.
LP: Default purge_slack_pool() executed.
LP: *** Starting iteration 2 ***
LP node written in file lpnode.lp
LP: Matrix size: 10 vars x 19 cuts
LP: Solution value: -5.0000 / 2 , 3
LP: Default display_lp_solution() executed.
LP : Displaying LP solution (RelaxedSolution) :
LP : Displaying solution :
Core var (internal index: 0 ) at 1.0000
Core var (internal index: 2 ) at 1.0000
Core var (internal index: 4 ) at 1.0000
Core var (internal index: 6 ) at 1.0000
Core var (internal index: 8 ) at 1.0000
LP: Row effectiveness: rownum: 19 ineffective: 9
LP: Number of leftover cuts: 0
generate_cuts_in_lp(): found 2 indexed cuts
generate_cuts_in_lp(): found 5 algorithmic cuts
LP: Number of cuts generated in the LP process: 7
LP: Non-violated (hence removed): 0
LP: Number of cuts received from CG: 0
LP: Total number of cuts in local pool: 7
LP: Number of leftover vars: 0
LP: Default generate_vars_in_lp() executed.
LP: Number of vars received from VG: 0
LP: Total number of vars in local pool: 0
LP: In iteration 2 BCP generated 7 cuts , 0 vars before calling branch()
LP: Default select_branching_candidates() executed.
LP: In iteration 2 BCP added 7 cuts, 0 vars.
LP: Default purge_slack_pool() executed.
LP: *** Starting iteration 3 ***
LP node written in file lpnode.lp
LP: Matrix size: 10 vars x 26 cuts
LP: Solution value: -2.6667 / 2 , 8
LP: Default display_lp_solution() executed.
LP : Displaying LP solution (RelaxedSolution) :
LP : Displaying solution :
Core var (internal index: 0 ) at 0.3333
Core var (internal index: 1 ) at 0.6667
Core var (internal index: 3 ) at 0.3333
Core var (internal index: 5 ) at 0.3333
Core var (internal index: 7 ) at 0.3333
Core var (internal index: 8 ) at 0.6667
LP: Default test_feasibility() executed.
LP: Default test_full() executed.
LP: Row effectiveness: rownum: 26 ineffective: 9
LP: Number of leftover cuts: 0
generate_cuts_in_lp(): found 0 indexed cuts
generate_cuts_in_lp(): found 0 algorithmic cuts
LP: Number of cuts received from CG: 0
LP: Total number of cuts in local pool: 0
LP: Number of leftover vars: 0
LP: Default generate_vars_in_lp() executed.
LP: Number of vars received from VG: 0
LP: Total number of vars in local pool: 0
LP: In iteration 3 BCP generated 0 cuts , 0 vars before calling branch()
LP: Default display_lp_solution() executed.
LP : Displaying LP solution (FinalRelaxedSolution) :
LP : Displaying solution :
Core var (internal index: 0 ) at 0.3333
Core var (internal index: 1 ) at 0.6667
Core var (internal index: 3 ) at 0.3333
Core var (internal index: 5 ) at 0.3333
Core var (internal index: 7 ) at 0.3333
Core var (internal index: 8 ) at 0.6667
LP: Default select_branching_candidates() executed.
LP: In iteration 3 BCP added 0 cuts, 0 vars.
LP: Default purge_slack_pool() executed.
LP: *** Starting iteration 4 ***
LP node written in file lpnode.lp
LP: Matrix size: 10 vars x 26 cuts
LP: Solution value: -2.5000 / 2 , 1
LP: Default display_lp_solution() executed.
LP : Displaying LP solution (RelaxedSolution) :
LP : Displaying solution :
Core var (internal index: 0 ) at 0.5000
Core var (internal index: 1 ) at 0.5000
Core var (internal index: 5 ) at 0.5000
Core var (internal index: 7 ) at 0.5000
Core var (internal index: 8 ) at 0.5000
LP: Default test_feasibility() executed.
LP: Default test_full() executed.
LP: Row effectiveness: rownum: 26 ineffective: 10
LP: Number of leftover cuts: 0
generate_cuts_in_lp(): found 0 indexed cuts
generate_cuts_in_lp(): found 0 algorithmic cuts
LP: Number of cuts received from CG: 0
LP: Total number of cuts in local pool: 0
LP: Number of leftover vars: 0
LP: Default generate_vars_in_lp() executed.
LP: Number of vars received from VG: 0
LP: Total number of vars in local pool: 0
LP: In iteration 4 BCP generated 0 cuts , 0 vars before calling branch()
LP: Default display_lp_solution() executed.
LP : Displaying LP solution (FinalRelaxedSolution) :
LP : Displaying solution :
Core var (internal index: 0 ) at 0.5000
Core var (internal index: 1 ) at 0.5000
Core var (internal index: 5 ) at 0.5000
Core var (internal index: 7 ) at 0.5000
Core var (internal index: 8 ) at 0.5000
LP: Default select_branching_candidates() executed.
LP: Starting strong branching:
LP node written in file lpnode.lp
LP node written in file lpnode.lp
LP: Presolving: (0,0.5000,-1.0000 / ) [-2.0000,2,2] [-2.0000,2,1]
LP: Default compare_presolved_branching_objects() executed.
LP: Deleting 10 rows from the matrix.
LP: Default set_actions_for_children() executed.
LP: SB selected candidate 0 out of 1.
LP: The selected object is: (0,0.5000,-1.0000 / ) [-2.0000,2,2] [-2.0000,2,1]
LP node written in file lpnode.lp
LP: **** Processing NODE 1 on LEVEL 1 (dived) ****
LP: Default purge_slack_pool() executed.
LP: *** Starting iteration 1 ***
LP node written in file lpnode.lp
LP: Matrix size: 10 vars x 16 cuts
LP: Solution value: -2.0000 / 2 , 2
LP: Default display_lp_solution() executed.
LP : Displaying LP solution (RelaxedSolution) :
LP : Displaying solution :
Core var (internal index: 0 ) at 1.0000
Core var (internal index: 5 ) at 1.0000
LP: Default test_feasibility() executed.
LP: Default test_full() executed.
LP: Default pack_feasible_solution() executed.
TM: Default unpack_feasible_solution() executed.
TM: Solution found at 0.718 sec.
TM 0.641: Sol from proc: 1 val: -2.000000 (prev best: infinity) tree size/procd: 3/1 cand list ins/size: 2/2
LP: Terminating and fathoming due to proven high cost.
TM: Pruning NODE 2 LEVEL 1 instead of sending it.
TM: final statistics:
TM: Running time: 0.641
TM: search tree size: 3 ( processed 2 ) max depth: 1
LP statistics:
time in cut generation : 0.031 sec
time in var generation : 0.030 sec
time in heuristics : 0.000 sec
time in solving LPs : 0.016 sec
time in strong branching: 0.062 sec
TM: The best solution found has value -2.000000
Customized display of the feasible solution:
1.00 0.00 0.00 0.00 0.00 1.00 0.00 0.00 0.00 0.00
Default BCP display of the feasible solution:
TM: Default BCP_tm_user::display_feasible_solution() executed.
Core var (internal index: 0 ) at 1.0000
Core var (internal index: 5 ) at 1.0000
Press any key to continue . . .
-------------- next part --------------
Compilation flags:
Problem created in memory
CORE:
Dumping matrix...
colordered: 0
major: 12 minor: 15
vec 0 has length 2 with entries:
0 1.0000000000000000000000000
2 1.0000000000000000000000000
vec 1 has length 2 with entries:
0 1.0000000000000000000000000
4 1.0000000000000000000000000
vec 2 has length 2 with entries:
0 1.0000000000000000000000000
6 1.0000000000000000000000000
vec 3 has length 2 with entries:
5 1.0000000000000000000000000
8 1.0000000000000000000000000
vec 4 has length 2 with entries:
9 1.0000000000000000000000000
4 1.0000000000000000000000000
vec 5 has length 2 with entries:
9 1.0000000000000000000000000
6 1.0000000000000000000000000
vec 6 has length 4 with entries:
9 1.0000000000000000000000000
6 1.0000000000000000000000000
12 1.0000000000000000000000000
14 1.0000000000000000000000000
vec 7 has length 1 with entries:
1 1.0000000000000000000000000
vec 8 has length 1 with entries:
3 1.0000000000000000000000000
vec 9 has length 1 with entries:
5 1.0000000000000000000000000
vec 10 has length 1 with entries:
7 1.0000000000000000000000000
vec 11 has length 2 with entries:
3 1.0000000000000000000000000
10 1.0000000000000000000000000
Finished dumping matrix
INDEXED:
Dumping matrix...
colordered: 0
major: 2 minor: 14
vec 0 has length 1 with entries:
5 1.0000000000000000000000000
vec 1 has length 3 with entries:
5 1.0000000000000000000000000
11 1.0000000000000000000000000
13 1.0000000000000000000000000
Finished dumping matrix
##########################################################
TM: Starting phase 0
##########################################################
TM: Default init_new_phase() executed.
LP: **** Processing NODE 0 on LEVEL 0 (from TM) ****
LP: Default purge_slack_pool() executed.
LP: *** Starting iteration 1 ***
LP node written in file lpnode.lp
LP: Matrix size: 15 vars x 12 cuts
LP: Solution value: 6.0000 / 2 , 8
LP: Default display_lp_solution() executed.
LP : Displaying LP solution (RelaxedSolution) :
LP : Displaying solution :
Core var (internal index: 0 ) at 1.0000
Core var (internal index: 1 ) at 1.0000
Core var (internal index: 3 ) at 1.0000
Core var (internal index: 5 ) at 1.0000
Core var (internal index: 7 ) at 1.0000
Core var (internal index: 9 ) at 1.0000
LP: Row effectiveness: rownum: 12 ineffective: 0
LP: Number of leftover cuts: 0
generate_cuts_in_lp(): found 0 indexed cuts
generate_cuts_in_lp(): found 6 algorithmic cuts
LP: Number of cuts generated in the LP process: 6
LP: Non-violated (hence removed): 0
LP: Number of cuts received from CG: 0
LP: Total number of cuts in local pool: 6
LP: Number of leftover vars: 0
LP: Default generate_vars_in_lp() executed.
LP: Number of vars received from VG: 0
LP: Total number of vars in local pool: 0
LP: In iteration 1 BCP generated 6 cuts , 0 vars before calling branch()
LP: Default select_branching_candidates() executed.
LP: In iteration 1 BCP added 6 cuts, 0 vars.
LP: Default purge_slack_pool() executed.
LP: *** Starting iteration 2 ***
LP node written in file lpnode.lp
LP: Matrix size: 15 vars x 18 cuts
LP: Solution value: 6.0000 / 36 , 1
LP: Default display_lp_solution() executed.
LP : Displaying LP solution (RelaxedSolution) :
LP : Displaying solution :
Core var (internal index: 0 ) at 2.0000
Core var (internal index: 1 ) at 1.0000
Core var (internal index: 3 ) at 1.0000
Core var (internal index: 4 ) at -1.0000
Core var (internal index: 5 ) at 1.0000
Core var (internal index: 6 ) at -1.0000
Core var (internal index: 7 ) at 1.0000
Core var (internal index: 9 ) at 2.0000
LP: Primal feasibility lost.
LP: Pruning node
TM: final statistics:
TM: Running time: 0.453
TM: search tree size: 1 ( processed 1 ) max depth: 0
LP statistics:
time in cut generation : 0.016 sec
time in var generation : 0.000 sec
time in heuristics : 0.000 sec
time in solving LPs : 0.032 sec
time in strong branching: 0.000 sec
TM: No feasible solution is found
Press any key to continue . . .
More information about the BCP
mailing list