Questions tagged [integer-programming]
The integer-programming tag has no usage guidance.
86
questions
0
votes
0
answers
87
views
Separation oracle for breaking cycles in directed graph
I am working on a directed graph problem and am collaterally interested to know whether there is a separation oracle for the following set of linear constraints.
We are given a directed graph $G$ ...
- 89
2
votes
0
answers
65
views
Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?
Given a graph $G=(V,E)$, costs $c \in \mathbb{R}^E$ the TSP problem is to compute a min cost tour of the graph. The LP is
min $ c^tx $
$x(\delta(S)) \geq 2 \ \ \ \ \forall S \subset V $
$x(\delta(v)...
- 217
1
vote
1
answer
112
views
Hardness of computing the dimension of an integral polytope?
Given a set of linear inequalities $Ax \leq b$ let $P = \text{conv}\{x \in \{0,1\}^n \mid A x \leq b \}$ be the convex hull of all binary vectors that satisfy the given inequalities.
I am interested ...
- 25
2
votes
1
answer
125
views
Do there exist two equivalent objective functions one of which can be approximated but another one cannot?
I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...
3
votes
1
answer
346
views
How hard is this combinatorial optimisation problem?
Suppose we have multiple intervals $R_1,R_2,...,R_i$ of non-negative integers. These intervals may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th interval $R_h$, ...
2
votes
1
answer
167
views
Characterization of integral polyhedra
A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$.
Equivalently, $P$ is integral if ...
- 547
6
votes
2
answers
453
views
Is that edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
- 533
6
votes
1
answer
288
views
Is this edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\...
- 533
3
votes
0
answers
122
views
(Integer) Linear Program formulation of planarity?
Q: Is there an efficient (I)LP formulation of planarity?
More specifically, I am looking for a set of constraints that are satisfied by exactly all planar graphs on $n$ vertices, in order to optimize ...
- 241
1
vote
1
answer
107
views
Ensuring integral maximizer from integral linear program
An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is ...
- 690
1
vote
0
answers
111
views
Is the edge cover polytope integral on graphs with self-loops?
It is well known that the edge cover polytope is integral on simple graphs. I am wondering whether this also holds for graphs with self-loops.
Here is a Linear Relaxation of the edge cover polytope, ...
- 547
1
vote
0
answers
151
views
Is the matching polytope integral?
In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.
The ...
- 547
1
vote
0
answers
130
views
Separation oracle for hitting all small cut on a graph?
We are given as input an undirected graph $G=(V,E)$, weights $w_e \ge 0$ for all $e\in E$ and an positive integer $k$. We aim to select a set of edges with the minimum weight, such that the cut set of ...
- 451
1
vote
1
answer
87
views
Name of (and solution to) this generalization of linear assignment
I would like to know if the following problem is known and has any efficient solution.
Given an $n\times n$ score matrix $S$. Find the best $a$ elements, in terms of their sum of scores, such that no ...
- 241
2
votes
0
answers
98
views
An integer programming on maximum number of triangles
Consider three distinct sets $A, B, C$ of $N$ elements respectively. For each pair of sets, say $A,B$, we introduce an variable for each combination of values $a,b$ as $x_{ab}$. Similarly, we ...
- 49
2
votes
0
answers
30
views
Finding shortest calculation of the sum of a subset of a group, given sums for other previously summed subsets
Say $S=\{g\in G\}$ is a set of elements in an abelian group $G$ whose group operation $(+)$ is expensive to compute. Given a subset $T\subset S$, we want to compute the sum of $T$'s elements, $\...
- 121
5
votes
0
answers
84
views
Relaxed minimum dominating set
(I moved this question from cs exchange to here, because it might be more on the topic here)
Let $G=(V,E)$ be a directed graph with $n$ nodes. For a subset of nodes $S\subseteq V$, let $\mathcal{N}(S,...
- 639
1
vote
0
answers
12
views
Size of solutions in integer programming
Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
- 12.5k
4
votes
0
answers
87
views
Fixed dimension Linear Integer Programming in $NC$
We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?
- 12.5k
5
votes
1
answer
433
views
Is there a counterexample to this work?
Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However ...
- 12.5k
0
votes
0
answers
135
views
Convex mixed linear integer programming with real nuclear norm objective and linear integer objective
Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
- 12.5k
4
votes
1
answer
226
views
Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?
I'm considering integer programming on an variation of Steiner Forest Problem:
Given a graph $G=(V,E)$, a cost function: $c:E \rightarrow R^{+}$, a terminal set $T \subseteq V$, and a positive ...
- 451
4
votes
1
answer
500
views
Minimum Union-Sum Cost Path
I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path ...
- 175
6
votes
1
answer
201
views
Anti bin packing
I have a (practically) unlimited amount of McDonald's coupons that I can use only if I shop for at least 1 money.
Thus I want to partition my family's meal into as many parts as possible that all ...
- 13.5k
1
vote
0
answers
107
views
Fixed dimension Integer programming minus LLL in fixed parameter $NC$?
If you remove LLL part then is remaining part of
a. Lenstra algorithm
b. Barvinok algorithm
in $O(f(n)(\log(mL))^c)$ time on $O(g(n)(mL)^c)$ processors with fixed $c>0$ in fixed $n$ dimension, $m$ ...
- 12.5k
1
vote
0
answers
110
views
Solving 0/1 integer programming and solving ACC-of-SYM circuits
I am referring to the proof of Theorem 1.4 in this STOC 2014 paper, https://arxiv.org/abs/1401.2444. In particular my question is about the argument that begins in the 8th line of page 9 where the ...
- 1,443
2
votes
0
answers
64
views
Has Khachiyan/Porkolob's convex integer optimization been implemented?
Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
- 12.5k
0
votes
1
answer
77
views
How do minimally violated k-mod cuts work (intuitive explanation)?
As a background, I am not a specialist in theoretical computer science. But I have to take an exam with research-level optimization topics, and I have to learn it on my own, without lectures or tutors....
- 109
4
votes
1
answer
193
views
Have fixed parameter integer program algorithms ever been implemented for research use?
Have any fixed parameter integer programming algorithms described in Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?
- 12.5k
5
votes
0
answers
240
views
What exactly did Lenstra prove on mixed integer linear program?
I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
- 12.5k
1
vote
1
answer
280
views
Max weight travel on a graph with deadline
Given a deadline $D>0$ and a complete graph $K_n$ (with loops) in which each edge $e_{ij}$ has a weight $w(e_{ij}) \ge 0$ and a travel time $l(e_{ij}) > 0$. Starting from one of the nodes, we ...
- 463
1
vote
1
answer
239
views
Fixed parameter tractable Integer Programming and $FPP$
Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $...
- 12.5k
1
vote
0
answers
62
views
Polynomial cases of 0 1 quadratic programm with linear constraints
A pseudo boolean function f:{0,1}^n-> R is defined as f(x)= x^tQx +cx where
Q is a symmetric matrix with null elements in the diagonal. Finding the minimum of this function is solvable in polynomial ...
- 11
3
votes
0
answers
104
views
Fixed parameter Integer Programming circuit depth complexity
It is well known Lenstra's and Kannan's algorithm achieves $n$-variable parameter $L$-bit integer programming solvability in $O(n^nL)$ time and $O(L)$ space.
If implemented as an arithmetic circuit ...
- 12.5k
7
votes
0
answers
330
views
Under what conditions does an Integer Programming problem run in polynomial time?
Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...
- 12.5k
3
votes
1
answer
136
views
Consequences of faster parameterized integer programming
Integer programming in $k$ variables can be done in $k^{O(k)}$ time and $O(k^c)$ space.
Is there any consequence if it can be done in $k^{O(k^\alpha)}$ time and $O(k^c)$ space for some $\alpha\in(0,1)...
- 12.5k
4
votes
1
answer
367
views
Space complexity of integer programming
Given $A\in\Bbb Z^{n\times k}$, $v\in\Bbb Z^n$ and variables $x_1,\dots,x_k$ given as a vector $x$ we know that solving $x\in\Bbb Z^k$ in $Ax\leq v$ is fixed parameter tractable. There is a ...
- 12.5k
5
votes
2
answers
392
views
On integer programming
Integer programming is NP-hard.
What is the status of integer programming problem that decides between existence of $\leq1$ solution and $>1$ solutions (note $0$ solutions falls in $\leq1$ ...
- 12.5k
3
votes
1
answer
233
views
Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K
I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known.
The ...
- 133
3
votes
1
answer
488
views
What are some example problems for integer programming that are *not binary*
I'm interested in NP-hard problems that have a "nice" integer-programming formulation (quadratic or linear, with quadratic or linear constraints) that is not binary.
Of course it is always possible ...
- 319
4
votes
0
answers
319
views
Are there integer programs with small coefficients that only have large solutions?
It is well-known that if an integer linear program has a feasible solution, then it has a feasible solution whose bit size is polynomially bounded. For example, here is Theorem 13.4 from Papadimitriou ...
- 371
1
vote
1
answer
298
views
Is finding an optimal solution to this Knapsack-like problem NP-hard?
Suppose our inputs are a set of objects with weights $w_1,...,w_n$. We have two separate sets of profits: $p_1,...,p_n$ and $v_1,...,v_n$. We wish to maximize $ \sum_{i=1}^{n} p_i(1-x_i)+\alpha_i ...
- 389
3
votes
1
answer
241
views
Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?
I'm wondering which is the approximation class of Minimum 0-1 Integer Programming if only non-negative integers are used. That is:
minimize $c^T \cdot x$,
with $x\in \{0,1\}^n$ and $c\in (\mathbb{Z}^...
- 333
2
votes
0
answers
443
views
How to prove integrality of LP with not totally unimodular matrix
I have a linear program (LP) for which the constraint matrix is NOT totally unimodular (TU). However, even though constraint matrix is small (14x20), extensive generation of random coefficients for ...
- 31
0
votes
2
answers
615
views
NP completeness of linear $0-1$ assignment problem
Supposing we have a linear equation in $n^2$ variables with integer (negatives allowed) coefficients of at most $m$ bits each.
Partition $\Pi_1$ the variables into $n$ disjoint sets of $n$ variables ...
- 12.5k
1
vote
1
answer
250
views
On a Linearization of the Quadratic Assignment Problem
The Quadratic Assignment Problem formulated as an integer program:
\begin{align}
\mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n ...
- 241
2
votes
0
answers
179
views
Runtime of Gomory's Cutting Plane Algorithm
I read in several sources that the use of Gomory's cuts exclusively in Integer Programming was shown to be inefficient in practice when Gomory had created them. But later down the line they were shown ...
- 299
2
votes
1
answer
83
views
Complexity of generating a pseudo-Boolean function
A pseudo-Boolean function is a mapping from $\mathcal{B}^n = \{0, 1\}^n$ to
$\mathbb{R}$.
Following is a pseudo-Boolean function.
$$s_1 s_4 - s_2 s_3 - s_3 s_5 - s_2 s_5 + s_1 + s_4 - s_1 s_3 - ...
- 997
7
votes
0
answers
69
views
Is there a name for this unimodilarity-related property?
Consider an arbitrary integer linear program of the form
$\min f(x,y) \\
@ \ Ax + By \leq c\\
x,y \in \mathbb{Z}_+$
If you continuous-relax the integer constraint and still always get integer ...
- 263
1
vote
0
answers
991
views
Is there a reduction from a 0-1 knapsack problem to the unbounded problem?
As we know, an unbounded knapsack problem could be described as:
$\max \sum_{i=1}^nc_1x_i$
s.t. $\sum_{i=1}^na_ix_i\le b$
$x_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$
And for an 0-1 knapsack problem, we ...
- 11