Originally posted by: batmanzmc

Hi everybody,

I have a combinatorial minimization problem and CP optimizer can solve it in 5 seconds even when there are 2^400 feasible solutions. I don't know why CP optimizer runs so fast. I did not change any algorithm option so I guess it uses the default one.

Can anybody tell me what's the specific algorithm that CP optimizer uses to solve these kinds of problems ? The manual tells only very general concepts, for example 'constraint propagation', but I need to know in more detail.  

Thank you very much if you tell me your ideas about this.

Mengchen.

email: batmanzmc@gmail.com

Originally posted by: GGR

Hi

First of all CPO is oppositely to many constraint solver adapted to optimization rather than feasibility.

The three foundations of the optimization algorithm for integer problems in CPO are a large neighborhood search, restart and impact and strong learning techniques looking like Genetic Algorithms.

For more information please refer to

L. Perron, P. Shaw, V. Furnon. Propagation Guided Large Neighborhood Search. In Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming (CP 2004): 468-481, 2004.

Originally posted by: batmanzmc

Hi GGR,

Thank you very much for the reply. It's really useful for me.

One more question: CPO only returns the results together with some solving information (search speed, branches, etc). Can I know exactly which algorithm it uses when solving a specific problem? Because I may want to understand the algorithm and make some improvements. 

Best,

Mengchen 

Originally posted by: GGR

Hi

CPO does not give this information because the control of the different optimization procedures is based on learning and randomization. Moreover several thread may run different algorithm simultaneously. The mix is not comprehensive.

Eventually you can play with the mix of algorithm by modifying some parameters.

In practice you will implement the search algorithm in the cp engine by setting your own goal (instance of IloCPGoal. In such a case, the searh of CPO is disabled to avoid not understandable behavior. You can only compare your optimization method with the automatic one of CPO

Hope that helps

Originally posted by: batmanzmc

Thank you!

Originally posted by: SergeyPolyakovskiy

Hello Mengchen,

Which version of CPoptimizer are you using? Try to precisely set the searching method to Depth First (as only this one proves optimality as far as I know). Thus,

cp.setParameter(IloCP.IntParam.SearchType, IloCP.ParameterValues.DepthFirst);

Perhaps, you will get a different running time. Restart mode is set by default.

Originally posted by: PhilippeLaborie

Just a precision: the default search type (Restart) is complete (like DepthFirst), so it will also prove optimality. Note that if the problem involves interval variables (scheduling problem), the capability of the default Restart search to prove optimality has been improved quite a lot in version 12.6 and later versions thanks to the introduction of Failure-Directed Search [1]. In general, the default search type is expected to behave better than DepthFirst, both for producing good quality solutions and for proving optimality. Of course there may be some exceptions, for instance if you are solving some really small and easy problems.

[1] P. Vilím, P. Laborie, P. Shaw. Failure-Directed Search for Constraint-Based Scheduling. Proceedings CP-AI-OR 2015.

Philippe

Originally posted by: SergeyPolyakovskiy

Yes, Philippe. You are right. Sorry for confusion. I will a have pleasure to see the presentation of the paper at CPAIOR in a couple of days.

However, I wonder if the post holder faced the same problem I had before.

https://www.ibm.com/developerworks/community/forums/html/topic?id=044f5dc9-badb-481f-ad55-3007089dd687&ps=100