"Non-traditional" linear programming formulation

Question

I am having trouble coming up with a linear programming formulation for the following question:

As head of a sales department, you have to form sales teams to perform site visits to 6 sites: $A, B, C, D, E, F.$ Each site must be visited at least $a_i$ ($a_i$ is a constant, $i=A,B...F$) times by your department, and each sales team can only visit strictly 3 or 4 sites.

Furthermore, due to conflicts of interest, certain pairs of sites cannot be visited by the same sales team: $(C,D), (C,E), (A,B), (B,F), (D,F)$.

Formulate an LP to minimise the number of sales teams you need to form.

I forgot the exact numbers for $a_i$s but you can take them to be 7,8,9,10,11,12 for convenience.

Can this LP be formulated at all? I was thinking of funny stuff like "the set of all teams visiting A", but that seems ridiculous.

Answer 1

Here is another formulation, that will be easier to solve than Math1000's model (as it has only $4$ variables and $6$ constraints). Let $\Omega$ be the set of feasible schedules for a given team. $\Omega$ is thus composed of the following visits:

1. A-C-F
2. A-D-E
3. A-E-F
4. B-D-E

Define binary variables $y_j$ that equal $1$ if schedule $j\in \Omega$ is used. The following formulation models the problem: $$ \min\quad y_1+y_2+y_3+y_4 $$ subject to \begin{align} y_1+y_2 +y_3 &\ge a_A\\ y_4 &\ge a_B \\ y_1 &\ge a_C \\ y_2+y_4 &\ge a_D \\ y_2+y_3+y_4 &\ge a_E \\ y_1+y_3 &\ge a_F \\ y_j&\in\{0,1\}\quad \forall j\in \Omega \end{align}

Note: it is easy to see that the problem is infeasible if $a_A>3$ or $a_B>1$ or $a_C>1$ or $a_D>2$ or $a_E>3$ or $a_F>2$.

Answer 2

Let $\alpha=\sum_i a_i$, $[\alpha]=\{1,2,\ldots,\alpha\}$, and $\mathcal S=\{A,B,C,D,E,F\}$. Define for each $j\in[\alpha]$ $$z_j = \begin{cases}1,& \text{ team $j$ is used}\\0,& \text{ otherwise}, \end{cases} $$ and define for $(i,j)\in \mathcal S\times[\alpha]$ $$x_{ij}=\begin{cases}1,& \text{ site $i$ is visited by team $j$ }\\0,& \text{ otherwise}. \end{cases} $$ We can model this problem as the mixed-integer linear program: \begin{align} \min&\quad \sum_{j=1}^\alpha z_j\\ \mathrm{s.t.}&\quad \sum_{j=1}^\alpha x_{ij}\geqslant a_i, \quad\quad\quad i\in\mathcal S \tag1\\ &\quad x_{ij} \leqslant z_j, \quad\quad\quad\quad\;\, (i,j)\in\mathcal S\times[\alpha]\tag2\\ &\quad \sum_{i\in\mathcal S}x_{ij} \geqslant 3z_j, \quad\quad\; (i,j)\in\mathcal S\times[\alpha]\tag3\\ &\quad \sum_{i\in\mathcal S}x_{ij} \leqslant 4z_j, \quad\quad\quad\quad (i,j)\in\mathcal S\times[\alpha]\tag4\\ &\quad x_{Cj} + x_{Dj} \leqslant 1, \quad\quad j\in[\alpha] \tag5\\ &\quad x_{Cj} + x_{Ej} \leqslant 1, \quad\quad j\in[\alpha]\tag6\\ &\quad x_{Aj} + x_{Bj} \leqslant 1, \quad\quad j\in[\alpha]\tag7\\ &\quad x_{Bj} + x_{Fj} \leqslant 1, \quad\quad j\in[\alpha]\tag8\\ &\quad x_{Dj} + x_{Fj} \leqslant 1, \quad\quad j\in[\alpha]\tag9\\ &\quad z_j\in\{0,1\},\quad\quad\quad\;\, j\in[\alpha]\\ &\quad x_{ij}\in\{0,1\},\quad\quad\quad i,j\in\mathcal S\times[\alpha] \end{align} Constraints $(1)$ satisfy demand. Constraints $(2)$ require that team $j$ be used in order for any site to be visited by team $j$. Constraints $(3)$ and $(4)$ enforce the restriction on the number of sites that a given team visits. Constraints $(5)$-$(9)$ enforce the conflicts of interest.

Note: I chose $\sum_i a_i$ as an upper bound for the number of teams because it works, but a better upper bound would likely result in a formulation that is much easier to solve.