4
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ What role does the average play in the model? Are you trying to optimize it or maybe bound it? $\endgroup$
    – RobPratt
    Dec 7, 2021 at 19:41
  • $\begingroup$ The actual problem I've pulled this example from is a larger goal program where I'm solving a TSP, but instead of minimizing the distance traveled while hitting every city I'm minimizing the negative deviation from the original average rating (among other things). So, the TSP formulation gets the subset of cities to travel to and calculates our new average. I want this new average to deviate from the original as minimally as possible. Hope that explains it well enough! $\endgroup$ Dec 7, 2021 at 19:49
  • 1
    $\begingroup$ For TSP, every city is visited, so $\sum_i X_i=N$, a constant. $\endgroup$
    – RobPratt
    Dec 7, 2021 at 19:53
  • $\begingroup$ Aye, but this isn't an exact TSP formulation. Subtours are encouraged in this formulation so $\sum_i{X_i}$ doesn't necessarily have to equal $N$ in this case. $\endgroup$ Dec 7, 2021 at 19:54

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ With this and Rob's answer you linked to, it looks like everything is falling into place! Took a bit of finagling, but I managed to work this approach into my problem and all appears to be working(: Very much appreciated! $\endgroup$ Dec 8, 2021 at 1:50
  • $\begingroup$ Glad it worked. Mathematically it's correct, but "big M" models actually solving in reasonable time is somewhat hit and miss. $\endgroup$
    – prubin
    Dec 8, 2021 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.