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

From: Kish Shen <kisshen_at_...5...>
Date: Tue, 27 Dec 2011 09:48:49 +0000
```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
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
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