0

In my introduction to optimization course, we are given the following problem as an example:

Sorting task: Given real numbers $c_1, c_2, \ldots, c_n \in \mathbb{R}$, we want to find the $k$ smallest numbers. This is the $k$-smallest numbers optimization problem: $$ \begin{align*} &\min_{x_1, \ldots, x_n} &c_1 x_1 + c_2 x_2 + \cdots + c_n x_n\\ &\textrm{subject to} &x_1 + x_2 + \cdots + x_n = k\\ & &\textrm{for all } i=1, \ldots, n: 0 \leq x_i \leq 1 \end{align*} $$

I don't understand what this is trying to achieve. If you are trying to find the 1st to $k$'th smallest numbers, why are $x_i$ real numbers instead of integers where $x_i \in \{0, 1\}$? If they were integers, then when $x_i = 0$, it would mean that $c_i$ is not among the $k$-smallest numbers (not selected), while $x_i= 1$ means that $c_i$ is selected. Or is this problem trying to minimize the weighted sum of $c_1, \ldots, c_n$? Why must all $x_i$ sum to $k$?

Jon
  • 11
  • To minimize the objective it pays off to assign $x_i=1$ for those values of $i$ which determine the $k$ smallest $c_i$ and $0$ otherwise. You see that if you had some different optimal point then it would pay off to "shift some weight of the $x_i$s" towards the smaller $c_i$ and ultimately you prove the statement from my first sentence. Try with $k=1$ first. – Michal Adamaszek Dec 06 '22 at 20:22
  • The way the question is set up is ambiguous. So I'm downvoting until it is clarified. If that's the way the question was presented to you, then it's no wonder you're confused. – Adam Rubinson Dec 06 '22 at 20:47
  • @AdamRubinson It was precisely how the problem was presented to me. I think I will ask the instructor for clarifications. – Jon Dec 06 '22 at 21:04

1 Answers1

-1

The person you should ask is the instructor -- it is hard to know what they had in mind when creating this problem. However, this is my best guess for what they were going for.

Presumably the values $c_{i}$ are intended to be positive. In this case, you are right that constraining each $x_{i}$ to be an integer would indeed result in then problem of finding which $k$ of the $c_{i}$ are smallest. However, that is an integer optimization problem -- integer optimization is generally quite difficult in a computational sense, so it is instead solve what is a called a relaxation of the original problem. Essentially weakening the constraints gives a problem which may be much easier to solve yet give an "approximate" solution to the original problem. Here we are relaxing the constraint that $x_{i} \in \{ 0, 1 \}$, replacing it with $x_{i} \in [0,1]$.

I put approximate in quotations, since it's not usually an approximation in the literal sense. We usually want to solve the original problem exactly, and the approximate solution helps us to do so. What that means depends on the situation, but in this case it is simple -- the approximate solution is actually a solution to the original problem. That is, if we solve the given problem we necessarily get a solution with each $x_{i}$ in $\{ 0, 1 \}$. Basically, we've reduced a computationally-difficult integer optimization problem into a rather straightforward linear optimization problem.

Jacob Maibach
  • 2,512
  • 2
  • 14
  • 20
  • Thank you for the detailed answer. I absolutley take your point on computational complexity and avoiding combinatorial optimization. I now see that this relaxed form still has an equivalent optimal solution as the original. It just seemed unintuitive and kind of roundabout to me, the way it was written (minimizing the weighted sum, sum of weights = k). – Jon Dec 06 '22 at 21:16
  • @Jon The reason this formulation is so nice is that it can be dualized and then you can write the sum of smallest $k$ elements as an LP, even if $c$ are optimization variables (which is what you really want, after all why use optimization to solve a problem which is trivial anyway). Details in https://docs.mosek.com/modeling-cookbook/linear.html#weak-and-strong-duality Example 2.7 – Michal Adamaszek Dec 07 '22 at 06:58