main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:48:59 for Gecode by
doxygen
1.8.4
examples
partition.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, 2003
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
using namespace
Gecode;
43
49
class
Partition
:
public
Script
{
50
protected
:
52
IntVarArray
x
;
54
IntVarArray
y
;
55
public
:
57
Partition
(
const
SizeOptions
&
opt
)
58
:
x
(*this,opt.
size
(),1,2*opt.
size
()),
59
y(*this,opt.
size
(),1,2*opt.
size
()) {
60
const
int
n
= opt.
size
();
61
62
// Break symmetries by ordering numbers in each group
63
rel
(*
this
,
x
,
IRT_LE
);
64
rel
(*
this
, y,
IRT_LE
);
65
66
rel
(*
this
,
x
[0],
IRT_LE
, y[0]);
67
68
IntVarArgs
xy(2*n);
69
for
(
int
i
= n;
i
--; ) {
70
xy[
i
] =
x
[
i
]; xy[n+
i
] = y[
i
];
71
}
72
distinct
(*
this
, xy, opt.
icl
());
73
74
IntArgs
c
(2*n);
75
for
(
int
i
= n;
i
--; ) {
76
c[
i
] = 1; c[n+
i
] = -1;
77
}
78
linear
(*
this
, c, xy,
IRT_EQ
, 0);
79
80
// Array of products
81
IntVarArgs
sxy(2*n), sx(n), sy(n);
82
83
for
(
int
i
= n;
i
--; ) {
84
sx[
i
] = sxy[
i
] =
expr
(*
this
,
sqr
(
x
[
i
]));
85
sy[
i
] = sxy[n+
i
] =
expr
(*
this
,
sqr
(y[i]));
86
}
87
linear
(*
this
, c, sxy,
IRT_EQ
, 0);
88
89
// Redundant constraints
90
linear
(*
this
,
x
,
IRT_EQ
, 2*n*(2*n+1)/4);
91
linear
(*
this
, y,
IRT_EQ
, 2*n*(2*n+1)/4);
92
linear
(*
this
, sx,
IRT_EQ
, 2*n*(2*n+1)*(4*n+1)/12);
93
linear
(*
this
, sy,
IRT_EQ
, 2*n*(2*n+1)*(4*n+1)/12);
94
95
branch
(*
this
, xy,
INT_VAR_AFC_SIZE_MAX
(opt.
decay
()),
INT_VAL_MIN
());
96
}
97
99
Partition
(
bool
share,
Partition
& s) :
Script
(share,s) {
100
x
.update(*
this
, share, s.
x
);
101
y.update(*
this
, share, s.
y
);
102
}
104
virtual
Space
*
105
copy
(
bool
share) {
106
return
new
Partition
(share,*
this
);
107
}
109
virtual
void
110
print
(std::ostream& os)
const
{
111
os <<
"\t"
;
112
int
a
,
b
;
113
a = b = 0;
114
for
(
int
i
= 0;
i
<
x
.size();
i
++) {
115
a +=
x
[
i
].val();
116
b +=
x
[
i
].val()*
x
[
i
].val();
117
os <<
x
[
i
] <<
", "
;
118
}
119
os <<
" = "
<< a <<
", "
<< b << std::endl <<
"\t"
;
120
a = b = 0;
121
for
(
int
i
= 0;
i
< y.
size
();
i
++) {
122
a += y[
i
].val();
123
b += y[
i
].val()*y[
i
].val();
124
os << y[
i
] <<
", "
;
125
}
126
os <<
" = "
<< a <<
", "
<< b << std::endl;
127
}
128
};
129
134
int
135
main
(
int
argc,
char
* argv[]) {
136
SizeOptions
opt
(
"Partition"
);
137
opt.
size
(32);
138
opt.
icl
(
ICL_BND
);
139
opt.
parse
(argc,argv);
140
Script::run<Partition,DFS,SizeOptions>(
opt
);
141
return
0;
142
}
143
144
145
// STATISTICS: example-any
146