Using multi-point search algorithms

Multi-point search is based on a pool of points. This pool can be managed via parameters.

One search technique available in CP Optimizer is a multi-point search algorithm. This algorithm is based on a pool of search points. A search point is a collection of decision variable assignments that may lead to either feasible or partial solutions (a partial solution has some variables which are still not fixed). The multi-point method starts with an initial pool of search points whose candidate assignments are generated with constructive search. It then produces new search points by learning new variable assignments from search points maintained in the pool. On an optimization problem, the multi-point search method is able to learn from partial solutions in order to produce feasible solutions.

Multi-point search produces solutions by first performing variable assignments proposed by each of the generated search points. It then attempts to complete the solution by invoking a tree-search based completion procedure. If no feasible solution can be produced, a solution with a maximal number of instantiated decision variable is retained.

The completion procedure used is basically the same as the one used by the restart method. If you have specified search phases, the multi-point search completion procedure will use the search phases as well. In addition, phase priorities will be respected when interpreting search point assignments. That is, if you have specified phases A, B and C, then, for each search point, assignments involving variables of A will be performed at first, followed by those of phase B, ending with those of phase C.

The search parameter MultiPointNumberOfSearchPoints controls the number of (possibly partial) solutions manipulated by the multi-point search algorithm. The default value is 30. A larger value will diversify the search, with possible improvement in solution quality at the expense of a longer run time. A smaller value will intensify the search, resulting in faster convergence at the expense of solution quality. Note that memory consumption increases proportionally to this parameter, for each search point must store each decision variable domain.

To use multipoint search in the C++ API of CP Optimizer, you use the method IloCP::setParameter and the values IloCP::SearchType, IloCP::MultiPoint and IloCP::MultiPointNumberOfSearchPoints.

To use multipoint search in the Java™ API of CP Optimizer, you use the method IloCP.setParameter and the values IloCP.IntParam.SearchType, IloCP.ParamterValues.MultiPoint and IloCP.IntParam.MultiPointNumberOfSearchPoints.

To use multipoint search in the C# API of CP Optimizer, you use the method CP.SetParameter and the values CP.IntParam.SearchType, CP.ParamterValues.MultiPoint and CP.IntParam.MultiPointNumberOfSearchPoints.