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

[Guido Tack]

Hi,

there’s nothing wrong with your model, it’s just that it falls into a subclass of problems (linear assignment problems) that is absolutely perfect for linear solvers and quite bad for CP solvers.  Unless you have other side constraints that would make it difficult for a linear or MIP solver to find feasible solutions, a MIP will always be many orders of magnitude faster than a CP solver on this problem class.

Cheers,
Guido

-- 
GUIDO TACK                  
Senior Lecturer

Information Technology
Monash University
Level 6, Room 6.40, Building H, Caulfield Campus
900 Dandenong Road
Caulfield East VIC 3145
Australia

T: +61 3 9903 1214                      
E: guido.tack at monash.edu <mailto:guido.tack at monash.edu>
http://www.csse.monash.edu/~guidot/ <http://www.csse.monash.edu/~guidot/>


> On 4 Apr 2016, at 6:18 AM, Florent Teichteil <florent.teichteil at gmail.com> wrote:
> 
> 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 at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20160404/788ff0e1/attachment.html>