[Cbc] Segfault solving a problem containing SOSs
John Forrest
john.forrest at fastercoin.com
Wed Oct 19 11:09:09 EDT 2016
Luis,
Can duplicate an error - will try and debug.
John Forrest
On 18/10/16 18:36, Luís Borges de Oliveira wrote:
> 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! :-)
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> https://urldefense.proofpoint.com/v2/url?u=http-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=CwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=6bp6XVnDyBE6AUyhwgl7nVe4LGvoYGSDpMuVdJfxeeI&s=1sZhc6WjykfRrV8vSGBUEk-ceb9UDg8Cb6ZByfBxcp0&e=
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20161019/0071af5f/attachment.html>
More information about the Cbc
mailing list