# "Non-traditional" linear programming formulation

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.

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.

• In constraint (4) I think there is typo, it should be $\sum_{i\in S} x_{ij} \le 4z_{j}$. Oct 1, 2016 at 14:34
• @Kuifje Indeed, thanks for pointing that out. Oct 1, 2016 at 14:35
• By inspection, it is not difficult to see that an upper bound on the number of teams is $4$, which significantly simplifies your model. Oct 1, 2016 at 18:28

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$.

• Indeed, this is a better formulation - I am used to modelling larger problems and did not notice that there were only four feasible subsets of sites for a team to visit! Oct 1, 2016 at 18:34
• I believe you are missing $y_3$ on the LHS of the constraint for site $A$ though. Oct 1, 2016 at 18:42
• I am indeed, thanks! Oct 1, 2016 at 18:44
• By the way, this is a network flow problem, so the integrality constraints need not be enforced. The constraint matrix is totally unimodular and the RHS is integral, and so the vertices of the feasible region are integral. Oct 1, 2016 at 18:48
• A network flow model? It looks more like a set covering model to me, very similar to the classical cutting stock problems. Oct 1, 2016 at 18:54