From: Kish Shen <kisshen_at_cisco.com>

Date: Wed, 08 Jun 2011 02:54:31 +0100

Date: Wed, 08 Jun 2011 02:54:31 +0100

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.Received on Wed Jun 08 2011 - 01:54:46 CEST

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*