The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
0answers
70 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
273 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 ...
3
votes
0answers
44 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
46 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 ...
0
votes
0answers
43 views

Cut generating linear program in mixed integer lift-and-project cut

In the paper A lift-and-project cutting plane algorithm for mixed 0-1 programs By Egon Balas, Sebastian Ceria and Gerard Cornuejols, a cut generating linear program is introduced: The reason of it ...
3
votes
1answer
156 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
64 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
70 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 ...
0
votes
0answers
64 views

polynomial time algorithm for integer programming with bounded dimension

Can anyone tell me the poly-time algorithm for integer programing with bounded dimension? I am not able to find the exact Lenstra's algorithm in a clearcut manner which elucidates the algorithm ...
4
votes
2answers
204 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
137 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 ...
8
votes
2answers
346 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 ...
1
vote
0answers
252 views

Formulation of the k-TSP as an integer programming problem?

Specifically, in a complete graph, I'm trying to find the simple path with $k$ nodes that minimizes the sums of their vector edge weights. Additionally, the solution should be Pareto efficient ...
10
votes
2answers
516 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
175 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
131 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
418 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
76 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. ...
4
votes
0answers
168 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
176 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
750 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
107 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
234 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
501 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
99 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
505 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
390 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
93 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
342 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 ...
17
votes
2answers
1k 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 ...
14
votes
0answers
252 views

Any example of an unsatisfiable integer program with non constant Rank Lower bounds for LS+ cuts but with short LS+ refutations?

Assume we want to refute an unsatisfiable CNF. We can interpret it as an integer program, thus a refutation can be done by applying Lovasz-Schrijver semidefinite cuts ($LS_{+}$ cuts) to its linear ...
7
votes
2answers
694 views

Integer Factoring via Lattice Reduction?

I found a paper titled "Factoring integers and computing discrete logarithms via diophantine approximation" by C. P. Schnorr from 1993. It looks like a probabilistic method with expected polynomial ...
22
votes
3answers
738 views

What is known about solutions to sparse integer linear programming problems?

If I have a set of linear constraints in which each constraint has at most (say) 4 variables (all nonnegative and with {0,1} coefficients except for one variable that can have a -1 coefficient), what ...