Conference Publication Details
Mandatory Fields
Yuri Malitsky, Deepak Mehta, Barry O'Sullivan, Helmut Simonis
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013
Tuning Parameters of Large Neighborhood Search for the Machine Reassignment Problem.
Scopus: 14 ()
Optional Fields
Carla P. Gomes and Meinholf Sellman
Data centers are a critical and ubiquitous resource for providing infrastructure for banking, Internet and electronic commerce. One way of managing the data centers efficiently is to minimize a cost function that takes into account the load of the machines, the balance among a set of available resources of the machines, and the costs of moving processes while respecting a set of constraints. This problem is called machine reassignment problem. An instance of this online problem can have several tens of thousands of processes. Therefore, the challenge is to solve a very large size instance in a very limited time. In this paper, we describe a constraint programming based Large Neighborhood Search (LNS) approach for solving this problem. The values of the parameters of LNS can have a significant impact on the performance of LNS when solving an instance. We, therefore, employ the Instance Specific Algorithm Configuration methodology, where a clustering of the instances is maintained in the offline phase and the parameters of LNS are automatically tuned for each cluster. When a new instance arrives the values of the parameters of the closest cluster are used for solving the instance in the online phase. Results con firm that our CP-based LNS approach with high quality parameter settings finds good quality solutions for very large size instances in very limited time. Our results also significantly outperform the hand-tuned settings of the parameters selected by a human expert.
Grant Details