کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4959013 1445465 2017 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration
چکیده انگلیسی
The definition of a “good” neighborhood structure on the solution space is a key step when designing several types of heuristics for Mixed Integer Programming (MIP). Typically, in order to achieve efficiency in the search, the neighborhood structures need to be tailored not only to the specific problem but also to the peculiar distribution of the instances to be solved (reference instance population). Nowadays, this is done by human experts through a time-consuming process comprising: (a) problem analysis, (b) literature scouting and (c) experimentation. In this paper, we illustrate an Automatic Neighborhood Design algorithm that mimics steps (a) and (c). Firstly, the procedure extracts some semantic features from a MIP compact model. Secondly, these features are used to derive automatically some neighborhood design mechanisms. Finally, the “proper mix” of such mechanisms is sought through an automatic configuration phase performed on a training set representative of the reference instance population. When assessed on four well-known combinatorial optimization problems, our automatically-generated neighborhoods outperform state-of-the-art model-based neighborhoods with respect to both scalability and solution quality.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 83, July 2017, Pages 106-119
نویسندگان
, , , , ,