# Constrained assignment problem (Linear Programming, Genetic Algorithm, etc...)

I'm looking for advice on how I should approach a specific problem. I have about 1000 shops that I have to assign to about 20 different supply centers out of a possible 28, and I'm trying to pick the best 20 (or less) centers that minimizes the overall distance between shops and supply centers.

I looked into the 'assignment problem' and how linear programming could help, but it seems this can only work if I have an equal number of shops and centers. I also looked into Genetic Algorithms and tried to code the algorithm to 1) ensure each shop is assigned to only one center and the center count must be no greater than 20, but results aren't that great (I can provide my R code if requested)

Should I continue trying to work with a Genetic Algorithm or can you folks suggest some other tool I should use or resource to look over? Thank you.

EDIT: Some nice user who's comment is now deleted suggested researching the Facility Location Problem. This seems more in line with what I'm looking for but most of the examples online cover single-facility problems, not multi-facility problems. Can anyone recommend a good resource for R or Python?

EDIT: Apparently, I should have posted my original recommendation about the facility location problem as a reply to your question, not as an answer. I am new to the forum, but I get it now.

Any way, I believe your problem can be formulated as follows.

Let $y_i$ = 1 if supply center i is opened and 0 otherwise

$x_i,_j$ = 1 if supply center i feeds shop j and 0 otherwise

$c_i,_j$ = distance from supply center i to shop j

Then you want to solve the following linear programming problem.

minimize  $\sum_i\sum_jc_i,_jx_i,_j$

subject to $\sum_ix_i,_j = 1$                j = 1,...,1000 (or the number of shops you have)

$\sum_jx_i,_j \le 1000y_i$      i = 1,...,28 (If you have a max capacity for each supply center, use that number instead of 1000; 1000 assumes there is no max capacity so one center could feasibly supply all shops)

$\sum_iy_i \le 20$                 (max of 20 supply centers chosen)

$x_i,_j$ = 0 or 1                  i=1,...,28; j =1,...,1000

$y_i$ = 0 or 1                     i=1,...,14

The Rsymphony package in R can solve this problem for you. You will need a vector of the distances $c_i,_j$ and 0's for each $y_i$ as well as a matrix to take care of the constraints (the three summations starting after "subject to"). If you aren't familiar with the constraint matrix, each column contains the coefficients for that variable. The help file for the Rsymphony package has a couple examples that should help with that. Don't forget to include columns for the $y_i$ in the matrix as well. You will also need to set the $x_i,_j$ and $y_i$ to be binary by using

types = "B"

As an example, suppose we have 3 shops and 2 supply centers with distances between them as $x_1,_1$ = 2.8, $x_1,_2$ = 5.4, $x_1,_3$ = 1.4, $x_2,_1$ = 4.2, $x_2,_2$ = 3.0, $x_2,_3$ = 6.3. Then

    library(Rsymphony)
obj <- c(2.8, 5.4, 1.4, 4.2, 3.0, 6.3, 0, 0)
mat <- matrix(c(1,0,0,1,0,0,0,1,0,1,0,0,0,0,1,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,0,0,-3,0,1,0,0,0,0,-3,1), nrow = 6)
dir <- c("==", "==", "==", "<=", "<=", "<=")
rhs <- c(1, 1, 1, 0, 0, 2)
max <- FALSE
types <- "B"
fac.loc <- Rsymphony_solve_LP(obj, mat, dir, rhs, types = types, max = max, write_lp = TRUE)
fac.loc


tells us that we should open both supply centers and supply center 1 will supply shops 1 and 3 and supply center 2 will supply shop 2, for a total distance of 7.2.

I hope this helps.

• Actually, this is a very direct answer to the question that suggests the use of the RSymphony package for integer linear programming to solve the problem. These types of integer programming problems are actually quite easy to solve exactly, so there's no need to use an heuristic approach such as genetic algorithms. Feb 7, 2015 at 21:30
• @TAS thanks! Sorry for the late reply but I think this is exactly what I'm looking for! I'm going to test it out on my own data set and let you guys know soon. Feb 11, 2015 at 15:12
• Glad to hear. I think the most difficult part will be coming up with your constraint matrix.
– TAS
Feb 11, 2015 at 18:24
• @TAS Thanks a freaking million dude! It worked, and building the constraint matrix wasn't that hard once I took your example constraint matrix and broke it into different 'blocks' then binded them all together! Feb 12, 2015 at 18:21