What is non-linear assignment problem?

Question

I am reading wikipedia article about assignment problem https://en.wikipedia.org/wiki/Assignment_problem

but cannot understand the definition of 'linear' assignment problem.

What is an example of non-linear assignment problem ?

thanks

Answer 1

When we refer to an optimization problem as "linear", it means that we can form the model in such a way that no term in the function has an exponent (greater than 1, at least).

Let's take a small example: Assigning professors to courses. I'll skip a lot of the middle details, but one model for this problem is to find an assignment such that each professor is assigned a course they would prefer to teach. We'll do this with the following objective function.

$$Z = min \displaystyle \sum^i \sum^j c_{i,j} ~x_{i,j}$$

Each term is one coefficient $c_{i,j}$ (the cost of professor $i$ teaching course $j$ - let's say this is how much a professor would dislike teaching a particular course) and one decision variable $x_{i,j}$ (a binary variable where $1$ means professor $i$ is assigned course $j$ and $0$ otherwise). Because each term is "linear", as in there are no terms where a variable is being multiplied by another variable or itself, the function (and therefore the problem) is linear.

Now how could this be made non-linear? What if we wanted to ensure that the spread of courses is as even as it can be so no professor is teaching too few or too many courses. For the sake of simplicity, let's define $k = \frac{\# \text{ of courses}}{\# \text{ of professors}}$ and ask each professor to teach that number of courses.

How can we enforce that? We could determine the number of courses a professor is teaching and try to minimize the difference. A naive approach would be to count the number of courses a professor is teaching and try to minimize the difference between that and the average.

$$Z = min \sum^i \big( \sum^j x_{i,j} \big) - k$$

A simple approach like this would not work, however. Take for example a system with 3 professors and 6 courses. If professors 1 and 2 only teach 1 course and professor 3 teaches 4 courses, then we get $Z = (1 - 2) + (1 - 2) + (4 - 2) = 0$. A value of 0 indicates that this is the best solution, right? Maybe for professors 1 and 2, but no. Thus, a different approach needs to be taken. Two approaches would be to rather take the absolute value of the difference or (even better) square the difference. Let's see how that objective function looks.

$$Z = min \sum^i \Big( \big( \sum^j x_{i,j} \big) - k \Big)^2 $$

If we used the skewed assignment, we get $Z = (1-2)^2 + (1-2)^2 + (4-2)^2 = 3$, while an even distribution gives $Z = (2-2)^2 + (2-2)^2 + (2-2)^2 = 0$. The only problem is there is now an exponent on the decision variables, making this problem non-linear. In particular, this becomes a quadratic formula, thus making it a quadratic assignment problem.