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 条

[1] SCIP: solving constraint integer programs [J].

Achterberg, Tobias .

MATHEMATICAL PROGRAMMING COMPUTATION, 2009, 1 (01) :1-41

[2]

Akgun O, 2013, LECT NOTES COMPUT SC, V8124, P107, DOI 10.1007/978-3-642-40627-0_11

[3] SUNNY: a Lazy Portfolio Approach for Constraint Solving [J].

Amadini, Roberto ;

Gabbrielli, Maurizio ;

Mauro, Jacopo .

THEORY AND PRACTICE OF LOGIC PROGRAMMING, 2014, 14 :509-524

[4]

[Anonymous], 1972, Complexity of Computer Computations, DOI [10.1007/978-3-540-68279-0-8, DOI 10.1007/978-1-4684-2001-2]

[5] Global constraint catalogue: Past, present and future [J].

Beldiceanu, Nicolas ;

Carlsson, Mats ;

Demassey, Sophie ;

Petit, Thierry .

CONSTRAINTS, 2007, 12 (01) :21-62

[6] LocalSolver 1.x: a black-box local-search solver for 0-1 programming [J].

Benoist, Thierry ;

Estellon, Bertrand ;

Gardi, Frederic ;

Megel, Romain ;

Nouioua, Karim .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2011, 9 (03) :299-316

[7]

Bjordal G., 2014, THESIS UPPSALA U SWE

[8]

Bofill M., FZN2SMT COMPILER FLA

[9]

Codognet Philippe., 2001, SAGA 01, P73

[10]

De Landtsheer R., 2012, OSCAR CBLS CONSTRAIN

← 1 2 3 4 5 →