20
votes
Accepted
Is there a counterexample to this work?
Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first ...
- 5,712
11
votes
Accepted
Anti bin packing
This problem is called bin covering. It's NP-hard and hard to approximate to better than a factor of two by an easy reduction from subset sum but has an asymptotic approximation scheme (i.e. one that ...
- 50.2k
11
votes
Accepted
Reduction from SAT to 0,1 integer linear program with zero or one solutions
OptP-complete. Krentel showed that MAX-SAT, finding the lexicographically maximum satisfying assignment, is OptP-complete and the reduction above reduces Max-SAT to ILP. ILP sits in OptP pretty much ...
- 8,546
9
votes
Accepted
What are some example problems for integer programming that are *not binary*
Here are a few examples:
(Most Common) Cutting Stock Problem - determine patterns for which to cut boards in order to meet demand.
(Kinda same problem) - Knapsack with general integer variables - ...
7
votes
Accepted
Is finding an optimal solution to this Knapsack-like problem NP-hard?
NOTE: My original reduction didn't work. Fixed now.
Can't subset-sum be reduced to this problem fairly easily? Suppose all the profits $v_i$ are the same, say $v_i = 1$, and all the profits $p_i$ are ...
- 23.5k
7
votes
Accepted
Consequences of faster parameterized integer programming
An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally ...
- 5,225
6
votes
Accepted
What is known about this binary representation polytope?
I think $S_n$ can be written in terms of inequalities in the obvious way. Let
$$
Q_n = \{(x, y): x = \sum_{i = 0}^{n-1}{2^i y_i}, \forall i: 0 \leq y_i \leq 1\}.
$$
I claim that $Q_n = S_n$. First, ...
- 18k
6
votes
Accepted
Quanitifier Free Presburger Arithmetic: Upper bound on solution size?
You can find an answer in the following paper:
Joachim von zur Gathen, Malte Sieveking. A bound on solutions of integer linear equalities and inequalities.
Proc. AMS 72(1) (1978)
(pdf)
A simple ...
- 527
6
votes
Accepted
Characterization of integral polyhedra
Here's a proof (sketch) that doesn't explicitly use duality. More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below.
EDIT: But, ...
- 8,228
5
votes
Have fixed parameter integer program algorithms ever been implemented for research use?
The original algorithm of Lenstra (from 1983) has not been implemented AFAIK. Certainly, no open-source code is known to be available.
Lovasz and Scarf proposed (in 1992) a generalized basis ...
- 316
5
votes
Accepted
NP completeness of linear $0-1$ assignment problem
If I understood it well, (1) is also NP-complete, a possible reduction is from SUBSET SUM:
Given a set of $m$ positive integers $A = \{a_1, ..., a_m\}$, and a positive integer $B$, is there a subset ...
- 22.3k
5
votes
Accepted
Fixed parameter tractable Integer Programming and $FPP$
You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^*$, whereas parameterized decision problems are ...
- 386
5
votes
On integer programming
It's NP-hard. Given an integer programming problem $P$, add an irrelevant variable $z$ with no constraints; call the resulting problem $P'$. Now if $P$ has no solutions, then $P'$ has no solutions; ...
- 10.4k
5
votes
Accepted
On integer programming
(1) As finding a second satisfying assignment to a 3SAT formula is still $\mathsf{FNP}$-complete (indeed, it is $\mathsf{ASP}$-complete, see Theorem 3.5 of [1]), and we can encode 3SAT as an integer ...
- 35.7k
4
votes
Accepted
Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?
Kolloiopoulos and Young give an $O(\log m)$ approximation for general covering integer programs. See the paper below.
http://www.sciencedirect.com/science/article/pii/S0022000005000656
- 6,649
4
votes
NP completeness of linear $0-1$ assignment problem
It seems that we can reduce Subset Sum to your problem (2). Hence, your problem (2) is NP-complete.
Consider the following formulation of Subset Sum.
Instance: A multi-set consisting of $n$ ...
- 4,900
4
votes
Accepted
Complexity of generating a pseudo-Boolean function
There's a straightforward way to construct a function $f_z:\{0,1\}^n \to \mathbb{R}$ that is zero at only a single point $z=(z_1,\dots,z_n)$ and strictly positive everywhere else: namely,
$$f_z(x_1,\...
- 10.4k
4
votes
Is that edge orientation optimization problem NP-hard?
We answer OP's last question: can an approximate solution to IQP be obtained by randomized rounding?
We show that the natural randomized-rounding scheme gives a 2-approximation, and a $(1+1/\overline ...
- 8,228
4
votes
Accepted
Is this edge orientation optimization problem NP-hard?
I believe that this problem is NP-hard, here is a sketch proof (don't hesitate to ask for more details if needed).
The idea is based on a reduction from the Not-all-equal 3-SAT. For $\varphi$ a 3-SAT ...
- 685
3
votes
Accepted
Minimum Union-Sum Cost Path
EDIT (Jan 2019): Lemma 2 as currently stated below is wrong. (Indeed, given any instance, adding a single edge with a single type of very large cost will not change the instance but will yield $N(I)=1$...
- 8,228
3
votes
Is that edge orientation optimization problem NP-hard?
Definition: Given an undirected graph $G$ and an edge orientation $\vec{G}$, an unstable path is a directed path that goes from a node $s$ to a node $t$, such that the out-degree of node $s$ is ...
- 685
3
votes
Accepted
How hard is this combinatorial optimisation problem?
This problem can be solved with dynamic programming in pseudo-polynomial time (proof below). Therefore, it is not possible to show that this problem is strongly NP-hard (unless P=NP).
First, let's ...
- 2,718
2
votes
FPT algorithm for mixed integer program
The complexity of Lenstra's algorithm for mixed-integer programming in his paper runs as $2^{O(n^3)}*poly(d, \phi)$ where there are $n$ integer variables, $d$ continuos variables, and $\phi$ is the ...
2
votes
convertion into integer linear program for Ising spin state problem
Have a look at the paper "Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem" by Alain Billionnet and Sourour Elloumi. They mention there that the binary ...
2
votes
Which Integer Linear Programs are easy?
An integer program with only equalities can be solved by linear program.
- 12.5k
2
votes
Accepted
Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?
Base on Komus's constraint, we add another constraint which ensures a Steiner Tree on $G^{'}=(V, E^{'})$, where $E'=\{(i,j): i,j \in V\}$:
$$\sum_{e \in cut(U,V)}x_e \ge 1, \forall u,v \in T, \forall ...
- 451
2
votes
Accepted
Ensuring integral maximizer from integral linear program
Given an integral LP, you can use a LP algorithm to compute in polynomial time
the optimal value of the LP,
a vertex of the feasible region (polytope) of the LP where the optimal value is attained.
...
- 14.8k
2
votes
Name of (and solution to) this generalization of linear assignment
It looks to me like this is a special case of minimum cost flow; introduce one vertex per row and one per column, with an edge for each entry whose cost is the negative of the value of that entry and ...
- 10.4k
2
votes
Accepted
Do there exist two equivalent objective functions one of which can be approximated but another one cannot?
The answer to Question (1) is no. The answer to Question (2) is yes. Here are the details.
I'll work with the following equivalent problem formulations. For the input, we are given $n$ pairs of ...
- 8,228
1
vote
How do minimally violated k-mod cuts work (intuitive explanation)?
Suppose you have an integer linear program, and it contains the following constraints:
x1 + x2 + x3 >= 1,
x1 + x2 + x4 >= 1,
x1 + x3 + x4 >= 1,
x2 + x3 + x4 >= 1.
If we set x1, ..., x4 to 1/3, we ...
Only top scored, non community-wiki answers of a minimum length are eligible