A constraint-based local search backend for MiniZinc

被引：18

作者：

Bjordal, Gustav ^{[1
]}

Monette, Jean-Noel ^{[1
]}

Flener, Pierre ^{[1
]}

Pearson, Justin ^{[1
]}

机构：

[1] Uppsala Univ, Dept Informat Technol, S-75105 Uppsala, Sweden

来源：

CONSTRAINTS | 2015年 / 20卷 / 03期

基金：

瑞典研究理事会;

关键词：

Constraint-based local search; MiniZinc; ABSTRACTIONS;

D O I：

10.1007/s10601-015-9184-z

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

MiniZinc is a modelling language for combinatorial problems, which can then be solved by a solver provided in a backend. There are many backends, based on technologies such as constraint programming, integer programming, or Boolean satisfiability solving. However, to the best of our knowledge, there is currently no constraint-based local search (CBLS) backend. We discuss the challenges to develop such a backend and give an overview of the design of a CBLS backend for MiniZinc. Experimental results show that for some MiniZinc models, our CBLS backend, based on the OscaR/CBLS solver, is able to give good-quality results in competitive time.

引用

页码：325 / 345

页数：21

共 41 条

[21]

Hoos H. H., 2004, Stochastic local search: Foundations and applications

[22]

HOOS H. H., 2011, Autonomous search, P37, DOI DOI 10.1007/978-3-642-21434-9_3

[23] AEON: Synthesizing Scheduling Algorithms from High-Level Models [J].

Monette, Jean-Noel ;

Deville, Yves ;

Van Hentenryck, Pascal .

OPERATIONS RESEARCH AND CYBER-INFRASTRUCTURE, 2009, :43-+

[24]

Nethercote N., CONVERTING MINIZINC

[25]

Nethercote N, 2007, LECT NOTES COMPUT SC, V4741, P529

[26]

Newton M. A. Hakim, 2011, Principles and Practice of Constraint Programming - CP 2011. Proceedings of the 17th International Conference (CP 2011), P645, DOI 10.1007/978-3-642-23786-7_49

[27]

Nightingale P, 2014, LECT NOTES COMPUT SC, V8656, P590, DOI 10.1007/978-3-319-10428-7_43

[28] A fast taboo search algorithm for the job shop problem [J].

Nowicki, E ;

Smutnicki, C .

MANAGEMENT SCIENCE, 1996, 42 (06) :797-813

[29]

OR Team at Google, OR TOOLS

[30]

OscaR Team, 2012, OSCAR SCAL IN OR

← 1 2 3 4 5 →