[gecode-users] Poor performance on simple allocation problem: did I make something wrong?

[Florent Teichteil]

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;
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20160403/1db018c8/attachment.html>