The integer-programming tag has no wiki summary.
-1
votes
0answers
28 views
Are all Integer Linear Programming problems NP-Hard? [migrated]
As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
2
votes
0answers
53 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.
...
-3
votes
0answers
14 views
two's complement integer [migrated]
Can someone explain in plain English what does two's complement integer mean? I read it in in JAVA long is a 64-bit signed two's complement integer
I probably ...
4
votes
0answers
93 views
How to determine proper rounding in linear programming relaxations?
Recall that in the vertex cover problem we are given an undirected graph ${G=(V,E)}$ and we want to find a minimum-size set of vertices ${S}$ that “touches” all the edges of the graph, that is, such ...
3
votes
0answers
92 views
Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables
Integer programing is one of the most narutal optimization tools.
As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation.
$x_{1}x_{2}x_{3}+$ ...
8
votes
2answers
349 views
Integer programming with a fixed number of variables
The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of ...
4
votes
0answers
88 views
LP-type vs. Approximation
I'm interested in an computational geometry problem that's sensibly expressed as an infinite dimensional 0-1 integer program. I'm not worried about finding an actual minimum for the objective ...
3
votes
3answers
125 views
Facility location problem with a cost function
I'm struggling with a facility location problem.
In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from ...
11
votes
4answers
408 views
Is 0-1 programming with constant number of constraints polynomially solvable?
It was shown in the paper "Integer Programming with a Fixed Number of Variables" that integer programmings with constant number of constraints (or variables) are polynomially solvable.
Does this hold ...
6
votes
0answers
93 views
Deterministic Parallel Algorithm for ILP with small number of variables and small coefficients
Given a set of $n$ linear inequalities in $d$ variables where the coefficients are integers of size bounded by $O(\log{n})$ is there a known deterministic parallel algorithm that runs in time ...
0
votes
2answers
375 views
Minimal non-negative linear combination of positive integers larger than a positive integer
The problem is the following:
We have a positive integer $w$. A set of positive integers $A$ such that $\forall a \in A$ it's true that $a \leq w$. We search for the minimal integer $x$ such that $w ...
1
vote
2answers
311 views
Known sparse integer programming problems
I am studying the properties of sparse integer programming problems, Would like to know if there are any interesting known problems of that type ?
I would define sparse problems as problems that have ...
5
votes
0answers
89 views
Quantized Unbounded Flow
I am interested in the following flow problem, since it turns out to be equivalent to a more general problem.
INPUT: A graph where each edge $e$ has an integer multiplier $q_e$, and a lower bound ...
3
votes
1answer
289 views
Applications and benchmarks for binary quadratic program algorithms
I have an algorithm that on all examples I was running finds an arbitrary approximation of global minimum of binary quadratic program. The algorithm find the minimum in polynomial time. Binary ...
15
votes
2answers
720 views
How fast can we solve a totally unimodular integer linear program?
(This is a follow-up to this question and its answer.)
I have the following totally unimodular (TU) integer linear program (ILP). Here ...
