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) <u, quad forall (i,j) in N^2, tag1 \

&quadsum_i x_i = p tag2 \

&quad x_{i} in {0,1}.

end{align}

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

1 Asked on August 19, 2021

1 Asked on August 19, 2021

1 Asked on August 19, 2021 by antarctica

2 Asked on August 19, 2021 by qinqinxiaoguai

6 Asked on March 1, 2021 by rajya

integer programming linearization nonlinear programming quadratic programming

1 Asked on March 1, 2021 by windbreeze

1 Asked on February 18, 2021 by dspinfinity

0 Asked on February 18, 2021 by yue-chao

1 Asked on February 15, 2021 by user152503

1 Asked on January 18, 2021

linear programming linearization logical constraints mixed integer programming

0 Asked on January 18, 2021 by amedeo

0 Asked on January 15, 2021 by robert-hildebrand

integer programming optimization scheduling simulated annealing solver

3 Asked on January 11, 2021 by stevgates

1 Asked on January 8, 2021 by fathese

1 Asked on December 22, 2020 by che

binary variable linear programming linearization logical constraints mixed integer programming

1 Asked on December 13, 2020 by high-gpa

3 Asked on November 28, 2020 by joffrey-l

1 Asked on September 25, 2020 by independentvariable

convex optimization convexity nonconvex programming probability distributions

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?

Recent Questions

- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?
- Why fry rice before boiling?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP