main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:24 for Gecode by
doxygen
1.8.4
examples
golomb-ruler.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Christian Schulte <schulte@gecode.org>
5
*
6
* Copyright:
7
* Christian Schulte, 2001
8
*
9
* Last modified:
10
* $Date: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
11
* $Revision: 13820 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
#include <
gecode/driver.hh
>
39
#include <
gecode/int.hh
>
40
#include <
gecode/minimodel.hh
>
41
42
#include <iomanip>
43
44
using namespace
Gecode;
45
66
class
GolombRuler
:
public
IntMinimizeScript
{
67
protected
:
69
IntVarArray
m
;
70
public
:
72
GolombRuler
(
const
SizeOptions
&
opt
)
73
: m(*this,opt.
size
(),0,
74
(opt.
size
() < 31) ? (1 << (opt.
size
()-1))-1 : Int::Limits::
max
) {
75
76
// Assume first mark to be zero
77
rel
(*
this
, m[0],
IRT_EQ
, 0);
78
79
// Order marks
80
rel
(*
this
, m,
IRT_LE
);
81
82
// Number of marks and differences
83
const
int
n
= m.size();
84
const
int
n_d = (n*n-
n
)/2;
85
86
// Array of differences
87
IntVarArgs
d
(n_d);
88
89
// Setup difference constraints
90
for
(
int
k=0,
i
=0;
i
<n-1;
i
++)
91
for
(
int
j=
i
+1; j<
n
; j++, k++)
92
// d[k] is m[j]-m[i] and must be at least sum of first j-i integers
93
rel
(*
this
, d[k] =
expr
(*
this
, m[j]-m[
i
]),
94
IRT_GQ
, (j-i)*(j-i+1)/2);
95
96
distinct
(*
this
, d, opt.
icl
());
97
98
// Symmetry breaking
99
if
(n > 2)
100
rel
(*
this
, d[0],
IRT_LE
, d[n_d-1]);
101
102
branch
(*
this
, m,
INT_VAR_NONE
(),
INT_VAL_MIN
());
103
}
104
106
virtual
IntVar
cost
(
void
)
const
{
107
return
m[m.size()-1];
108
}
109
111
virtual
void
112
print
(std::ostream& os)
const
{
113
os <<
"\tm["
<< m.size() <<
"] = "
<< m << std::endl;
114
}
115
117
GolombRuler
(
bool
share,
GolombRuler
& s)
118
:
IntMinimizeScript
(share,s) {
119
m.update(*
this
, share, s.
m
);
120
}
122
virtual
Space
*
123
copy
(
bool
share) {
124
return
new
GolombRuler
(share,*
this
);
125
}
126
};
127
131
int
132
main
(
int
argc,
char
* argv[]) {
133
SizeOptions
opt
(
"GolombRuler"
);
134
opt.
solutions
(0);
135
opt.
size
(10);
136
opt.
icl
(
ICL_BND
);
137
opt.
parse
(argc,argv);
138
if
(opt.
size
() > 0)
139
IntMinimizeScript::run<GolombRuler,BAB,SizeOptions>(opt);
140
return
0;
141
}
142
143
// STATISTICS: example-any
144