Hi all,
I am wondering if I use Gecode the right way since I get poor performances
on a simple optimal allocation problem. The B&B search algorithm keeps
improving the cost but without ever converging (even after several minutes)
while the same problem is solved in less than 100ms with the CBC solver
from COIN. I must say that I am more comfortable with operation research
algorithms than with CP ones, so it is possible that I misuse Gecode.
The problem consists in assigning objects in A to objects in B so as to
maximize the overall revenue.
Allocations are optional, i.e. a given object in B does not need to have an
assigned object from A if it decreases the overall revenue.
By abusing the notation I represent A and B as positive integers and the
corresponding object sets as {0,...,A-1} and {0,...,B-1}
ILP model:
* Decision variables: x(a,b) in {0,1} for each a in {0,...,A-1} and b in
{0,...,B-1}
* R(a,b)=floor(A*B*cos(2*PI*a*b/A*B)) is the revenue of the allocation
pair (a,b)
* max sum_{a in {0,...,A-1}, b in {0,...,B-1}} x(a,b) * R(a,b)
* for each a in {0,...,A-1}: sum(b in {0,...,B-1}) x(a,b) <= 1
* for each b in {0,...,B-1}: sum(a in {0,...,A-1}) x(a,b) <= 1
CP model:
* Decision variables:
- x(b) in {0,...,A} for each b in {0,...,B-1}; x(b)=A when no object
from A is assigned to b
- y(b) = R(x(b),b) in {0,...} if x(b) != A else 0, for each b in
{0,...,B-1}
* with R(a,b)=floor(A*B*cos(2*PI*a*b/A*B)) is the revenue of the
allocation pair (a,b)
* max sum_{b in {0,...,B-1}} y(b)
* for each b in {0,...,B-1}: y(b) = floor(A*B*cos(2*PI*x(b)*b/A*B)) if
x(b) != A else 0
* alldistinct(x)
* branching with: branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
In my test I use A=200 and B=100.
The ILP CBC solver can even solve the problem with A=2000 and B=1000 like a
charm.
Note that the number of variables in the ILP model is much larger than in
the CP model.
I tried also to use Gecode with the ILP model but the performances are poor
too.
Why can't Gecode solve this simple problem? Did I make something wrong?
Are MILP solvers much better than CP ones for such optimization problems?
The entire code is given below.
Many thanks in advance!
Florent
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
using namespace Gecode;
class Allocation : public MaximizeScript {
protected:
static const int A = 200;
static const int B = 100;
IntVarArray x;
IntVarArray y;
IntVar total_reward;
public:
Allocation(const SizeOptions& opt)
: MaximizeScript(opt),
x(*this, B, 0, A),
y(*this, B, Int::Limits::min, Int::Limits::max),
total_reward(*this, Int::Limits::min, Int::Limits::max) {
IntArgs rewards((A+1)*B);
double PI = std::acos(-1.0);
for (unsigned int b = 0 ; b < B ; b++) {
for (unsigned int a = 0 ; a < A ; a++) {
rewards[a + b * (A+1)] =
static_cast<int>(std::floor(A*B*std::cos(2*PI*((double) a*b)/((double)
A*B))));
if (rewards[a + b * (A+1)] < 0.0) {
rel(*this, x[b] != a);
}
}
rewards[A*(b+1) + b] = 0.0;
}
IntSharedArray sc(rewards);
for (unsigned int b = 0 ; b < B ; b++) {
rel(*this, y[b] == element(sc, x[b] + b * (A+1)));
}
distinct(*this, x);
rel(*this, total_reward == sum(y));
branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
// branch(*this, x, INT_VAR_DEGREE_MIN(), INT_VAL_MIN());
}
virtual void print(std::ostream& os) const {
os << "total_reward: " << total_reward << std::endl;
for(int b = 0; b < B; b++) {
os << x[b] << " ";
}
os << std::endl;
}
virtual IntVar cost(void) const {
return total_reward;
}
Allocation(bool share, Allocation& s)
: MaximizeScript(share,s) {
x.update(*this, share, s.x);
y.update(*this, share, s.y);
total_reward.update(*this, share, s.total_reward);
}
virtual Space* copy(bool share) {
return new Allocation(share,*this);
}
};
int main(int argc, char* argv[]) {
SizeOptions opt("Allocation");
opt.solutions(0);
opt.iterations(20000);
opt.parse(argc,argv);
MaximizeScript::run<Allocation,BAB,SizeOptions>(opt);
return 0;
}
_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
