The significance of infeasibility for a Capacitated Facility Location Problem

Question

I am modelling a capacitated facility location problem in R with the ompr package.

When I am removing the Capacity constraint, the model is giving me results. But when the constraint is added, it is showing infeasibility. I am trying to understand the implications of this result.

The cumulative capacity of the potential locations is more than the demand. So, there should be feasibility in the solution, right? I would expect more Facility locations than the Uncapacitated Solution and probably a higher solution cost. But why would there be infeasibility?

The code if anyone needs a reference:

model <- MIPModel() %>%
  # 1 if pin i gets assigned to warehouse j
  add_variable(x[i, j], i = 1:n, j = 1:m, type = "binary") %>%
  
  # 1 if warehouse j is built
  add_variable(y[j], j = 1:m, type = "binary") %>%
  
  # Objective function
  set_objective(sum_expr(transportcost_matrix[i, j] * x[i, j], i = 1:n, j = 1:m) +
                  sum_expr(fixedcost * y[j], j = 1:m) +
                  sum_expr((demand[i] * x[i, j])* rent_per_sqft[j], i = 1:n, j = 1:m), "min") %>%
  
  # Every pin needs to be assigned to a warehouse
  add_constraint(sum_expr(x[i, j], j = 1:m) == 1, i = 1:n) %>% 
  
  # If a pin is assigned to a warehouse, then the warehouse must be built
  add_constraint(x[i,j] <= y[j], i = 1:n, j = 1:m) %>%
  
  #The demand of each warehouse shouldn't exceed their capacities
  add_constraint(sum_expr(demand[i] * x[i, j], i = 1:n) <= capacity[j] * y[j], j = 1:m)

Answer 1

I think what you have faced with infeasibility came from the problem data. I tried to run the problem with the formulation you mentioned by some of the random data and the problem is being solved without any issues. The data I have used is:

parameter transportcost_matrix(i,j); transportcost_matrix(i,j)= uniform(150,300);
parameter fixedcost(j); fixedcost(j)= uniform(100,200);
parameter demand(i); demand(i)= uniform(500,900);
parameter rent_per_sqft(j); rent_per_sqft(j)= uniform(500,700);
parameter capacity(j); capacity(j)= uniform(1500,3000);

Please, noted that this data is produced based on a uniform distribution function, but you may use your favorite function.

Answer 2

Given that your problem has binary assignment variables (the &$x_{ij}$ variables) it is not a capacitated facility location problem (CFLP) , it is a single source CFLP (SSCFLP). The decision problem "does the SSCFLP have a feasible solution" is NP-complete, and hence it is not enough to look at the cumulative capacity to check feasibility.

Take for instance the problem with three customers having a demand of two units each and two potential facilities with a capacity of three units each. There is a total capacity of six units, a total demand of six units, and no single source solution.