# NP-Complete Proof - Using CFLP

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?

• or.stackexchange.com/questions/tagged/facility-location Commented Jul 4, 2023 at 10:39
• @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. Commented Jul 4, 2023 at 10:46
• Thank you for editing your post! Commented Jul 4, 2023 at 10:57

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