this repo has no description
dekker.one
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, 2006
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36#include <gecode/minimodel.hh>
37
38#include <cstdlib>
39
40using namespace Gecode;
41
42/**
43 * \brief %Example: All-interval series
44 *
45 * An all-interval series of length \f$n\f$ is a sequence
46 * \f[
47 * (x_0,x_1,\ldots,x_{n-1})
48 * \f]
49 * where each \f$x_i\f$ is an integer between \f$0\f$ and \f$n-1\f$
50 * such that the following conditions hold:
51 * - the \f$x_i\f$ are a permutation of \f$\{0,1,\ldots,n-1\}\f$
52 * (that is, they are pairwise distinct and take values from
53 * \f$\{0,1,\ldots,n-1\}\f$).
54 * - the differences between adjacent values \f$(d_1,d_2,\ldots,d_{n-1})\f$
55 * with \f$d_i=\operatorname{abs}(x_i-x_{i-1})\f$ form a permutation of
56 * \f$\{1,2,\ldots,n-1\}\f$.
57 *
58 * See also problem 7 at http://www.csplib.org/.
59 *
60 * \ingroup Example
61 */
62class AllInterval : public Script {
63private:
64 /// The numbers
65 IntVarArray x;
66 /// The differences
67 IntVarArray d;
68public:
69 /// Actual model
70 AllInterval(const SizeOptions& opt) :
71 Script(opt),
72 x(*this, opt.size(), 0, opt.size()-1),
73 d(*this, opt.size()-1, 1, opt.size()-1) {
74 const int n = x.size();
75
76 // Set up variables for distance
77 for (int i=0; i<n-1; i++)
78 rel(*this, d[i] == abs(x[i+1]-x[i]), opt.ipl());
79
80 distinct(*this, x, opt.ipl());
81 distinct(*this, d, opt.ipl());
82
83 // Break mirror symmetry
84 rel(*this, x[0], IRT_LE, x[1]);
85 // Break symmetry of dual solution
86 rel(*this, d[0], IRT_GR, d[n-2]);
87
88 branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
89 }
90 /// Constructor for cloning \a e
91 AllInterval(AllInterval& s)
92 : Script(s) {
93 x.update(*this, s.x);
94 d.update(*this, s.d);
95 }
96 /// Copy during cloning
97 virtual Space*
98 copy(void) {
99 return new AllInterval(*this);
100 }
101 /// Print solution
102 virtual void
103 print(std::ostream& os) const {
104 const int n = x.size();
105 os << "\tx[" << n << "] = {";
106 for (int i = 0; i < n-1; i++)
107 os << x[i] << "(" << d[i] << "),";
108 os << x[n-1] << "}" << std::endl;
109 }
110};
111
112
113/** \brief Main-function
114 * \relates AllInterval
115 */
116int
117main(int argc, char* argv[]){
118 SizeOptions opt("AllInterval");
119 opt.size(1000);
120 opt.iterations(5);
121 opt.ipl(IPL_BND);
122 opt.parse(argc, argv);
123 if (opt.size() < 2) {
124 std::cerr << "size must be at least 2!" << std::endl;
125 return -1;
126 }
127 Script::run<AllInterval,DFS,SizeOptions>(opt);
128 return 0;
129}
130
131// STATISTICS: example-any
132