2
$\begingroup$

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)
$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Accepted the other answer as it was more specific to my data. Yours also made things clearer. +1. $\endgroup$ Mar 4 at 7:33
  • 1
    $\begingroup$ Thants fine. I think your comment pins the central thing here: it is specific for your data. Of course you can mingle the data, such that you end up with an easy special case, but that does not make it easier to solve general SSCLPs. $\endgroup$
    – Sune
    Mar 4 at 9:10
  • $\begingroup$ Yeap. Even after mingling my data, it will be hard to solve this SSCFLP. $\endgroup$ Mar 4 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.