# Polynomially solvable cases of zero-one programming

Operations Research Asked on August 19, 2021

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&quadsum_i c_i x_i \ text{s.t.}&quad x_i + x_j leq 1, quad d(i,j)

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 Axgeq b, xin Z^ntimes 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 :)).

Correct answer by Marco Lübbecke on August 19, 2021

## Related Questions

### Conditions required for strong duality to hold for SDPs

1  Asked on August 19, 2021

### Relationship between extreme points and optimal solutions of SDPs

1  Asked on August 19, 2021

### How to parallelize metaheuristics algorithms (Island Model)?

1  Asked on August 19, 2021 by antarctica

### Can we get closed form solution for such a problem?

1  Asked on August 19, 2021

### Can we use reinforcement learning and convex optimization to solve an optimization problem?

2  Asked on August 19, 2021 by qinqinxiaoguai

### Nonlinear integer (0/1) programming solver

6  Asked on March 1, 2021 by rajya

### How can I find the shortest path for all nodes in a graph from a source $s$?

1  Asked on March 1, 2021 by windbreeze

### Free solver for MINP problems

1  Asked on February 18, 2021 by dspinfinity

### Where I can study some job shop scheduling by course (video )?

0  Asked on February 18, 2021 by yue-chao

### Linear objective function with power term in constraint

1  Asked on February 15, 2021 by user152503

### Formulating these logical constraint in an ILP

1  Asked on January 18, 2021

### Modeling the multiplication of two binary decision variables in undirected graph in python

0  Asked on January 18, 2021 by amedeo

### Flexible Job Shop with Preemption

0  Asked on January 15, 2021 by robert-hildebrand

### How to handle an equality constraint in metaheuristic algorithms (like GA, PSO)?

3  Asked on January 11, 2021 by stevgates

### What is the difference between min- cut formulation and (bi) partitioning formulation?

1  Asked on January 8, 2021 by fathese

### Logical constraint in ILP

1  Asked on December 22, 2020 by che

### Quasi-convex function must be “partially monotonic”?

1  Asked on December 13, 2020 by high-gpa

### Constraint programming resources

3  Asked on November 28, 2020 by joffrey-l

### Pyomo variable creation dilemma

1  Asked on October 31, 2020 by ethan-deakins

### Convexity of the variance of a mixture distribution

1  Asked on September 25, 2020 by independentvariable