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.t...@monash.edu <mailto:guido.t...@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.teicht...@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@gecode.org > https://www.gecode.org/mailman/listinfo/gecode-users
_______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
