[Cbc] Another problem "long to be solved"
Yves Touchard
ytouch at dxo.com
Tue Nov 18 09:05:53 EST 2014
John,
Thanks for your (great) support!
I would like to test these improvements but make fails:
[...]
(cd .libs && rm -f libCbc.so.0 && ln -s libCbc.so.0.0.0 libCbc.so.0)
(cd .libs && rm -f libCbc.so && ln -s libCbc.so.0.0.0 libCbc.so)
creating libCbc.la
(cd .libs && rm -f libCbc.la && ln -s ../libCbc.la libCbc.la)
/bin/sh ../../libtool --tag=CXX --mode=link /soft/gcc-4.9.0/bin/g++ -O3 -pipe -DNDEBUG -pedantic-errors -Wparentheses -Wreturn-type -Wcast-qual -Wall -Wpointer-arith -Wwrite-strings -Wconversion -Wno-unknown-pragmas -Wno-long-long -DCBC_BUILD -o cbc CoinSolve.o libCbcSolver.la libCbc.la -lpthread -lrt /home/ytouch/coin-Cbc/Clp/src/OsiClp/libOsiClp.la /home/ytouch/coin-Cbc/Clp/src/libClp.la /home/ytouch/coin-Cbc/Osi/src/Osi/libOsi.la /home/ytouch/coin-Cbc/CoinUtils/src/libCoinUtils.la -lbz2 -lz -lm /home/ytouch/coin-Cbc/Cgl/src/libCgl.la /home/ytouch/coin-Cbc/Clp/src/OsiClp/libOsiClp.la /home/ytouch/coin-Cbc/Clp/src/libClp.la /home/ytouch/coin-Cbc/Osi/src/Osi/libOsi.la /home/ytouch/coin-Cbc/CoinUtils/src/libCoinUtils.la -lbz2 -lz -lm
/soft/gcc-4.9.0/bin/g++ -O3 -pipe -DNDEBUG -pedantic-errors -Wparentheses -Wreturn-type -Wcast-qual -Wall -Wpointer-arith -Wwrite-strings -Wconversion -Wno-unknown-pragmas -Wno-long-long -DCBC_BUILD -o .libs/cbc CoinSolve.o ./.libs/libCbcSolver.so ./.libs/libCbc.so -lpthread -lrt /home/ytouch/coin-Cbc/Cgl/src/.libs/libCgl.so /home/ytouch/coin-Cbc/Clp/src/OsiClp/.libs/libOsiClp.so /home/ytouch/coin-Cbc/Clp/src/.libs/libClp.so /home/ytouch/coin-Cbc/Osi/src/Osi/.libs/libOsi.so /home/ytouch/coin-Cbc/CoinUtils/src/.libs/libCoinUtils.so -lbz2 -lz -lm -Wl,--rpath -Wl,/home/ytouch/coin-Cbc/lib
./.libs/libCbc.so: undefined reference to `CoinPthreadStuff::waitParallelTask(int, int&, bool)'
./.libs/libCbc.so: undefined reference to `CoinPthreadStuff::waitAllTasks()'
./.libs/libCbc.so: undefined reference to `CoinPthreadStuff::sayIdle(int)'
./.libs/libCbc.so: undefined reference to `CoinPthreadStuff::~CoinPthreadStuff()'
./.libs/libCbc.so: undefined reference to `CoinPthreadStuff::CoinPthreadStuff(int, void* (*)(void*))'
./.libs/libCbc.so: undefined reference to `CoinPthreadStuff::startParallelTask(int, int, void*)'
./.libs/libCbc.so: undefined reference to `CoinPthreadStuff::whichThread() const'
collect2: error: ld returned 1 exit status
make[3]: *** [cbc] Error 1
make[3]: Leaving directory `/home/ytouch/coin-Cbc/Cbc/src'
make[2]: *** [all] Error 2
make[2]: Leaving directory `/home/ytouch/coin-Cbc/Cbc/src'
make[1]: *** [all-recursive] Error 1
make[1]: Leaving directory `/home/ytouch/coin-Cbc/Cbc'
make: *** [all-recursive] Error 1
Tested with a fresh new svn base.
Yves
On 11/18/2014 02:10 PM, cbc-request at list.coin-or.org<mailto:cbc-request at list.coin-or.org> wrote:
Send Cbc mailing list submissions to
cbc at list.coin-or.org<mailto:cbc at list.coin-or.org>
To subscribe or unsubscribe via the World Wide Web, visit
http://list.coin-or.org/mailman/listinfo/cbc
or, via email, send a message with subject or body 'help' to
cbc-request at list.coin-or.org<mailto:cbc-request at list.coin-or.org>
You can reach the person managing the list at
cbc-owner at list.coin-or.org<mailto:cbc-owner at list.coin-or.org>
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Cbc digest..."
Today's Topics:
1. Re: Another problem "long to be solved" (John Forrest)
2. Re: New Heuristic (due to Fischetti and Monaci) (Matteo Fischetti)
3. Re: Another problem "long to be solved" (John Forrest)
4. Re: Another problem "long to be solved" ( Lu?s Borges de Oliveira)
----------------------------------------------------------------------
Message: 1
Date: Mon, 17 Nov 2014 17:46:57 +0000
From: John Forrest <john.forrest at fastercoin.com><mailto:john.forrest at fastercoin.com>
To: cbc at list.coin-or.org<mailto:cbc at list.coin-or.org>
Subject: Re: [Cbc] Another problem "long to be solved"
Message-ID: <546A3491.5040304 at fastercoin.com><mailto:546A3491.5040304 at fastercoin.com>
Content-Type: text/plain; charset="windows-1252"; Format="flowed"
Yves,
I have been making some modifications to the diving heuristics which
should help.
I have a lot of changes to trunk - but I think the unsafe ideas are not
normally switched on - so should be safe to update trunk. Will do it
tomorrow.
John
On 17/11/14 11:43, Yves Touchard wrote:
Hello,
I split an huge problem in several little problems which sizes are
(IMO) equivalent.
Solving each of them lasts several seconds (no more than 2-3 seconds)
except one (several minutes).
I tried different combination of options (w/wo diving, w/wo zero
root...) without any success. (threads 104 ratio 0.05 cutlength 40
multiple 4 divingv on divingl on divingf on divingg on divingc on
divingp on zero root)
Have you an idea to help this problem to be fastly solved ? Or my
splitting and the cost function are not well balanced ?
The constraint file may be downloaded here:
https://www.dropbox.com/s/lbd7o2bdn5392m1/long.lp?dl=0
One of the sol file may be downloaded here:
https://www.dropbox.com/s/a7foc860ap6lbmn/long.txt?dl=0
I use the the trunk version, revision #2092, compiled with gcc 4.9.0
Thanks and regards
Yves
------------------------------------------------------------------------------
This message and any attachments (the "message") are confidential and
intended solely for the addressee(s). Any unauthorized use or
dissemination is prohibited. E-mails are susceptible to alteration.
Neither DxO Labs nor any of its subsidiaries or affiliates shall be
liable for the message if altered, changed or falsified.
Ce message et toutes les pi?ces jointes (ci-apr?s le "message") sont
confidentiels et ?tablis ? l'intention exclusive de ses destinataires.
Toute utilisation ou diffusion non autoris? est interdite. Tout
message ?lectronique est susceptible d'alt?ration. DxO Labs et ses
filiales d?clinent toute responsabilit? au titre de ce message s'il a
?t? alt?r?, modifi? ou falsifi?.
_______________________________________________
Cbc mailing list
Cbc at list.coin-or.org<mailto: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/20141117/4198e593/attachment-0001.html><http://list.coin-or.org/pipermail/cbc/attachments/20141117/4198e593/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 17 Nov 2014 19:16:05 +0100
From: Matteo Fischetti <m.fischetti at gmail.com><mailto:m.fischetti at gmail.com>
To: John Forrest <john.forrest at fastercoin.com><mailto:john.forrest at fastercoin.com>
Cc: cbc at list.coin-or.org<mailto:cbc at list.coin-or.org>, Michele Monaci <monaci at dei.unipd.it><mailto:monaci at dei.unipd.it>
Subject: Re: [Cbc] New Heuristic (due to Fischetti and Monaci)
Message-ID: <38C522A2-DE19-44E7-B924-4FBCDF36DB06 at gmail.com><mailto:38C522A2-DE19-44E7-B924-4FBCDF36DB06 at gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Dear John,
for your reference, the final version (with some improvements over the first version) of my joint paper with Michele Monaci on Proximity Search is now printed on
M. Fischetti, M. Monaci, "Proximity Search for 0-1 Mixed-Integer Convex Programming", Journal of Heuristics 20 (6), 709-731, 2014. DOI: 10.1007/s10732-014-9266-x
@article{
year={2014},
issn={1381-1231},
journal={Journal of Heuristics},
volume={20},
number={6},
doi={10.1007/s10732-014-9266-x},
title={Proximity search for 0-1 mixed-integer convex programming},
url={http://dx.doi.org/10.1007/s10732-014-9266-x},
publisher={Springer US},
keywords={Mixed-integer convex optimization; Proximal methods; Primal methods; Heuristics},
author={Fischetti, Matteo and Monaci, Michele},
pages={709-731},
language={English}
}
Best
Matteo
Il giorno 21/nov/2012, alle ore 13:11, John Forrest <john.forrest at fastercoin.com><mailto:john.forrest at fastercoin.com> ha scritto:
I am pleased to say that I have spent a very small amount of time implementing the Proximity Search heuristic by Fischetti and Monaci.
At present it is only in Cbc trunk and by default is off. The simplest way to switch it on using stand-alone version is "-proximity on".
Proximity Search is the new "No-Neighborhood Search" 0-1 MIP refinement heuristic recently proposed by Fischetti and Monaci (2012). The idea is to define a sub-MIP without additional constraints but with a modified objective function intended to attract the search in the proximity of the incumbent. The approach works well for 0-1 MIPs whose solution landscape is not too irregular (meaning the there is reasonable probability of finding an improved solution by flipping a small number of binary variables), in particular when it is applied to the first heuristic solutions found at the root node. Feedback about (un)successful applications are very welcome, and can be send directly to Matteo Fischetti (matteo.fischetti at unipd.it<mailto:matteo.fischetti at unipd.it>)
Feedback about unsuccessful applications may also be sent to me as I may need to improve my implementation.
John Forrest
_______________________________________________
Cbc mailing list
Cbc at list.coin-or.org<mailto:Cbc at list.coin-or.org>
http://list.coin-or.org/mailman/listinfo/cbc
---
Prof. Matteo Fischetti
DEI, University of Padova
via Gradenigo 6/A
I-35131 Padova (Italy)
e-mail: matteo.fischetti at unipd.it<mailto:matteo.fischetti at unipd.it>
web: www.dei.unipd.it/~fisch<http://www.dei.unipd.it/~fisch>
reports: www.dei.unipd.it/~fisch/papers<http://www.dei.unipd.it/~fisch/papers>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20141117/19c87796/attachment-0001.html><http://list.coin-or.org/pipermail/cbc/attachments/20141117/19c87796/attachment-0001.html>
------------------------------
Message: 3
Date: Tue, 18 Nov 2014 12:03:16 +0000
From: John Forrest <john.forrest at fastercoin.com><mailto:john.forrest at fastercoin.com>
To: cbc at list.coin-or.org<mailto:cbc at list.coin-or.org>
Subject: Re: [Cbc] Another problem "long to be solved"
Message-ID: <546B3584.9070306 at fastercoin.com><mailto:546B3584.9070306 at fastercoin.com>
Content-Type: text/plain; charset="windows-1252"; Format="flowed"
Yves,
In trunk there are some new/modified options.
There was a parameter "experiment". I have left some old meanings, but
introduced some new ones. For difficult problems I would suggest
-experiment 3000 !!. This actually switches on multiple root solvers
(4), does more aggressive preprocessing, adds some extra root cut
generators AND switches on most diving heuristics.
When I tried, the code had no problems with long.lp, but I would suggest
you look at a new parameter divesolves. This can increase the number of
solves a diving heuristic can do. The bottom digit is ignored for
number of solves but can switch on something which could help you a
lot. Normally the diving heuristics fix some integer variables if they
are at their bound, however they do not fix satisfied general integer
variables - not at bound - so if 0 <= x <= 20 and x is at 12 then it
does not get fixed. I have allowed this behaviour to change so
-divesolves 301 will allow up to 300 solves and will fix some satisfied
general integers.
You may also want to look at diveoptions and even set -DDIVE_PRINT=1 in
configure. This switches on some printout which may help you understand
what is happening in which heuristic.
John
On 17/11/14 11:43, Yves Touchard wrote:
Hello,
I split an huge problem in several little problems which sizes are
(IMO) equivalent.
Solving each of them lasts several seconds (no more than 2-3 seconds)
except one (several minutes).
I tried different combination of options (w/wo diving, w/wo zero
root...) without any success. (threads 104 ratio 0.05 cutlength 40
multiple 4 divingv on divingl on divingf on divingg on divingc on
divingp on zero root)
Have you an idea to help this problem to be fastly solved ? Or my
splitting and the cost function are not well balanced ?
The constraint file may be downloaded here:
https://www.dropbox.com/s/lbd7o2bdn5392m1/long.lp?dl=0
One of the sol file may be downloaded here:
https://www.dropbox.com/s/a7foc860ap6lbmn/long.txt?dl=0
I use the the trunk version, revision #2092, compiled with gcc 4.9.0
Thanks and regards
Yves
------------------------------------------------------------------------------
This message and any attachments (the "message") are confidential and
intended solely for the addressee(s). Any unauthorized use or
dissemination is prohibited. E-mails are susceptible to alteration.
Neither DxO Labs nor any of its subsidiaries or affiliates shall be
liable for the message if altered, changed or falsified.
Ce message et toutes les pi?ces jointes (ci-apr?s le "message") sont
confidentiels et ?tablis ? l'intention exclusive de ses destinataires.
Toute utilisation ou diffusion non autoris? est interdite. Tout
message ?lectronique est susceptible d'alt?ration. DxO Labs et ses
filiales d?clinent toute responsabilit? au titre de ce message s'il a
?t? alt?r?, modifi? ou falsifi?.
_______________________________________________
Cbc mailing list
Cbc at list.coin-or.org<mailto: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/20141118/a917c99c/attachment-0001.html><http://list.coin-or.org/pipermail/cbc/attachments/20141118/a917c99c/attachment-0001.html>
------------------------------
Message: 4
Date: Tue, 18 Nov 2014 13:09:58 +0000
From: lbo at siscog.pt<mailto:lbo at siscog.pt> ( Lu?s Borges de Oliveira)
To: John Forrest <john.forrest at fastercoin.com><mailto:john.forrest at fastercoin.com>
Cc: cbc at list.coin-or.org<mailto:cbc at list.coin-or.org>
Subject: Re: [Cbc] Another problem "long to be solved"
Message-ID: <y538uj87izd.fsf at siscog.pt><mailto:y538uj87izd.fsf at siscog.pt>
Content-Type: text/plain; charset=utf-8
Hello John,
John Forrest <john.forrest at fastercoin.com><mailto:john.forrest at fastercoin.com> writes:
In trunk there are some new/modified options.
FWIW, I was interested in giving these options a spin so I tried to
compile the Cbc trunk using mingw64 but got the following error:
CbcNode.cpp:4566:14: error: 'NUMBER_THREADS' was not declared in this scope
int status[NUMBER_THREADS];
^
That file seems to assume in a couple of other places that threading is
present.
Please let me know if I can provide more information.
Cheers,
Lu?s
------------------------------
_______________________________________________
Cbc mailing list
Cbc at list.coin-or.org<mailto:Cbc at list.coin-or.org>
http://list.coin-or.org/mailman/listinfo/cbc
End of Cbc Digest, Vol 89, Issue 8
**********************************
------------------------------------------------------------------------------
This message and any attachments (the "message") are confidential and intended solely for the addressee(s). Any unauthorized use or dissemination is prohibited. E-mails are susceptible to alteration. Neither DxO Labs nor any of its subsidiaries or affiliates shall be liable for the message if altered, changed or falsified.
Ce message et toutes les pièces jointes (ci-après le "message") sont confidentiels et établis à l'intention exclusive de ses destinataires. Toute utilisation ou diffusion non autorisé est interdite. Tout message électronique est susceptible d'altération. DxO Labs et ses filiales déclinent toute responsabilité au titre de ce message s'il a été altéré, modifié ou falsifié.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20141118/ec976125/attachment-0001.html>
More information about the Cbc
mailing list