CP for Facility Location Problem?

[Qiang Gao]

Hi,

I'm working on a large scale Capacity Facility Location Problem (2000 customers and 300 facilities), where each facility can only serve customers within its radius (like 5KM). Facility has lower bound and upper bound of the capacity. Not all the customers must be served. 

The model looks like this:

-------------------------------------------- 

var x[Customers * Depots] binary;

var open[Depots] binary;

var cover[Customers] binary;

minimize SUM_COST:

(sum <depot> in Depots: open[depot]) + 

NbCustomers - sum<customer> in Customers: cover[customer] + 

(sum <customer, depot> in Customers * Depots: x[customer, depot] * disMat[customer, depot] * demand[customer])/(sum<customer> in Customers: demand[customer]) ;

subto COVER:

forall <customer> in Customers do

sum<depot> in Depots: x[customer, depot] == 1 * cover[customer];

    

subto RADIUS:

forall <customer, depot> in Customers * Depots do

     x[customer, depot] * disMat[customer, depot] <= open[depot] * 5;

    

subto LB:

forall <depot> in Depots do

     sum<customer> in Customers: x[customer, depot] * demand[customer] >= 80 * open[depot];

  

subto UB:

forall <depot> in Depots do

     sum<customer> in Customers: x[customer, depot] * demand[customer] <= 1200 * open[depot];

-------------------------------------------- 

I managed to model it in 0-1 Integer Programming and solved with SCIP solver within 10 minutes. 

I was wondering if I could model the problem with the help of CP and Local Search built in Or-tools to get an approximated solution? 

I've read some examples and documents in Or-tools but didn't know if CP is a good option and how to set its decision builder correctly.

Thanks.

Qiang GAO

[Laurent Perron]

Hi, 

First I would try replacing SCIP_MIXED_INTEGER_PROGRAMMING with BOP_INTEGER_PROGRAMMING to see if it improves.

Now CP could be good. The closest example would be examples/cpp/dobble_ls.cc.

The downside is that I think you will need to code in C++ as you will need to create custom moves and filters.

I hope this helps.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Antonio Medrano]

Did you model this as a capacitated maximum cover location problem (MCLP) in SCIP?

[Qiang Gao]

Hi, Antonio

I didn't know it has a exact name. This could help me finding some papers. Thanks.

在 2016年11月1日星期二 UTC+8上午6:39:33，Antonio Medrano写道：