We are given the polyhedron $X=\{x:Ax\le b,x\ge 0\}$ and the point $y\in X$. We want to find a point $x \in X$ such that $d(x,y)$ is maximized. The function $d(x,y)$ represents the distance between the two points. With regard to this problem, I have the following question:

Are you aware of some distance function $d(x,y)$ such that the problem can be formulated as a linear program or be solved very efficiently?

I was trying to use $d(x,y)=\sum_{i=1}^n|x_i-y_i|$ where $x_i$ and $y_i$ are elements of $n$-vectors $x$ and $y$, respectively. The issue is that I can only formulate the problem as a mixed-integer linear program, not a linear program. Any suggestions?

  • $\begingroup$ I'm not sure my reasoning is correct. Lets see the one dimensional case: You are trying to maximize the function |x-y|. That is essentially solving the following two linear programming problems: $\max: x-y$ such that $x-y\geq 0\text{ and }x\in X$, and $\max: y-x$ such that $y-x\geq 0\text{ and }x\in X$. The solution you want is the maximum between the solutions of this two linear programmings. $\endgroup$ – Hugocito Jul 12 '18 at 2:25
  • 1
    $\begingroup$ @Hugocito Yes, but this is the idea of the mixed-integer linear program that I mentioned. When you are in $n$ dimensional space, you need $n$ binary decision variables and therefore $2^n$ linear programs might be necessary to solve. If you formulate the problem as a mixed-integer linear program, then solving that formulation usually is done without having to enumerate all possible ($2^n$) cases. In the end, it is still a mixed-integer program that is NP-hard in general. I am looking for some other distance measure that can be handled using one linear program (or maybe a few of them). $\endgroup$ – Opt Jul 12 '18 at 3:10
  • $\begingroup$ You are trying to maximize a convex function over a convex set. In general, this problem is NP hard, so I think it’s unlikely you can get an LP formulation. That being said, modern MIP solvers are very good, so it may be worth trying the MIP approach (depending on exactly what your needs are). These slides discuss some other approaches. $\endgroup$ – David M. Jul 12 '18 at 4:18

Your Answer

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

Browse other questions tagged or ask your own question.