1
$\begingroup$

Take a single source capacitated FLP (facility location problem). As we know the linear formulation to this problem is:
\begin{align} & && \text{min} \; \sum_{j \in J} a_{ij} \; t_{ij} && \\ & s.t. && \sum_{j \in J} \; a_{ij} = 1 && \forall i\in I \\ & && a_{ij} \in \{0,1\} && \\ \end{align} Where $a_{ij}$ is equal to 1 if client $i$ is served by center $j$ and 0 otherwise. $t_{ij}$ is the travel cost from center $j$ to client $i$.
Is the first constraint correct? P.S. I am new to this subject and hence my struggle to solve this problem.

$\endgroup$
1
  • $\begingroup$ Could you give your question a more descriptive title? That way, others that find your post can also benefit from the answers to your question. $\endgroup$ – Joris Kinable Apr 15 at 4:45
3
$\begingroup$

Here's a way to formulate a more generic constraint that you can then apply to your situation. Suppose you have constant $b$ and binary variables $y_r$ and $z$ and want to enforce $$\sum_{r\in R} y_r \ge b \implies z=1$$ The contrapositive is $$z = 0 \implies \sum_{r\in R} y_r \le b - 1$$ You can enforce this via an indicator constraint or by using the following big-M constraint $$\sum_{r\in R} y_r -(b - 1) \le M z$$ Here, $M$ should be a small constant upper bound on the LHS when $z=1$, and a good choice is $M=|R|-b+1$.

$\endgroup$
5
  • $\begingroup$ Thank you for your response. I can't quite get the relation between your response and my problem. Here what is $R$ representing? If I am write, with this response, I could have $M$ as negative number! $\endgroup$ – mrjamaisvu Apr 11 at 22:29
  • $\begingroup$ For example for a subset like $\{0, 3, 4, 8 ,10\}$ and penalty of 25, I have a $M = 5 - 25 +1 = -19$ which is a negative number. For this set I am gonna have $x_0 + x_3 + x_4 + x_8 + x_{10} - 19 z \leq 24$. Am I right? $\endgroup$ – mrjamaisvu Apr 11 at 22:39
  • $\begingroup$ No, $b=2$ for your situation. The penalty of $25$ will appear as an objective coefficient, not in the constraint. $\endgroup$ – RobPratt Apr 11 at 22:52
  • $\begingroup$ How did you come up with $b=2$? $\endgroup$ – mrjamaisvu Apr 11 at 23:00
  • $\begingroup$ The value $b=2$ corresponds to the "if at least two sites" in your problem description. $\endgroup$ – RobPratt Apr 11 at 23:03
1
$\begingroup$

@RobPratt's answer is obviously the correct answer to this question and is also more general than this one, however, I think this answer can supplement it as it is specific to the OP's case and it also gives a simple thought process to arrive at the result.

The way I think about it is, that you would like to have less than two facilities open from each set $S_k$. Less than two, when counting, means less than or equal to 1. Thus what we ideally would like, in order to avoid the penalties, is that the following set of constraints are satisfied \begin{equation} \sum_{j\in S_k}x_j\leq 1,\quad \forall k=1,\dots,K \end{equation} However, we cannot be sure, that it isn't better to pay some penalties in order to get a better facility constellation, so we introduce a new binary variable for each set $S_k$, here called $z_k$. This binary variable $z_k$ equals 1 if we choose two or more facilities from set $S_k$. The implication \begin{equation} \sum_{j\in S_k}x_j\geq 2 \Rightarrow z_k=1, \quad\forall k=1,\dots,K \end{equation} can be modelled using a "big-$M$" constraint as \begin{equation} \sum_{j\in S_k}x_j\leq 1+ M_kz_k,\quad \forall k=1,\dots,K \end{equation} Here you allow the left hand side to become strictly larger than 1 at the price of setting $z_k=1$. The value of $M_k$ should be set large enough not to interfere with the logic of the problem, but as small as possible: The maximal value of $\sum_{j\in S_k}x_j$ is $\vert S_k\vert$ implying that $M_k$ should be the solution to $\vert S_k\vert = 1 + M_k$, which obviously is (as @RobPratt's answer states) $M_k= \vert S_k\vert-1$. The last thing to do is to add the term \begin{equation} \sum_{k=1}^Kp_kz_k \end{equation} to the objective function.

$\endgroup$

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.