- Mail actions: [ respond to this message ] [ mail a new topic ]
- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Bogdan Tanasa <g-bogta_at_...107...>

Date: Wed, 8 Jun 2011 09:55:19 +0200

Received on Wed Jun 08 2011 - 07:55:28 CEST

Date: Wed, 8 Jun 2011 09:55:19 +0200

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

- application/octet-stream attachment: tasm.ecl

*
This archive was generated by hypermail 2.3.0
: Tue Aug 06 2024 - 21:13:21 CEST
*