[gecode-users] bin packing variant
Yilmaz Arslanoglu
yilmaz.arslanoglu at gmail.com
Thu Jun 1 10:19:01 CEST 2017
Hi;
I was trying to write a model for a bin packing variant.
(You can find the problem description at the bottom of this mail)
I'm quite new to Gecode so I couldn't get the whole logic behind it,
but below is my model which I based on the given directions in Gecode
documentation:
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/set.hh>
namespace {
using namespace Gecode;
const int rod_length[] = { 3, 2, 4, 5, 3 };
const int bin_weight_limit[] = { 30 };
const int bin_start[] = {0, 15};
inline int num_rods() {
return static_cast<int>(
sizeof(rod_length) / sizeof(int)
);
}
inline int num_bins() {
return static_cast<int>(
(sizeof(bin_weight_limit) / sizeof(int))
);
}
inline int box_start() {
return bin_start[0];
}
inline int box_end() {
return bin_start[num_bins()];
}
class Test : public Script {
public:
SetVarArray rod_position;
IntVarArray accum;
Test(const Options& opt)
: Script(opt)
, rod_position(*this,
num_rods(),
IntSet::empty,
IntSet(box_start(),
box_end()))
, accum(*this,
num_bins() * num_rods()) {
for (int i = 0; i < num_rods(); ++i) {
//
convex(*this, rod_position[i]);
//
cardinality(*this,
rod_position[i],
rod_length[i],
rod_length[i]);
}
Matrix<IntVarArray> accum_matrix(accum,
num_bins(),
num_rods());
for (int i = 0; i < num_bins(); ++i) {
//
auto bin_interval = IntSet(bin_start[i] + 1,
bin_start[i + 1]);
//
for (int j = 0; j < num_rods(); ++j) {
rel(*this,
accum_matrix(i, j) ==
cardinality(rod_position[j] & bin_interval));
}
//
rel(*this,
sum(accum_matrix.col(i)) <= bin_weight_limit[i]);
}
}
Test(bool share, Test& s)
: Script(share, s) {
rod_position.update(*this, share, s.rod_position);
accum.update(*this, share, s.accum);
}
virtual
Space* copy(bool share) {
return new Test(share, *this);
}
};
}
I get an exception in <gecode>/int.hpp at this location:
forceinline int
IntVarImp::RangeList::min(void) const {
return _min;
}
And here is my bin packing problem description (please check the image
attached):
I would like to place *N* rods (the red ones) into a rectangle which is
divided into *M* contiguous bins with different sizes. The rods can move
through bins. That is, they don't need to be completely covered by a single
bin, but can be hold by more than one bin.
My constraint is: for each bin, there is a specific weight capacity *W* and
total weight of rod pieces falling into that bin cannot exceed *W*.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20170601/6b876e35/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: packing_rods.png
Type: image/png
Size: 18132 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20170601/6b876e35/attachment-0001.png>
More information about the users
mailing list