Re: [eclipse-clp-users] Eplex

From: Kish Shen <kisshen_at_...5...>
Date: Wed, 08 Jun 2011 13:23:31 +0100
Hi Bogdan,

On 08/06/2011 08:55, Bogdan Tanasa wrote:

> 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.
>

The case with eplex: (integers(Rows)) only is what you have in your 
original code, right? This is the variant 2 I mentioned, i.e. the one 
with few integer variables. For the case of L = 7, it has 30 integer 
variables (out of 748 variables). I have not looked at your code in 
detail, but it looks like this is not doing what you expected, i.e. 
making all variables in your problem integers. This might also imply 
that not all your variables are 0/1 variables as you expect.

I got the information on the problem using eplex_get/2. You can also 
write out the problem using eplex_write/2 -- I suggest using the lp 
format, which is much easier to read.

Cheers,

Kish



> 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@...5...]
> 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
>
>
>
>
> ------------------------------------------------------------------------------
> EditLive Enterprise is the world's most technically advanced content
> authoring tool. Experience the power of Track Changes, Inline Image
> Editing and ensure content is compliant with Accessibility Checking.
> http://p.sf.net/sfu/ephox-dev2dev
>
>
>
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users


-- 
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.
Received on Wed Jun 08 2011 - 12:23:41 CEST

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