# Developing Constraints for a linear programming based problem

Recently, I thought of developing a mathematical approach to a task I commonly do every week. Simply enough, it's a schedule.

That said, I have a few questions regarding the process. I haven't worked with linear programming before, but the math isn't the concern. It's expressing the constraints.

Let me describe them:

I have several roles to fill. Role A, say, is a priority, then each role after that is less important. I then have several groups of individuals. Group A can perform tasks in role A, and any other tasks after that. Then Group B, can't fill Role A, but any task after that. Each group, from increasing alphabetical order, has less individuals then the previous (i.e. A

That is the general idea.

Like I said before, I don't have much experience with linear programming (I recently ordered a book on the subject, but if there are any good suggestions that deal with applications like the above would be very much appreciated).

In any case, I'm particularly curious as how the constraints would look regarding having several roles with priorities that only certain groups can perform. Obviously, it's quite simple to write a constraint stating that each role must be filled, but I haven't seen many constraints describing what I'm needing.

Also, I'm still trying to find a way to express each group. For instance, say group A was composed of {Ed, Ted, Red, Bob, John}. Would I express that group as a variable itself, such as x? However, that violates one of the needed constraints: Ed can't have two roles at the same time! I need a way to prevent that. A matrix within a matrix perhaps? So A=[Ed, Ted,...]. It would more likely be a column matrix though.

Regardless, a little insight would be helpful. I don't necessarily want a complete answer, such as do this then this - more so a good starting place.

Any help is appreciated.

-

This problem won't strictly be a linear program, but is better suited to Integer Programming.

First question: What sort of sets are working with? We seem to have a set of jobs that must be completed. Additionally, we have a set of people who can do these jobs. Let's denote these sets $J$ and $P$, respectively. I'll assume those are the only sets you're dealing with, unless you'd like to clarify further.

Next question: What sort of decision variables will I need to formulate the problem? Well, we probably need to assign people to jobs, in some fashion. Let $j\in J$ and $p\in P$ and let \begin{equation*}x_{ij}=\begin{cases}1& \text{job } j \text{ is completed by person }p\\ 0& \text{otherwise}\end{cases}.\end{equation*} Alternatively, you might want to assign a person to a group, the A and B you spoke of, or a group and a job, etc. You'll have to go back and make more sets, if that's the case.

What sort of parameters do you need? Maybe something that measures your utility of finishing one job before another? Then, you would need a parameter $v$ which encodes a value for each job.

What's your goal? Receive the most utility from completing these jobs? Complete as many as possible? etc. Encode whatever your objective is into a function using whatever sets, variables, and parameters you've defined above.

What constraints do you need? A common constraint in such a resource allocation problem might be that a person can only work on a finite number of jobs throughout the week, say $c$. We might write this constraint as \begin{equation*} \sum_{j\in J} x_{jp}\leq c \hspace{10pt}\forall p\in P. \end{equation*}

The above info is a great general approach to formulating math programming problems.

As for your question regarding forbidding specific tasks from people who are in particular roles, let's suppose we have a set of roles $R$, jobs $J$, and people $P$. Consider $y_{rp}$, a decision variable equal to 1 if person $p$ is assigned to role $r$, and $x_{jp}$ from above. Further, let $J_r\subseteq J$ be a portion of the jobs only a member of role $r$ can perform. Then, we might write the constraint \begin{equation*} \sum_{j\in J'} x_{jp}\leq cy_{rp} \hspace{10pt}\forall p\in P. \end{equation*}

Note that if person $p$ is not assigned to role $r$, he cannot perform any of these tasks, as \begin{equation*} \sum_{j\in J_r} x_{jp}\leq 0. \end{equation*}

However, if he is assigned to role $r$, he may perform as many as $c$ tasks from subset $J_r$.

Does that help get you started? Feel free to ask other questions...

-
Good point, I should've said integer programming. The ultimate goal is not to maximize or minimize, instead it is to make sure every role is filled with the appropriate individual, there are no more jobs to be done - nothing more. To make sure I understand, an individual will not necessarily be a distinctly defined variable. Instead, he/she is simply a parameter attached to a variable as you said, p is an element of P. Is this correct? Also, you would simply put the expansions of the constraints into a coefficient matrix, correct? – Mlagma Sep 29 '12 at 5:15
>The ultimate goal is... to make sure every role is filled This is a satisfiability problem. Your objective function may be something as simple as summing over your person to job assignments. If for some initial conditions your IP produces a value less than your total number jobs, you know that it was impossible for every job to be completed. You'll need a set of constraints to ensure that each job is performed at most once, in order to get valuable answers. And almost, any person's decisions will be described as a set of decision variables denoted by his respective subscript $p$. – Doug Mercer Sep 29 '12 at 5:26
I understand that. In any case, all of this can be represented by matrices as all of the constraints are linear equations? Also, the set itself for P is essentially a group of names assigned incremental integers to represent them? – Mlagma Sep 29 '12 at 5:33
Yes, if you were to enumerate all the constraints you write, you could then take the constraints and write a set of equations $Ax\leq b$ and $Bx=d$ or what have you. However, if you plan on working with a large number of people, jobs, roles, etc, the number of decision variables and constraints will grow rather rapidly. Look into glpk (Gnu Linear Programming Kit) for a fantastic free LP and MIP solver. And sure, P can be a set of names, but you don't want your equations to look like $x_{Ted,1}$. You simply create a bijection between your list of names and a subset of the natural numbers. – Doug Mercer Sep 29 '12 at 5:38
That makes a lot of sense. So the decision variable is simply a 1 or a 0 with "i" being an arbitrary parameter ( such as it being replaced with j in one of the constraints). The person, p, is identified by it's position in the matrix (row - column) within the solution. – Mlagma Sep 29 '12 at 5:40