<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Apologies for long post.<br>
<br>
When I ran the problem (with 4 threads) I got - <br>
<br>
extrav - 7338 seconds and 10711 nodes<br>
no extrav 5875 seconds and 14445 nodes<br>
<br>
so the extra work per node meant that extrav lost out.<br>
<br>
One big reason is that until a good solution is obtained, a solve
can take many iterations with the objective increasing to a very
large value.<br>
<br>
So it is important to get good heuristic solutions at root node.<br>
<br>
Now the feasibility pump heuristic can be very powerful and there
are many obscure options set by some hocus pocus. There is a
parameter pumptune whose default value is (obviously)1005043! The
1 actually does setAccumulate(1) in the feasibility pump
heuristic. In general the heuristic is designed for 0-1 problems
- if only a small percentage of integer variables are general,
then it will treat them as continuous and then try a small branch
and bound to try and fix up. In this case all variables are
general so it just exits.<br>
<br>
If the 1 is changed to a 5 then it always does the feasibility
pump and plays some tricks. So I tried adding -pumptune 5005043
-multiple 4, which will do feasibility pump and try four different
starting continuous solutions in parallel. With this the extrav
run gets a reasonable root solution and both improve to 6792
seconds and 5311 seconds.<br>
<br>
There still is a problem in that the extra variable was added to
improve branching, and will probably have a detrimental effect on
heuristics. So in trunk I have modified code in most heuristics
to test - isHeuristicInteger. This should make no difference to
the no extrav version - but trunk is slightly different in other
ways - and any change makes a difference (see Haroldo's remarks).
So extrav changes to 5479 seconds while the no extrav gets a bit
worse to 5877.<br>
<br>
I have not committed changes in trunk. Anyway, I would recommend
change to parameters.<br>
<br>
John Forrest <br>
<br>
On 06/06/16 15:28, <a class="moz-txt-link-abbreviated" href="mailto:acw@ascent.com">acw@ascent.com</a> wrote:<br>
</div>
<blockquote
cite="mid:OF29127B0F.91D35336-ON85257FCA.004DDD1D-85257FCA.004F7924@ascent.com"
type="cite">
<meta http-equiv="Context-Type" content="text/html;
charset=US-ASCII">
This is a sequel to a problem I posted
about back in April.
<br>
<br>
I have a 3.4 Mb MPS file that has the
following behavior:
<br>
<br>
cbc -import extrav-test.mps -extrav
10 -solve -quit
<br>
<br>
takes 9723 CPU seconds to solve, while
<br>
<br>
cbc -import extrav-test.mps -solve -quit
<br>
<br>
takes 10850 CPU seconds. The difference
is only about 10%, but it's in the wrong direction -- that is, the
-extraVariables
trick makes it solve slower. In April I presented a similar case,
but Dr.
Forrest pointed out on that occasion that the solver spent most of
its
time on heuristics, and the problem was in fact solved by
heuristic; apparently
introducing the extra variables slows down the heuristic phase.
<br>
<br>
But the new problem spends most of its
time branching, and -extrav still slows it down, though not as
dramatically
as the earlier problem. I can't send the MPS file to the list
because it's
too big, but I will be happy to share it with anybody who is
willing to
take a look.
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Cbc mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Cbc@list.coin-or.org">Cbc@list.coin-or.org</a>
<a class="moz-txt-link-freetext" href="http://list.coin-or.org/mailman/listinfo/cbc">http://list.coin-or.org/mailman/listinfo/cbc</a>
</pre>
</blockquote>
<br>
</body>
</html>