Polynomially solvable cases of zero-one programming

Question

I am dealing with a problem having two types of variables: binary variables, and continuous variables.

In some cases, the continuous variables are not used, and so the problem contains those binary variables only. These cases are then very easy to solve with the commercial solvers. For example, a problem with 1000 variables can be optimally solved within 4 seconds on a PC.

What I am looking for is to find out whether the resulting zero-one problem is polynomially solvable. I would like to know what special cases of zero-one programming problems are polynomially solvable.

---

EDIT: My thanks to @MarcoLubbecke. The model I am working on is as follows. There is a set $N$ of nodes, where every node $i \in N$ is associated with a positive integer weight $c_i$, and the distance between two nodes $i$ and $j$ is represented by $d(i,j)$ (also positive integers). The problem is to select $p$ nodes, where the distance between each two selected nodes should not be less than a pre-specified integer $u$.

\begin{align} z = \min&\quad\sum_i c_i x_i \\ \text{s.t.}&\quad x_i + x_j \leq 1, \quad d(i,j) <u, \quad \forall (i,j) \in N^2, \tag1 \\ &\quad\sum_i x_i = p \tag2 \\ &\quad x_{i} \in \{0,1\}. \end{align}

Answer 1

First of all, I would say that "fast solvable in practice" is possible also when your remaining problem still is NP-hard. But since you ask specifically for polytime solvability, there are some cases.

Most well-known is probably "TU-ness" of your matrix. When you solve a MIP $$\min\{c^tx \mid Ax\geq b, x\in Z^n\times Q^q\}$$ then you will obtain an integer solution to the LP relaxation if your matrix is totally unimodular and your right hand side $b$ is integer (this would imply that you only need to solve the LP, which is doable -- in theory -- in polynomial time). E.g., optimization problems on (undirected) bipartite graphs and flow problems on directed graphs lead to models of this structure. This is one case of the more general situation that your underlying polyhedron is integer (i.e., every face, in particular the vertices, contain an integer point), and there are other criteria for this to happen (check also TDI systems); in fact, it is sufficient if you could show that your optimal face is always integral, or even only that the optimal face always contains an integer point (here is an example where people do this for half-integrality).

But this is not exhaustive; it is possible that your model does not possess this property and you can still solve it polynomially. It may happen that your particular problem structure is a polynomial special case of an NP-hard problem; e.g., you solve a maximum clique problem, hard in general, but on, let's say, interval graphs, this is super easy.

And then again, your structure may not be one of those "special ones" where polynomial time solvability is known, but your data is so restricted that a (new?) polynomial special case results.

Saying this, it would be nice to see your particular problem/model.

EDIT after you added your model; this is a stable set/independent set problem, where you are looking for a minimum weight stable set. This would be typically: selecting no vertex at all. However, you have this cardinality constraint forcing you to select vertices. I don't know the status of this problem, but it may be that there are "fixed parameter" algorithms for stable set, where the parameter is the size of the solution (which is fixed to $p$ in your case). In principle, you could enumerate all $p$-subsets of vertices and pick a cheapest set; there are $n \choose p$ such subsets, and when $p$ is fixed this is polytime :) [you see, that I answered my question about complexity status while writing...]

You have one more special property: assuming that your distances are metric, your conflict graph is a unit disk graph: you have an edge iff the distance between two nodes is smaller than a (unit) distance. The stable set problem is easier to approximate on unit disk graphs, so it may be "easier" also computationally (that brings me back to my initial sentence :)).