<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hello,<br>
<br>
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!<br>
<br>
Alas, I have found some issues leading to segfaults in certain
instances.<br>
<blockquote><tt>command line - cbc.exe -import sos.lp -solve
(default strategy 1)</tt><br>
<tt>Continuous objective value is 15 - 0.00 seconds</tt><br>
<tt>Cgl0003I 0 fixed, 67 tightened bounds, 0 strengthened rows, 0
substitutions</tt><br>
<tt>Cgl0004I processed model has 277 rows, 652 columns (652
integer (616 of which binary)) and 2812 elements</tt><br>
<tt>Cutoff increment increased from 1e-005 to 0.9999</tt><br>
<tt>Cbc0038I Initial state - 28 integers unsatisfied sum - 12.2793</tt><br>
<tt>Cbc0038I Pass 1: suminf. 0.57576 (4) obj. 114 iterations
116</tt><br>
<tt>Cbc0038I Pass 2: suminf. 0.15933 (4) obj. 114 iterations
60</tt><br>
<tt>Cbc0038I Solution found of 114</tt><br>
<tt>Cbc0038I Before mini branch and bound, 579 integers at bound
fixed and 36 continuous</tt><br>
<tt>Cbc0038I Full problem 277 rows 652 columns, reduced to 23 rows
20 columns</tt><br>
<font color="#cc0000"><tt>Program received signal SIGSEGV,
Segmentation fault.</tt><br>
<tt>0x000000000051e064 in
CbcSOS::infeasibility(OsiBranchingInformation const*,
int&) const ()</tt></font><br>
<br>
<tt>Backtrace:</tt><br>
<tt>#0 0x000000000051e064 in
CbcSOS::infeasibility(OsiBranchingInformation const*, int&)
const ()</tt><br>
<tt>#1 0x0000000000764ab2 in
OsiObject::checkInfeasibility(OsiBranchingInformation const*)
const ()</tt><br>
<tt>#2 0x000000000050e382 in
CbcNode::chooseDynamicBranch(CbcModel*, CbcNode*,
OsiSolverBranch*&, int) ()</tt><br>
<tt>#3 0x00000000004e85ac in
CbcModel::chooseBranch(CbcNode*&, int, CbcNode*,
OsiCuts&, bool&, CoinWarmStartBasis*, double const*,
double const*, OsiSolverBranch*&) ()</tt><br>
<tt>#4 0x0000000000504c00 in CbcModel::branchAndBound(int) ()</tt><br>
<tt>#5 0x00000000004a47c9 in
CbcHeuristic::smallBranchAndBound(OsiSolverInterface*, int,
double*, double&, double,
std::__cxx11::basic_string<char,
std::char_traits<char>, std::allocator<char> >)
const ()</tt><br>
<tt>#6 0x00000000004b0941 in
CbcHeuristicFPump::solutionInternal(double&, double*) ()</tt><br>
<tt>#7 0x00000000004b3165 in
CbcHeuristicFPump::solution(double&, double*) ()</tt><br>
<tt>#8 0x00000000004e7482 in CbcModel::doHeuristicsAtRoot(int) ()</tt><br>
<tt>#9 0x000000000050534e in CbcModel::branchAndBound(int) ()</tt><br>
<tt>#10 0x0000000000422162 in CbcMain1(int, char const**,
CbcModel&, int (*)(CbcModel*, int),
CbcSolverUsefulData&) ()</tt><br>
<tt>#11 0x000000000043e1e3 in CbcMain1(int, char const**,
CbcModel&, int (*)(CbcModel*, int)) ()</tt><br>
</blockquote>
<br>
Naively, I thought this might be something specific to the
feasibility pump heuristic, but disabling it only postpones the
segfault for a while:<br>
<br>
<blockquote><tt>command line - cbc.exe -import sos.lp -feas off
-solve (default strategy 1)</tt><br>
<tt>Option for feasibilityPump changed from on to off</tt><br>
<tt>Continuous objective value is 15 - 0.00 seconds</tt><br>
<tt>Cgl0003I 0 fixed, 67 tightened bounds, 0 strengthened rows, 0
substitutions</tt><br>
<tt>Cgl0004I processed model has 277 rows, 652 columns (652
integer (616 of which binary)) and 2812 elements</tt><br>
<tt>Cutoff increment increased from 1e-005 to 0.9999</tt><br>
<tt>Cbc0031I 3 added rows had average density of 161.66667</tt><br>
<tt>Cbc0013I At root node, 3 cuts changed objective from 15 to 15
in 5 passes</tt><br>
<tt>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</tt><br>
<tt>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</tt><br>
<tt>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</tt><br>
<tt>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</tt><br>
<tt>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</tt><br>
<tt>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</tt><br>
<tt>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</tt><br>
<tt>Cbc0010I After 0 nodes, 1 on tree, 1e+050 best solution, best
possible 15 (0.11 seconds)</tt><br>
<tt>Cbc0010I After 1000 nodes, 494 on tree, 1e+050 best solution,
best possible 15 (3.09 seconds)</tt><br>
<tt>Cbc0010I After 2000 nodes, 591 on tree, 1e+050 best solution,
best possible 15 (5.37 seconds)</tt><br>
<tt>Cbc0010I After 3000 nodes, 583 on tree, 1e+050 best solution,
best possible 15 (7.20 seconds)</tt><br>
<tt>Cbc0010I After 4000 nodes, 577 on tree, 1e+050 best solution,
best possible 15 (9.05 seconds)</tt><br>
<tt>Cbc0010I After 5000 nodes, 564 on tree, 1e+050 best solution,
best possible 15 (11.09 seconds)</tt><br>
<tt>Cbc0010I After 6000 nodes, 632 on tree, 1e+050 best solution,
best possible 15 (13.07 seconds)</tt><br>
<tt>Cbc0010I After 7000 nodes, 622 on tree, 1e+050 best solution,
best possible 15 (14.98 seconds)</tt><br>
<tt>Cbc0010I After 8000 nodes, 646 on tree, 1e+050 best solution,
best possible 15 (16.98 seconds)</tt><br>
<tt>Cbc0010I After 9000 nodes, 659 on tree, 1e+050 best solution,
best possible 15 (18.67 seconds)</tt><br>
<tt>Cbc0010I After 10000 nodes, 728 on tree, 1e+050 best solution,
best possible 15 (20.47 seconds)</tt><br>
<tt>Cbc0010I After 11000 nodes, 711 on tree, 1e+050 best solution,
best possible 15 (22.37 seconds)</tt><br>
<tt>Cbc0010I After 12000 nodes, 1212 on tree, 1e+050 best
solution, best possible 15 (25.43 seconds)</tt><br>
<tt>Cbc0010I After 13000 nodes, 1753 on tree, 1e+050 best
solution, best possible 15 (28.55 seconds)</tt><br>
<tt>Cbc0010I After 14000 nodes, 1789 on tree, 1e+050 best
solution, best possible 15 (30.48 seconds)</tt><br>
<tt>Cbc0010I After 15000 nodes, 1790 on tree, 1e+050 best
solution, best possible 15 (32.39 seconds)</tt><br>
<tt>Cbc0010I After 16000 nodes, 1787 on tree, 1e+050 best
solution, best possible 15 (34.41 seconds)</tt><br>
<tt>Cbc0010I After 17000 nodes, 1764 on tree, 1e+050 best
solution, best possible 15 (36.27 seconds)</tt><br>
<tt>Cbc0010I After 18000 nodes, 1829 on tree, 1e+050 best
solution, best possible 15 (38.11 seconds)</tt><br>
<tt>Cbc0010I After 19000 nodes, 1826 on tree, 1e+050 best
solution, best possible 15 (40.22 seconds)</tt><br>
<tt>Cbc0010I After 20000 nodes, 1817 on tree, 1e+050 best
solution, best possible 15 (42.34 seconds)</tt><br>
<tt>Cbc0010I After 21000 nodes, 1812 on tree, 1e+050 best
solution, best possible 15 (44.43 seconds)</tt><br>
<tt>Cbc0010I After 22000 nodes, 1820 on tree, 1e+050 best
solution, best possible 15 (46.31 seconds)</tt><br>
<tt>Cbc0010I After 23000 nodes, 1843 on tree, 1e+050 best
solution, best possible 15 (48.65 seconds)</tt><br>
<tt>Cbc0010I After 24000 nodes, 1811 on tree, 1e+050 best
solution, best possible 15 (50.33 seconds)</tt><br>
<tt>Cbc0016I Integer solution of 705 found by strong branching
after 239392 iterations and 24441 nodes (51.17 seconds)</tt><br>
<tt>Cbc0038I Full problem 277 rows 652 columns, reduced to 83 rows
86 columns</tt><br>
<tt><font color="#cc0000">Program received signal SIGSEGV,
Segmentation fault.</font></tt><br>
<tt><font color="#cc0000">0x000000000051daa5 in
CbcSOS::infeasibility(OsiBranchingInformation const*,
int&) const ()</font></tt><br>
<br>
<tt>#0 0x000000000051e055 in
CbcSOS::infeasibility(OsiBranchingInformation const*, int&)
const ()</tt><br>
<tt>#1 0x0000000000764ab2 in
OsiObject::checkInfeasibility(OsiBranchingInformation const*)
const ()</tt><br>
<tt>#2 0x000000000050e382 in
CbcNode::chooseDynamicBranch(CbcModel*, CbcNode*,
OsiSolverBranch*&, int) ()</tt><br>
<tt>#3 0x00000000004e85ac in
CbcModel::chooseBranch(CbcNode*&, int, CbcNode*,
OsiCuts&, bool&, CoinWarmStartBasis*, double const*,
double const*, OsiSolverBranch*&) ()</tt><br>
<tt>#4 0x0000000000504c00 in CbcModel::branchAndBound(int) ()</tt><br>
<tt>#5 0x00000000004a47c9 in
CbcHeuristic::smallBranchAndBound(OsiSolverInterface*, int,
double*, double&, double,
std::__cxx11::basic_string<char,
std::char_traits<char>, std::allocator<char> >)
const ()</tt><br>
<tt>#6 0x00000000004c6e3c in
CbcHeuristicRINS::solution(double&, double*) ()</tt><br>
<tt>#7 0x00000000004fba0d in CbcModel::doOneNode(CbcModel*,
CbcNode*&, CbcNode*&) ()</tt><br>
<tt>#8 0x00000000005010ec in CbcModel::branchAndBound(int) ()</tt><br>
<tt>#9 0x0000000000422162 in CbcMain1(int, char const**,
CbcModel&, int (*)(CbcModel*, int),
CbcSolverUsefulData&) ()</tt><br>
<tt>#10 0x000000000043e1e3 in CbcMain1(int, char const**,
CbcModel&, int (*)(CbcModel*, int)) ()</tt><br>
<tt>#11 0x0000000000402709 in main (argc=6, argv=0x28d2ef0) at
main.cpp:535</tt><br>
</blockquote>
<br>
<br>
I'm using CBC trunk rev. 2292. I have attached this example, sos.lp,
in case it's useful.<br>
<br>
Cheers,<br>
Luís<br>
<br>
<br>
[1] This was partly motivated by your suggestion to "turn most of
the constraints into mandatory cuts" in a previous response of
yours:
<a class="moz-txt-link-rfc2396E" href="http://list.coin-or.org/pipermail/clp/2016-September/001675.html"><http://list.coin-or.org/pipermail/clp/2016-September/001675.html></a>.
Thanks! :-)<br>
</body>
</html>