forked from isse-augsburg/minibrass
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
196 lines (151 loc) · 8.95 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
<!DOCTYPE html>
<html>
<head>
<meta charset='utf-8'>
<meta http-equiv="X-UA-Compatible" content="chrome=1">
<meta name="description" content="Constraint Relationships : A utility library for constraint relationships on top of the MiniZinc/MiniSearch toolchain as well as native utils for JaCoP.">
<link rel="stylesheet" type="text/css" media="screen" href="stylesheets/stylesheet.css">
<title>Constraint Relationships</title>
</head>
<body>
<!-- HEADER -->
<div id="header_wrap" class="outer">
<header class="inner">
<a id="forkme_banner" href="https://github.com/isse-augsburg/constraint-relationships">View on GitHub</a>
<h1 id="project_title">Constraint Relationships</h1>
<h2 id="project_tagline">A utility library for constraint relationships on top of the MiniZinc/MiniSearch toolchain as well as native utils for JaCoP.</h2>
<section id="downloads">
<a class="zip_download_link" href="https://github.com/isse-augsburg/constraint-relationships/zipball/master">Download this project as a .zip file</a>
<a class="tar_download_link" href="https://github.com/isse-augsburg/constraint-relationships/tarball/master">Download this project as a tar.gz file</a>
</section>
</header>
</div>
<!-- MAIN CONTENT -->
<div id="main_content_wrap" class="outer">
<section id="main_content" class="inner">
<p><a href="http://www.isse.uni-augsburg.de/"><img src="images/isse.png" style = "width: 150px; height: auto;" alt="Constraint Relationships indicate priorities over constraints"></a></p>
<h1>
<a id="what-are-constraint-relationships-about" class="anchor" href="#what-are-constraint-relationships-about" aria-hidden="true"><span aria-hidden="true" class="octicon octicon-link"></span></a>Optimization with Preferences</h1>
<p><img src="images/cr-o.png" style="float: right; margin: 10px; " alt="Constraint Relationships indicate priorities over constraints"></p>
<p>Many combinatorial optimization problems are conveniently expressed using a constraint-based modeling language. They are then solved by powerful constraint programming or mathematical programming solvers.</p>
<p>We provide support for over-constrained problems or problems where desirable properties can be modeled as optional (soft) constraints. Importance is expressed only by means of relations between constraints (see <a href="http://www.isse.uni-augsburg.de/software/constraint-relationships/constraint-relationships.pdf">this 1 slide</a> to get an idea). Our library extensions are built on top of <a href="http://www.minizinc.org/">MiniZinc</a> that facilitates modeling combinatorial optimization problems for various solvers. The library includes:</p>
<ul>
<li>Convenient expression of soft constraint problems using constraint relationships</li>
<li>Automatic translation to weighted CSP</li>
<li>Generic search heuristics</li>
<li>Consistency checks of the specified relationships</li>
</ul>
<h2>
<a id="quick-example" class="anchor" href="#quick-example" aria-hidden="true"><span aria-hidden="true" class="octicon octicon-link"></span></a>Quick Example</h2>
<pre><code>% A really simplistic over-constrained model
% X: {x,y,z} D_i = {1,2,3}, i in X
% * c1: x + 1 = y
% * c2: z = y + 2
% * c3: x + y <= 3
% -------------------------------------------
% import libraries as bundle for a quick start
include "minisearch.mzn"; % include the search minisearch lite
include "soft_constraints/minisearch_bundle.mzn";
var 1..3: x;
var 1..3: y;
var 1..3: z;
% read as "soft constraint c1 is satisfied iff x + 1 = y"
constraint x + 1 = y <-> satisfied[1];
constraint z = y + 2 <-> satisfied[2];
constraint x + y <= 3 <-> satisfied[3];
% soft constraint data specific to this model
nScs = 3; % number of soft constraints
% Constraint Relationships:
% c1
% c2 c3
% -----------------------------------------
% three soft constraints c1, c2, c3
% c2 less imp than c1,
% c3 less imp than c1,
nCrEdges = 2;
crEdges = [| 2, 1 | 3, 1 |];
% uses a specific branch-and-bound search to perform optimization
solve
:: seq_search( [
% generic soft constraint search heuristic
int_search([satisfied[mostImpFirst[i]] | i in SOFTCONSTRAINTS],
input_order, indomain_max, complete),
% problem-specific heuristic
int_search([x,y,z], input_order, indomain_max, complete)] )
search time_limit(3000, strictlyBetterBAB(violatedScs)) /\
if hasSol() then print()
else print("No solution found\n") endif;
output ["Obj: \(penSum) by violating {\(violatedScs) } : " ++
" x -> \(x), y -> \(y), z -> \(z)"];
</code></pre>
<h2>
<a id="download-and-installation" class="anchor" href="#download-and-installation" aria-hidden="true"><span aria-hidden="true" class="octicon octicon-link"></span></a>Download and Installation</h2>
<h3>
<a id="quickest-start" class="anchor" href="#quickest-start" aria-hidden="true"><span aria-hidden="true" class="octicon octicon-link"></span></a>Quickest start:</h3>
<ol>
<li>Download and install the newest MiniZinc IDE version from <a href="http://www.minizinc.org/">http://www.minizinc.org/</a>
</li>
<li>Download <a href="http://www.isse.uni-augsburg.de/software/constraint-relationships/soft_constraints.zip">soft_constraints.zip</a> and unpack it</li>
<li>Locate the directory "./share/minizinc/std" of your MiniZinc installation</li>
<li>Copy the directory "soft_constraints" into "./share/minizinc/std"</li>
<li>Run the above code (smallexample_minizinc.mzn in <a href="http://www.isse.uni-augsburg.de/software/constraint-relationships/codeexamples.zip">codeexamples.zip</a>)</li>
</ol>
<h3>
<a id="slightly-slower-start" class="anchor" href="#slightly-slower-start" aria-hidden="true"><span aria-hidden="true" class="octicon octicon-link"></span></a>Slightly slower start:</h3>
<ol>
<li>Build MiniSearch according to the instructions at <a href="http://www.minizinc.org/minisearch/">MiniSearch</a>
</li>
<li>Download <a href="http://www.isse.uni-augsburg.de/software/constraint-relationships/soft_constraints.zip">soft_constraints.zip</a> and unpack it</li>
<li>Locate the directory "./share/minizinc/std" of your MiniSearch installation</li>
<li>Copy the directory "soft_constraints" into "./share/minizinc/std"</li>
<li>Run the above code (smallexample.mzn in <a href="http://www.isse.uni-augsburg.de/software/constraint-relationships/codeexamples.zip">codeexamples.zip</a>) to see custom search and variable ordering heuristics in action.</li>
</ol>
<h3>
<a id="after-starting" class="anchor" href="#after-starting" aria-hidden="true"><span aria-hidden="true" class="octicon octicon-link"></span></a>After starting:</h3>
<p>Have a look at these case studies to get a better idea. We will continously improve these pages, but for starters please refer to the slides.</p>
<ol>
<li><a href="http://www.isse.uni-augsburg.de/software/constraint-relationships/Case-Studies.zip">Case Studies</a></li>
<li><a href="images/step-by-step.zip"> Step-by-step conversion of a MiniZinc problem</a> </li>
<li>Language Features (coming soon)</li>
</ol>
<h2>
<a id="citing" class="anchor" href="#citing" aria-hidden="true"><span aria-hidden="true" class="octicon octicon-link"></span></a>Citing</h2>
<p>If you plan to use constraint relationships in your research, please consider citing </p>
<pre><code>
@INPROCEEDINGS{Schiendorfer13,
author = {Alexander Schiendorfer and
Jan-Philipp Steghöfer and
Alexander Knapp and
Florian Nafz and
Wolfgang Reif},
title = {{Constraint Relationships for Soft Constraints}},
editor = {Max Bramer and
Miltos Petridis},
booktitle = {Proc. 33\textsuperscript{rd} SGAI Int. Conf.
Innovative Techniques and Applications of Artificial Intelligence (AI'13)},
publisher = {Springer},
year = {2013},
pages = {241-255},
nolanguage = {English}
}
</code></pre>
<h2>
<a id="authors-and-contributors" class="anchor" href="#authors-and-contributors" aria-hidden="true"><span aria-hidden="true" class="octicon octicon-link"></span></a>Authors and Contributors</h2>
<ul>
<li>Alexander Schiendorfer (<a href="https://github.com/Alexander-Schiendorfer" class="user-mention">@Alexander-Schiendorfer</a>)</li>
<li>Alexander Knapp </li>
</ul>
<h2>
<a id="support-or-contact" class="anchor" href="#support-or-contact" aria-hidden="true"><span aria-hidden="true" class="octicon octicon-link"></span></a>Support or Contact</h2>
<p>For general information and support please contact <a href="https://github.com/Alexander-Schiendorfer" class="user-mention">@Alexander-Schiendorfer</a>. </p>
</section>
</div>
<!-- FOOTER -->
<div id="footer_wrap" class="outer">
<footer class="inner">
<p class="copyright">Constraint Relationships maintained by <a href="https://github.com/isse-augsburg">isse-augsburg</a></p>
<p>Published with <a href="https://pages.github.com">GitHub Pages</a></p>
</footer>
</div>
</body>
</html>