Re: [eclipse-clp-users] Minimizing a parameter that depends on global state

From: Thorsten Winterer <thorsten_winterer_at_...126...>
Date: Fri, 07 Oct 2011 08:49:34 +0200
```Am 06.10.2011 23:16, schrieb Sergey Dymchenko:
> On Thu, Oct 6, 2011 at 5:31 PM, Thorsten Winterer
> <thorsten_winterer@...126...>  wrote:
>> Here is a test case that Sergey supplied where proving optimality was too
>> expensive for CLP:
>>
>> solve(9, [](1, 2, 1, 4, 5, 6, 7, 4, 3, 1, 2, 3, 4, 5, 6, 7, 8, 9,
>>              9, 8, 7, 6, 5, 4, 3, 2, 1, 9, 8, 7, 6, 5, 4, 3, 2, 1,
>>              9, 8, 3, 2, 1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 9, 8, 3, 2,
>>              1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 9, 8, 3, 2, 1, 9, 8, 7,
>>              6, 5, 4, 3, 2, 1, 9, 8, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9,
>>              1, 1, 2, 3, 4, 5, 6, 7, 8, 9), S).
>>
>> Assuming that the strategy is optimal and using search/6 alone, it can be
>> solved in 0.01 seconds. Proving optimality takes forever with the CLP
>> program, though  (I stopped it eventually). Your eplex program takes 0.5
>> seconds with CPLEX to find a (proven) optimal solution.
> Unfortunately, with OSI solvers it takes forever...
>
> Sergey.

But that's a general problem with CLP/CBC and integer problems. Which is
why I only use it for very small problems. For pure LP problems, it is
ok-ish (and of course much cheaper than CPLEX or Xpress).

Here's a reformulation of some parts of the MIP that lets ECLiPSe solve
it with CLP/CBC in 1.77 seconds, possibly because it uses fewer integer
variables:

( count(I, 2, Q), fromto(0, C_previous, C_current, C),
param(States,S) do
%C_current = (States[I] =\= States[I - 1]) + C_previous ),
States[I]-States[I-1] \$= Diff1,
States[I-1]-States[I] \$= Diff2,
Diff \$>= Diff1, Diff \$>= Diff2, % Diff is max(Diff1, Diff2)
Switch \$:: 0..1,
0 \$>= Diff-S*Switch,    % Diff > 0 -> Switch = 1
0 \$=< Diff-0.3*Switch,  % Diff = 0 -> Switch = 0, cf. Williams,
"Model Building"
integers([Switch]),
C_current \$= C_previous + Switch
),

Note that, interestingly, the factor m in the formula "0 \$=<
Diff-SmallM*Switch" makes a difference for CBC, while for CPLEX, I
didn't see any. With a factor of 0.01, the program takes 17.18 seconds
with CBC. With 0.1, it's 2.9 seconds. Larger than 0.3, and the times get
worse again.

I have no idea what happens inside CBC, and why it sometimes takes forever.

Cheers,
Thorsten
```
Received on Fri Oct 07 2011 - 06:49:42 CEST

This archive was generated by hypermail 2.2.0 : Mon Jul 09 2018 - 02:05:29 CEST