[Cbc] Segfault solving a problem containing SOSs
Luís Borges de Oliveira
lbo at siscog.pt
Tue Oct 18 13:36:43 EDT 2016
Hello,
While playing with a model whose majority of constraints have the form x
+ y <= 1 (~80% or more), I have tried to move those constraints to S1
SOSs. [1] On some instances, the gainings are quite spectacular; in one
in particular, the time to find the optimal solution went down by two
orders of magnitude!
Alas, I have found some issues leading to segfaults in certain instances.
command line - cbc.exe -import sos.lp -solve (default strategy 1)
Continuous objective value is 15 - 0.00 seconds
Cgl0003I 0 fixed, 67 tightened bounds, 0 strengthened rows, 0
substitutions
Cgl0004I processed model has 277 rows, 652 columns (652 integer (616
of which binary)) and 2812 elements
Cutoff increment increased from 1e-005 to 0.9999
Cbc0038I Initial state - 28 integers unsatisfied sum - 12.2793
Cbc0038I Pass 1: suminf. 0.57576 (4) obj. 114 iterations 116
Cbc0038I Pass 2: suminf. 0.15933 (4) obj. 114 iterations 60
Cbc0038I Solution found of 114
Cbc0038I Before mini branch and bound, 579 integers at bound fixed
and 36 continuous
Cbc0038I Full problem 277 rows 652 columns, reduced to 23 rows 20
columns
Program received signal SIGSEGV, Segmentation fault.
0x000000000051e064 in CbcSOS::infeasibility(OsiBranchingInformation
const*, int&) const ()
Backtrace:
#0 0x000000000051e064 in
CbcSOS::infeasibility(OsiBranchingInformation const*, int&) const ()
#1 0x0000000000764ab2 in
OsiObject::checkInfeasibility(OsiBranchingInformation const*) const ()
#2 0x000000000050e382 in CbcNode::chooseDynamicBranch(CbcModel*,
CbcNode*, OsiSolverBranch*&, int) ()
#3 0x00000000004e85ac in CbcModel::chooseBranch(CbcNode*&, int,
CbcNode*, OsiCuts&, bool&, CoinWarmStartBasis*, double const*,
double const*, OsiSolverBranch*&) ()
#4 0x0000000000504c00 in CbcModel::branchAndBound(int) ()
#5 0x00000000004a47c9 in
CbcHeuristic::smallBranchAndBound(OsiSolverInterface*, int, double*,
double&, double, std::__cxx11::basic_string<char,
std::char_traits<char>, std::allocator<char> >) const ()
#6 0x00000000004b0941 in
CbcHeuristicFPump::solutionInternal(double&, double*) ()
#7 0x00000000004b3165 in CbcHeuristicFPump::solution(double&,
double*) ()
#8 0x00000000004e7482 in CbcModel::doHeuristicsAtRoot(int) ()
#9 0x000000000050534e in CbcModel::branchAndBound(int) ()
#10 0x0000000000422162 in CbcMain1(int, char const**, CbcModel&, int
(*)(CbcModel*, int), CbcSolverUsefulData&) ()
#11 0x000000000043e1e3 in CbcMain1(int, char const**, CbcModel&, int
(*)(CbcModel*, int)) ()
Naively, I thought this might be something specific to the feasibility
pump heuristic, but disabling it only postpones the segfault for a while:
command line - cbc.exe -import sos.lp -feas off -solve (default
strategy 1)
Option for feasibilityPump changed from on to off
Continuous objective value is 15 - 0.00 seconds
Cgl0003I 0 fixed, 67 tightened bounds, 0 strengthened rows, 0
substitutions
Cgl0004I processed model has 277 rows, 652 columns (652 integer (616
of which binary)) and 2812 elements
Cutoff increment increased from 1e-005 to 0.9999
Cbc0031I 3 added rows had average density of 161.66667
Cbc0013I At root node, 3 cuts changed objective from 15 to 15 in 5
passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0
elements, 0 column cuts (0 active) in 0.006 seconds - new frequency
is -100
Cbc0014I Cut generator 1 (Gomory) - 14 row cuts average 280.4
elements, 0 column cuts (0 active) in 0.006 seconds - new frequency
is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0
elements, 0 column cuts (0 active) in 0.002 seconds - new frequency
is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements,
0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 0 row cuts
average 0.0 elements, 0 column cuts (0 active) in 0.001 seconds -
new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0
elements, 0 column cuts (0 active) in 0.001 seconds - new frequency
is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 83 row cuts average 172.0
elements, 0 column cuts (0 active) in 0.012 seconds - new frequency
is -100
Cbc0010I After 0 nodes, 1 on tree, 1e+050 best solution, best
possible 15 (0.11 seconds)
Cbc0010I After 1000 nodes, 494 on tree, 1e+050 best solution, best
possible 15 (3.09 seconds)
Cbc0010I After 2000 nodes, 591 on tree, 1e+050 best solution, best
possible 15 (5.37 seconds)
Cbc0010I After 3000 nodes, 583 on tree, 1e+050 best solution, best
possible 15 (7.20 seconds)
Cbc0010I After 4000 nodes, 577 on tree, 1e+050 best solution, best
possible 15 (9.05 seconds)
Cbc0010I After 5000 nodes, 564 on tree, 1e+050 best solution, best
possible 15 (11.09 seconds)
Cbc0010I After 6000 nodes, 632 on tree, 1e+050 best solution, best
possible 15 (13.07 seconds)
Cbc0010I After 7000 nodes, 622 on tree, 1e+050 best solution, best
possible 15 (14.98 seconds)
Cbc0010I After 8000 nodes, 646 on tree, 1e+050 best solution, best
possible 15 (16.98 seconds)
Cbc0010I After 9000 nodes, 659 on tree, 1e+050 best solution, best
possible 15 (18.67 seconds)
Cbc0010I After 10000 nodes, 728 on tree, 1e+050 best solution, best
possible 15 (20.47 seconds)
Cbc0010I After 11000 nodes, 711 on tree, 1e+050 best solution, best
possible 15 (22.37 seconds)
Cbc0010I After 12000 nodes, 1212 on tree, 1e+050 best solution, best
possible 15 (25.43 seconds)
Cbc0010I After 13000 nodes, 1753 on tree, 1e+050 best solution, best
possible 15 (28.55 seconds)
Cbc0010I After 14000 nodes, 1789 on tree, 1e+050 best solution, best
possible 15 (30.48 seconds)
Cbc0010I After 15000 nodes, 1790 on tree, 1e+050 best solution, best
possible 15 (32.39 seconds)
Cbc0010I After 16000 nodes, 1787 on tree, 1e+050 best solution, best
possible 15 (34.41 seconds)
Cbc0010I After 17000 nodes, 1764 on tree, 1e+050 best solution, best
possible 15 (36.27 seconds)
Cbc0010I After 18000 nodes, 1829 on tree, 1e+050 best solution, best
possible 15 (38.11 seconds)
Cbc0010I After 19000 nodes, 1826 on tree, 1e+050 best solution, best
possible 15 (40.22 seconds)
Cbc0010I After 20000 nodes, 1817 on tree, 1e+050 best solution, best
possible 15 (42.34 seconds)
Cbc0010I After 21000 nodes, 1812 on tree, 1e+050 best solution, best
possible 15 (44.43 seconds)
Cbc0010I After 22000 nodes, 1820 on tree, 1e+050 best solution, best
possible 15 (46.31 seconds)
Cbc0010I After 23000 nodes, 1843 on tree, 1e+050 best solution, best
possible 15 (48.65 seconds)
Cbc0010I After 24000 nodes, 1811 on tree, 1e+050 best solution, best
possible 15 (50.33 seconds)
Cbc0016I Integer solution of 705 found by strong branching after
239392 iterations and 24441 nodes (51.17 seconds)
Cbc0038I Full problem 277 rows 652 columns, reduced to 83 rows 86
columns
Program received signal SIGSEGV, Segmentation fault.
0x000000000051daa5 in CbcSOS::infeasibility(OsiBranchingInformation
const*, int&) const ()
#0 0x000000000051e055 in
CbcSOS::infeasibility(OsiBranchingInformation const*, int&) const ()
#1 0x0000000000764ab2 in
OsiObject::checkInfeasibility(OsiBranchingInformation const*) const ()
#2 0x000000000050e382 in CbcNode::chooseDynamicBranch(CbcModel*,
CbcNode*, OsiSolverBranch*&, int) ()
#3 0x00000000004e85ac in CbcModel::chooseBranch(CbcNode*&, int,
CbcNode*, OsiCuts&, bool&, CoinWarmStartBasis*, double const*,
double const*, OsiSolverBranch*&) ()
#4 0x0000000000504c00 in CbcModel::branchAndBound(int) ()
#5 0x00000000004a47c9 in
CbcHeuristic::smallBranchAndBound(OsiSolverInterface*, int, double*,
double&, double, std::__cxx11::basic_string<char,
std::char_traits<char>, std::allocator<char> >) const ()
#6 0x00000000004c6e3c in CbcHeuristicRINS::solution(double&,
double*) ()
#7 0x00000000004fba0d in CbcModel::doOneNode(CbcModel*, CbcNode*&,
CbcNode*&) ()
#8 0x00000000005010ec in CbcModel::branchAndBound(int) ()
#9 0x0000000000422162 in CbcMain1(int, char const**, CbcModel&, int
(*)(CbcModel*, int), CbcSolverUsefulData&) ()
#10 0x000000000043e1e3 in CbcMain1(int, char const**, CbcModel&, int
(*)(CbcModel*, int)) ()
#11 0x0000000000402709 in main (argc=6, argv=0x28d2ef0) at main.cpp:535
I'm using CBC trunk rev. 2292. I have attached this example, sos.lp, in
case it's useful.
Cheers,
Luís
[1] This was partly motivated by your suggestion to "turn most of the
constraints into mandatory cuts" in a previous response of yours:
<http://list.coin-or.org/pipermail/clp/2016-September/001675.html>.
Thanks! :-)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20161018/65353cca/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sos.lp.gz
Type: application/gzip
Size: 17722 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20161018/65353cca/attachment-0001.gz>
More information about the Cbc
mailing list