Can you calculate the mean of some MIP variables using linear constraints?

Question

got a lingering question from a graduate course in integer programming that's been bugging me ever since.

Is it possible to find the mean of some variables in a MIP without resorting to quadratic constraints?

Here's an example of what I mean:

Suppose there are $N$ cities you could travel to and you've given each city a rating, $r$. In some goal program style MIP you create a binary variable, $X_{i}$, to indicate whether or not you will be travelling to city $i$.

Finding the average rating you've attributed to a city is simple enough:

$\bar{r} = \frac{1}{N}\sum_i{r_i}$

But what if you wanted to find the average rating of the cities the program has selected, i.e., those whos $X_i = 1$?

This is where I am stuck - the calculations I have to find this new average are pretty simple:

$\bar{R} = \frac{1}{\sum_i{X_i}}\sum_i{r_iX_i}$

But because I am multiplying $\bar{R}$ and $\sum_i{X_i}$, both decision variables that the model calculates based on its solution, the constraint used to find $\bar{R}$ is quadratic.

For clarification - in this problem, you're trying to find a subtour of the $N$ cities to travel to, so it cannot be assumed that $\sum_i{X_i} = N$. The number of cities you travel to, $\sum_i{X_i}$, is in itself a decision variable.

Is there any way to make this kind of calculation linear?

The aforementioned graduate class seemed to imply such a thing could be done, but I could have just misinterpreted what the lecture was saying at that time.

As of yet, I haven't been able to come up with a way to do this, so I'm wondering if the smart people of the internet might be able to tell me for certain if its impossible or not.

Answer 1

You can do it if you have a fairly high pain tolerance. :-)

Let's start by introducing binary variables $Z_1,\dots, Z_K$ (where $K$ is the dimension of $X$) and making $N$ a variable. Add constraints $$\sum_{j=1}^K Z_j = 1,$$$$N=\sum_{j=1}^K j\cdot Z_j$$and $$\sum_{j=1}^K X_j = N.$$I'm assuming here that at least one of the $X$ variables will be 1, since $N=0$ makes the mean a bit undefined.

Now comes the fun part. If variable $Y$ is supposed to be the mean, we want to set$$Y\cdot N = \sum_{j=1}^K r_j \cdot X_j.$$The right side is linear, so that's no problem. The left side expands to $\sum_{j=1}^K j\cdot Z_j \cdot Y$. Each term is a product of a general variable ($Y$) and a binary variable ($Z_j$). Rob's answer to Mixed-integer optimization with bilinear constraint shows how to linearize those by adding more variables and constraints, assuming that you can bound $Y$.