main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 14 2013 20:59:22 for Gecode by
doxygen
1.8.3.1
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: 2011-06-21 06:39:54 +1000 (Tue, 21 Jun 2011) $ by $Author: schulte $
11
* $Revision: 12069 $
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
branch
(*
this
, xy,
INT_VAR_SIZE_AFC_MIN
,
INT_VAL_MIN
);
95
}
96
98
Partition
(
bool
share,
Partition
& s) :
Script
(share,s) {
99
x.update(*
this
, share, s.
x
);
100
y.update(*
this
, share, s.
y
);
101
}
103
virtual
Space
*
104
copy
(
bool
share) {
105
return
new
Partition
(share,*
this
);
106
}
108
virtual
void
109
print
(std::ostream& os)
const
{
110
os <<
"\t"
;
111
int
a
,
b
;
112
a = b = 0;
113
for
(
int
i
= 0;
i
< x.
size
();
i
++) {
114
a += x[
i
].val();
115
b += x[
i
].val()*x[
i
].val();
116
os << x[
i
] <<
", "
;
117
}
118
os <<
" = "
<< a <<
", "
<< b << std::endl <<
"\t"
;
119
a = b = 0;
120
for
(
int
i
= 0;
i
< y.
size
();
i
++) {
121
a += y[
i
].val();
122
b += y[
i
].val()*y[
i
].val();
123
os << y[
i
] <<
", "
;
124
}
125
os <<
" = "
<< a <<
", "
<< b << std::endl;
126
}
127
};
128
133
int
134
main
(
int
argc,
char
* argv[]) {
135
SizeOptions
opt
(
"Partition"
);
136
opt.
size
(32);
137
opt.
icl
(
ICL_BND
);
138
opt.
parse
(argc,argv);
139
Script::run<Partition,DFS,SizeOptions>(
opt
);
140
return
0;
141
}
142
143
144
// STATISTICS: example-any
145