Re: [eclipse-clp-users] reduced cost based filtering technique

On 20/12/2011 14:54, sharareh monfared wrote:
> hello,
>
> I want to know how I can implement reduced cost based filtering technique in my code.
> I wrote a code for an employee timetabling problem but I can't get the optimal solution, so I want to use this technique to reduce the domains more by considering the LP relaxation of the problem, how can I do this? Is there any similar examples that use this technique? also do I need anything besides Eclipse?
>
> thank you
> Sharareh
>

Hi Sharareh,

I am not sure if I completely understand your question, it looks to me 
you are asking a specific question (about reduced cost filtering 
technique), but if I am understanding you correctly, you seem to want 
the answer to a much more general question about how to implement hybrid 
techniques to solve problems.

I am not sure what you mean exactly by "reduced cost based filtering 
technique"; the only usage of reduced cost I know about is associated 
with solving a linear problem using the Simplex method, and reduced cost 
is a property associated with columns in the matrix (variables in your 
problem), which can be used to guide the finding of an optimal solution 
to your linear problem. In the context of ECLiPSe, we do not implement 
our own Simplex solver, but instead we interface to external 
Mathematical Programming solvers (via lib(eplex)), of which the Simplex 
method is the most common linear solving method. Within this context, 
the reduced costs are automatically used by the solver, and the user 
does not need to do anything explicitly with the reduced cost.

You do not mention which solving technique you are using to solve your 
time-tabling problem, nor why you don't obtain the optimal. I will 
assume from the context that you are solving the problem using a 
constraint solver over finite (integer) domain (e.g. lib(ic)), and this 
is insufficient to find the optimal solution in a reasonable amount of 
time, and so you are thinking that you might be able to use hybrid 
technique (in this case combining a finite domain solver with a linear 
MP solver) to solve your problem more efficiently.

Using hybrid techniques to solve problems is an active research area, 
and it is beyond the scope of a posting to describe hybrid solving (nor 
am I the best person to do so in any case, as I am not directly involved 
in this research), but I think I can say there is currently no 
pre-packaged "best" way of using hybrid technique to solve general 
problems, but you need to write your own code to do so. Reduced cost is 
one possible source of information generated by a Simplex solver that 
you can then make use of in a hybrid solving, but I don't think there is 
a single correct way of using this information, and reduced cost is not 
the only information you can use, either.

The literature section of the ECLiPSe website 
(http://www.eclipseclp.org/reports/index.html) provides some links to 
papers, books, and other materials, some of which are related to hybrid 
techniques. In particular, the course on Hybrid Algorithms given by Mark 
Wallace at the Constraint Programming Summer School 2005 specifically 
mentions reduced cost. These links might provide some better guide to 
how to use hybrid techniques.

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.