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

Am 06.10.2011 23:16, schrieb Sergey Dymchenko:
> On Thu, Oct 6, 2011 at 5:31 PM, Thorsten Winterer
> <thorsten_winterer_at_web.de>  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