I have a scheduling of staff program that I think can be solved using linear programming. However, I am stumped on how to formulate the equations.
Problem: I have a list of candidates with specific job titles and certificates. For example - a candidate can either be an Engineer, Dredge Master or Technician. Each person can hold certificates in Firefighting, First Aid, Lifesaving.
I need to select, for example,
- $3$ Engineers
- $2$ Dredge Masters
- $7$ Technicians
but between them, there must be
- $4$ First Aid certificates
- $2$ Lifesaving certificates
- $5$ First Aid certificates.
Any help will be appreciated. Thanks.
Suppose we have $n \geq 12$ candidates and binary matrices $\mathrm A, \mathrm B \in \{0,1\}^{n \times 3}$, where $a_{ij} = 1$ means that candidate $i$ has job title $j$, and $b_{ij} = 1$ means that candidate $i$ has certificate $j$. Let $\mathrm c \in \mathbb R^n$ be the cost vector, whose $i$-th entry is the cost of hiring candidate $i$.
Let $\mathrm x \in \{0,1\}^n$ be the decision vector, where $x_i = 1$ means that we hire candidate $i$. If we want to minimize the cost, we have the following binary linear program
$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A^{\top} \mathrm x = \begin{bmatrix} 3\\ 2\\ 7 \end{bmatrix}\\ & \mathrm B^{\top} \mathrm x \geq \begin{bmatrix} 4\\ 2\\ 5 \end{bmatrix}\\ & \mathrm x \in \{0,1\}^n\end{array}$$