I have formulated the below optimization problem.

\begin{align}\nonumber \hspace{-3mm}&\text{(P) minimize}\!\sum_{i}\!\alpha_{i}w_{i}\!+\!\sum_{i}\sum_{j}\!c_{ij} p_{ij}\!\\ \text{s.t.} & \sum_{i}\! p_{ij} = 1 , \forall(j) \in \mathcal{J}\\ & \sum_{j} d_j p_{ij} \leq b_i w_{i} , \forall(i) \in \mathcal{I}\\ & p_{ij} \in \{0,1\}, \forall(i) \in \mathcal{I},\forall(j) \in \mathcal{J}\\ & w_{i} \in \{0,1\}, \forall(i) \in \mathcal{I}\\ & q_{i} \in \{0,1\}, \forall(i) \in \mathcal{I} \end{align}

In $(P)$:

  • $w_i$ and $p_{ij}$, and $q_i$ are decision variable.
  • $\alpha_i,c_{ij},\beta_{i}$ are coefficients.

For the proof of being NP-complete, It is easy to show that problem in is NP. For the reduction part of the proof, I aimed to show that Capacitated Facility Location Problem is polynomially reducible to $(P)$.

The main obstacle (so as to prove the instance of CFLP can be solved as instance of our problem) here is that in order to remove the last term in objective function of $(P)$, we can set the decision variable $q_i=0$, however, it yields that $w_i$ should be $1$ for all $i$ (due to existence of third constraints). In CFLP notation, it means that all facilities should be open (which does not parse to me). Is there any alternative way to for the proof?

  • $\begingroup$ or.stackexchange.com/questions/tagged/facility-location $\endgroup$ Commented Jul 4, 2023 at 10:39
  • 1
    $\begingroup$ @Nathaniel: Thank you for your comment. I addressed most of the concerns you mentioned. about attribution, besides noting that (P) is written by myself, I need to check CFLP attribution then. $\endgroup$
    – Ramon
    Commented Jul 4, 2023 at 10:46
  • $\begingroup$ Thank you for editing your post! $\endgroup$
    – Nathaniel
    Commented Jul 4, 2023 at 10:57

1 Answer 1


Just set $\beta_i = 0$ instead of $q_i$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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