The integer-programming tag has no usage guidance.
1
vote
0answers
33 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 ...
0
votes
0answers
37 views
All or nothing Integer Multi Commodity Flow
I couldn't find any approximation algorithms for all or nothing integer multi commodity flow. By all or nothing, I mean I wish to maximize the number of commodities fully transferred from their source ...
-2
votes
0answers
14 views
Relaxing quasi convex polynomial requirement?
From https://dl.acm.org/citation.cfm?id=1716350 we know that quasi convex polynomial integer minimization with sets described by quasi convex polynomials is in $P$ in fixed dimensions.
Is it possible ...
4
votes
1answer
275 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 ...
4
votes
1answer
124 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 ...
1
vote
0answers
81 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$...
0
votes
0answers
227 views
Complexity of Quadratic Programming
I'm trying to learn the complexity of a quadratic program in the form of:
minimize:
$f(x,y)=x^2-y^2-4xy$
given only $x*y$
s.t.
$x=a+b$
$y=a-b$
$x+y>3\,\sqrt{xy}$
$x,y,a,b >0$
What I ...
1
vote
0answers
102 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 ...
2
votes
0answers
47 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$ ...
0
votes
1answer
34 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....
4
votes
1answer
157 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?
4
votes
0answers
152 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 ...
1
vote
1answer
164 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 ...
1
vote
1answer
154 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 $...
1
vote
0answers
54 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 ...
3
votes
0answers
101 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 ...
8
votes
0answers
223 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 ...
2
votes
1answer
124 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)...
3
votes
1answer
180 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 ...
6
votes
2answers
303 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$ ...
4
votes
1answer
118 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 ...
2
votes
0answers
176 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 ...
4
votes
0answers
166 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 ...
1
vote
1answer
258 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 ...
3
votes
1answer
223 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}^...
2
votes
0answers
284 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 ...
0
votes
2answers
385 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 ...
1
vote
1answer
153 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 ...
1
vote
0answers
108 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 ...
2
votes
1answer
75 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 - ...
7
votes
0answers
68 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 ...
1
vote
0answers
769 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 ...
-1
votes
1answer
223 views
convertion into integer linear program for Ising spin state problem [closed]
I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp_solve. (This is just a miniature version of Ising state problem)
$$
maximise: \...
7
votes
1answer
104 views
Quanitifier Free Presburger Arithmetic: Upper bound on solution size?
DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question.
According to this paper, if ...
6
votes
0answers
146 views
Are highly symmetric inequalities solvable over integers?
Suppose I have $n$ variables $x_1,\ldots,x_n$ that satisfy some inequalities that are highly symmetric, e.g., for all $S\subset [n], |S|=k$ we have $\sum_{i\in S} f(x_i,k)\le \sum_{i\in [n]} g(x_i,k)$,...
4
votes
1answer
319 views
FPT algorithm for mixed integer program
It is known that every integer linear program parameterized by the number of variables is FPT (fixed parameter tractable). Is every mixed integer program parameterized by the number of integer ...
5
votes
1answer
862 views
Reduction from SAT to 0,1 integer linear program with zero or one solutions
Probably this is well known. There is probabilistic reduction
from SAT to Unique SAT (0 or 1 solutions).
According to answer and comments derandomizing the reduction would imply $PH \subseteq \oplus ...
5
votes
0answers
56 views
Interpolating the Tutte polynomial at the values of two hyperbolas
In a MO question
basically I asked when the Tutte polynomial of planar graph
can be uniquely determined by the polynomially computable values at the special points
and at the two hyperbolas. The ...
2
votes
0answers
90 views
Linear ordering of bipartite tournament graphs
I have an ordered bipartite graph such that every node of the first node set is connected to every node in the second node set by an edge of a given direction (i.e., a so-called bipartite tournament ...
3
votes
1answer
182 views
What is known about this binary representation polytope?
Consider the following set.
$S_n =\{ (x,y) ~|~x \in \mathbb{Z}_+~\wedge~ y \in \{0,1\}^n ~\wedge~x=\sum_{i=0}^{n-1} 2^i y_i \}$
$S_n$ is a collection of pairs $(x,y)$, where $x$ is an integer ...
1
vote
1answer
74 views
Small number of inequalities defining integer hull of integer programming problem
In integer programming problem, we often want to relax the integer programming problem to linear programming problem. So we want to find the integer hull of the problem. The number of inequalities to ...
2
votes
1answer
79 views
Paper about the upper bound of the number of inequalities to describe the Integer hull of a polyhedron
I am interested in the upper bound of the number of inequalities to describe the integer hull of a polyhedron. That is, given an integer programming problem with n inequalities which construct a ...
4
votes
2answers
255 views
Lattice-based algorithms in practice
Are there any applications of lattice-based algorithms other than those in cryptography and integer programming?
Could someone state a few papers where
the primary algorithms use lattice-based LLL ...
2
votes
0answers
209 views
Quadratic Binary Optimization formulation of Steiner Tree problem
can someone point out to me a solution or give advice on how to formulate as efficiently as possible in terms of number of bits the minimum Steiner tree problem as a 0-1 quadratic optimization problem?...
9
votes
2answers
372 views
Exact exponential-time algorithms for 0-1 programs with nonnegative data
Are there known algorithms for the following problem that beat the naive algorithm?
Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers.
Output: an ...
10
votes
2answers
573 views
Exact exponential-time algorithms for 0-1 programming
Are there known algorithms for the following problem that beat the naive algorithm?
Input: A system $Ax \le b$ of $m$ linear inequalities.
Output: A feasible solution $x^*\in \{0,1 \}^n$ if ...
3
votes
1answer
188 views
Efficient flow problem for a complex integer program
I have a bunch of marbles each with some weight (they can also have negative weights). I want to pick the nodes such that the weight is maximized. The only rule is that if I pick X1 and X2 I have to ...
3
votes
2answers
171 views
On facets of 01-polytope
$0,1$-polytopse are fundamental objects in combinatorial geometry and comvex optimization. I am interested in the size of binary representation of hyperplanes to use in the framework of computational ...
0
votes
1answer
1k views
Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem
What is the difference between Multiple Knapsack problem and Multidimensional Knapsack Problem? (http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints) According to the ...
2
votes
0answers
81 views
General covering approximation
Consider the following integer program (general covering):
$\min c \cdot x$ subject to
$Ax \ge b$,
where all entries in $A, b, c$ are nonnegative and $x$ is required
to be nonnegative and integral.
...
