Re: [eclipse-clp-users] Eplex

Hi Kish,

Thank you for your answer. I tried to fix some parts in the code.

By ILP I tried to say when all variables are integers and by MILP when only
some of the variables are integers. The int_csp predicate transforms some
variables into integers.

If the call int_csp(L, N, BoolMatrix), is commented and the call eplex:
(integers(Row)) is not then the code should solve the ILP problem. In the
opposite case the code should solve the MILP problem.

For the case when roughly half of the variables are integers the MILP takes
considerable more time the ILP for large values of L. I was suspecting that
this behavior is not normal since the difference between total number if
integer variables is quite big. 

Thanks,
Bogdan.

-----Original Message-----
From: Kish Shen [mailto:kisshen_at_cisco.com] 
Sent: 8 iunie 2011 03:55
To: Bogdan Tanasa
Cc: eclipse-clp-users_at_lists.sourceforge.net
Subject: Re: [eclipse-clp-users] Eplex

Hi Bogdan,


On 05/06/2011 17:19, Bogdan Tanasa wrote:

> I am trying to solve a MILP problem using Eplex invoked from CLP. The
> optimization variables are Boolean variables but because the ILP
equivalent
> problem is hard to solve it in a reasonable amount of time I decided to do
> some relaxations.

I am not sure I follow your code very well -- although you post some ic 
constraints, your calls to eplex solve the problems as pure MP problems, 
and you never perform any search (i.e. labelling the problem variables, 
so except for whatever initial propagation you can get from posting your 
ic constraints, nothing else seem to use them. The complete_search 
predicate seems to only set up the eplex constraints, rather than 
performing any search -- it seems to leave behind some choicepoints if 
you call int_csp/4, by labelling one set of variables as integer, and 
then (from what I can tell) some other variables.

> Now I have an example where if I am trying to solve the ILP problem it
takes
> around 120 seconds. I was thinking to force eplex to see only some Boolean
> variables as integers and the others as float numbers in order to check if
I
> can get an suboptimal solution faster.
>
> I have seen that in general this is not the case. Solving the ILP can be
> faster than solving the MILP.

> Can someone please explain to me this behavior? I attached my clp code.
>

I am not sure what exactly you mean -- in the code you sent, I modified 
your code to run 3 variants:

1) No integer variables, i.e. a linear problem
2) The code as you sent it, where there are few integer variables
3) I uncommented your call to int_csp/4, which turns about half the 
variables to integers.

This behave as might be expected, such that the more integer variables 
you have (for the same problem), the longer it takes the MIP solver to 
solve the problem. For example, for your L = 7 problem, which has 581 
columns (variables) and 763 rows (constraints), variant 1 has 0 integer 
variable, variant 2 has 10, and variant 3 has 220, and the time to solve 
this problem are

1)  0.01 sec
2)  0.05 sec
3) 50    sec

using CLP/CBC as the solver,

What exactly do you mean by 'Solving the ILP can be faster than solving 
the MILP'? If by ILP you mean all variables being integers, then the 
code does not do this. In any case, it is certainly possible for a 
specific instance that has more integer variables to be solved faster 
than one with less, especially if the proportional difference in the 
integer variable is small when you ave lots of integer variables.

Cheers,

Kish

-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.