Restart strategies with NoGoods in the MiniCP constraint programming solver

Details

Supervisors

Deville, Yves

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en informatique, à finalité spécialisée

Abstract

Restart strategies are meta-heuristics used in Constraint Programming to avoid heavy-tailed behaviors encountered by systematic searches. In doing so, they may reexplore certain areas of the search tree, which could decrease efficiency. A solution to this problem is to incorporate learning with the help of nogoods, which are sequences of decisions leading to previously visited regions. Their management guides the later part of the search towards unexplored areas of the search space. The goal of this thesis is to integrate an efficient base, storing nogoods, in the MiniCP constraint programming solver and then to study their impact when used on a regular restart strategy and a large neighborhood search. Along the implementation, the nogood base was also extended to support an additional type of decision. Experimental results have shown that nogoods can improve the performances of a regular restart strategy and worsen the performances of a large neighborhood search.