I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express these logical operations I introduce binary variables (as in here) $\gamma_1$, $\gamma_2$ so I end up with a Mixed Integer Linear Program that looks something like this:

$$ \begin{equation*} \begin{aligned} & \underset{x, \gamma}{\text{minimize}} & & c^T \mathbf{x} \\ & \text{subject to} & & X^i_{1} \leq \gamma^i_1, \; i \in [n], \\ &&& X^i_{2} \leq \gamma^i_2, \; i \in [n], \\ &&& \gamma^i_1 \leq \gamma^i_2, \; i \in [n], \\ &&& \gamma^i_1, \gamma^i_2 \in \left\{ 0,1\right\}, \; i \in [n] \\ &&& \mathbf{x} \succeq 0 \end{aligned} \end{equation*} $$

I know these types of problems can be solved well in practice using a wide range of heuristics, but I am interested in a provably efficient algorithm for approximating this problem.

I don't see why the LP relaxation of this MILP (obtained by only asking that the $\gamma$'s be in $[0,1]$) gives me anything: unlike classic examples like Set Cover, is it clear how to obtain a feasible solution (integral) to the original problem from a solution to the LP relaxation? A rounding approach seems useless here, because I can do whatever I want to the values of $\gamma$, but that doesn't actually effect the solution $\mathbf{x}$. If I can't "translate" a solution to the LP to an integral solution, how can I say anything about the integrality gap?

My questions:

  1. Am I correct in that for this particular type of MILP (resulting from logical constraints), the LP relaxation is useless?
  2. Is there any other approach which I might be able to use to say something about the ability to approximate my problem?

I have very little background in approximation algorithms so I would really appreciate any pointers. I hope the question is clear and made sense. Thanks!

  • $\begingroup$ I suspect LP with logical implications is NP-hard, in which case you shouldn't expect any provably efficient algorithm to find the optimal solution. It's not clear what kind of approximately you have in mind (i.e., what notion of approximability you are thinking of), but I suspect there's not much hope for provable approximations, either. $\endgroup$
    – D.W.
    Feb 10, 2019 at 7:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.