From: Kish Shen <kisshen_at_cisco.com>

Date: Tue, 27 Dec 2011 09:48:49 +0000

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 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.Received on Tue Dec 27 2011 - 09:48:58 CET

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