Generated on for Gecode by doxygen 1.18.0
knapsack-overload.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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 <utility>
35
36namespace Gecode { namespace Int { namespace Cumulative {
37
38 // Knapsack-augmented overload checking
39 namespace Kaoc {
40
41 struct Bits {
42 unsigned long long low;
43 unsigned long long high;
44 };
45
46 forceinline void
47 add(Bits& bits, int demand, int capacity) {
48 unsigned long long shifted_low = 0ULL;
49 unsigned long long shifted_high = 0ULL;
50 if (demand < 64) {
51 shifted_low = bits.low << demand;
52 shifted_high = bits.high << demand;
53 if (demand != 0)
54 shifted_high |= bits.low >> (64-demand);
55 } else if (demand < 128) {
56 shifted_high = bits.low << (demand-64);
57 }
58 bits.low |= shifted_low;
59 bits.high |= shifted_high;
60 if (capacity < 63)
61 bits.low &= (1ULL << (capacity+1))-1ULL;
62 if (capacity < 64) {
63 bits.high = 0ULL;
64 } else if (capacity < 127) {
65 bits.high &= (1ULL << (capacity-63))-1ULL;
66 }
67 }
68
69 forceinline int
70 most_significant(unsigned long long word) {
71 assert(word != 0ULL);
72 int bit = 0;
73 if (word >> 32) { word >>= 32; bit += 32; }
74 if (word >> 16) { word >>= 16; bit += 16; }
75 if (word >> 8) { word >>= 8; bit += 8; }
76 if (word >> 4) { word >>= 4; bit += 4; }
77 if (word >> 2) { word >>= 2; bit += 2; }
78 if (word >> 1) { bit += 1; }
79 return bit;
80 }
81
82 forceinline unsigned long long
83 through(int bit) {
84 assert((bit >= 0) && (bit < 64));
85 return bit == 63 ? ~0ULL : (1ULL << (bit+1))-1ULL;
86 }
87
89 forceinline int
90 max_reachable(const Bits& bits, int residual) {
91 if (residual <= 0)
92 return 0;
93 residual = (std::min)(residual,127);
94 if (residual >= 64) {
95 const int high_bit = residual-64;
96 const unsigned long long high = bits.high & through(high_bit);
97 if (high != 0ULL)
98 return 64+most_significant(high);
99 }
100 const int low_bit = (std::min)(residual,63);
101 const unsigned long long low = bits.low & through(low_bit);
102 return low == 0ULL ? 0 : most_significant(low);
103 }
104
105 template<class Tasks>
106 bool
107 conflict(Tasks& tasks, int capacity) {
108 const int n = tasks.size();
109 if ((n < 4) || (n > 64) ||
110 (capacity < 2) || (capacity > 127))
111 return false;
112 bool non_unit = false;
113 for (int i=0; i<n; i++) {
114 // The earliest-start profile assumes a fixed processing time.
115 if ((static_cast<long long>(tasks[i].ect())-tasks[i].est()) !=
116 (static_cast<long long>(tasks[i].lct())-tasks[i].lst()))
117 return false;
118 if ((tasks[i].c() <= 0) || (tasks[i].c() > capacity))
119 return false;
120 non_unit = non_unit || (tasks[i].c() != 1);
121 }
122 if (!non_unit)
123 return false;
124
125 Region region;
126 int* order = region.alloc<int>(n);
127 int* times = region.alloc<int>(4*n);
128 for (int i=0; i<n; i++) {
129 order[i] = i;
130 times[4*i] = tasks[i].est();
131 times[4*i+1] = tasks[i].ect();
132 times[4*i+2] = tasks[i].lst();
133 times[4*i+3] = tasks[i].lct();
134 }
135 std::sort(order,order+n,[&](int left, int right) {
136 return std::make_pair(tasks[left].lct(),left) <
137 std::make_pair(tasks[right].lct(),right);
138 });
139 std::sort(times,times+4*n);
140 int events = 0;
141 for (int i=0; i<4*n; i++)
142 if ((events == 0) || (times[i] != times[events-1]))
143 times[events++] = times[i];
144 if (events < 2)
145 return false;
146
147 // Compulsory demand from all tasks, independent of the current prefix.
148 int* fixed = region.alloc<int>(events);
149 int* required = region.alloc<int>(events);
150 Bits* bits = region.alloc<Bits>(events);
151 for (int point=0; point<events; point++) {
152 fixed[point] = 0;
153 required[point] = 0;
154 bits[point].low = 1ULL;
155 bits[point].high = 0ULL;
156 for (int task=0; task<n; task++)
157 if ((tasks[task].lst() <= times[point]) &&
158 (times[point] < tasks[task].ect()))
159 fixed[point] += tasks[task].c();
160 if (fixed[point] > capacity)
161 return true;
162 }
163
164 // Extend the prefix in deadline order. At each event, bits contains
165 // reachable demands of prefix tasks outside their compulsory parts;
166 // required records their earliest-start demand outside those parts.
167 int earliest = tasks[order[0]].est();
168 for (int prefix=0; prefix<n; prefix++) {
169 const int task = order[prefix];
170 earliest = (std::min)(earliest,tasks[task].est());
171 for (int point=0; point<events; point++) {
172 const int time = times[point];
173 const bool compulsory =
174 (tasks[task].lst() <= time) && (time < tasks[task].ect());
175 if ((tasks[task].est() <= time) &&
176 (time < tasks[task].lct()) && !compulsory)
177 add(bits[point],tasks[task].c(),capacity);
178 if ((tasks[task].est() <= time) &&
179 (time < (std::min)(tasks[task].ect(),tasks[task].lst())))
180 required[point] += tasks[task].c();
181 }
182
183 const int finish = tasks[task].lct();
184 // Carry unserved energy forward to the deadline. Clipping at zero
185 // prevents earlier unused capacity from serving later demand.
186 long long overflow = 0;
187 for (int point=0; point+1<events; point++) {
188 const int left = times[point];
189 if ((left < earliest) || (left >= finish))
190 continue;
191 const int right = (std::min)(times[point+1],finish);
192 const int usable = max_reachable(bits[point],capacity-fixed[point]);
193 overflow = (std::max)(0LL,overflow+
194 (static_cast<long long>(right)-left) *
195 static_cast<long long>(required[point]-usable));
196 }
197 if (overflow > 0)
198 return true;
199 }
200 return false;
201 }
202
203 }
204
205 template<class Task>
206 forceinline ExecStatus
210
211 forceinline ExecStatus
215 forceinline ExecStatus
219 forceinline ExecStatus
223 forceinline ExecStatus
227
228}}}
229
230// STATISTICS: int-prop
Task array.
Definition task.hh:165
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Computation spaces.
Definition core.hpp:1787
bool conflict(Tasks &tasks, int capacity)
unsigned long long through(int bit)
int max_reachable(const Bits &bits, int residual)
Return the greatest reachable subset demand at most residual.
void add(Bits &bits, int demand, int capacity)
int most_significant(unsigned long long word)
Scheduling for cumulative resources
ExecStatus knapsack_overload(Space &, int, TaskArray< Task > &)
Perform knapsack-augmented overload checking.
ExecStatus supported_knapsack_overload(TaskArray< Task > &tasks, int capacity)
Finite domain integers.
Definition lastval.hh:52
Gecode toplevel namespace
void order(Home home, IntVar s0, int p0, IntVar s1, int p1, BoolVar b, IntPropLevel ipl=IPL_DEF)
Post propagators for ordering two tasks.
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
const int capacity[n_warehouses]
Capacity of a single warehouse.