The tag has no usage guidance.

learn more… | top users | synonyms

4
votes
0answers
46 views

Brute Force Search Algorithm for Semidefinite Programming (Representation of Spectrahedron)

I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for ...
2
votes
0answers
137 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
88 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
194 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 ...
0
votes
0answers
22 views

On the Continuous Relaxation of the Quadratic Assignment Problem

Consider the Quadratic Assignment Problem: Minimize $$\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 c_{ijkl}x_{ij}x_{kl}$$ subject to $$\sum_{i=1}^n x_{ij} ...
0
votes
0answers
88 views

An approximate optimization algorithm

Let $f(n)$ be the number of bits for representing natural number $n$: $f(n) = \lfloor \lg n + 1 \rfloor$. I am looking for an efficient algorithm for the following problem: Input: $w_1, w_2, \cdots, ...
2
votes
1answer
188 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
75 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
295 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
74 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 ...
0
votes
0answers
36 views

Complexity of fixed fractional relaxations

I recently stumbled upon a curious relaxation of a combinatorial problem that was restricted to a fixed subset of fractional solutions. I am now wondering if the complexity of such constrained ...
1
vote
0answers
68 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
73 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
62 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
177 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
163 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: \...
6
votes
1answer
90 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
137 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
0answers
149 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
472 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 ...
4
votes
0answers
54 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
68 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
176 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
69 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
77 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
235 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
180 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
362 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
548 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
185 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
147 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
960 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
80 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
380 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
206 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}+$ $x_{3}x_{4}x_{...
10
votes
2answers
1k 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
135 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
296 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
601 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 ...
7
votes
0answers
110 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 $(d\log{...
0
votes
2answers
567 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
504 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
98 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
366 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 ...
18
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 $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$...
14
votes
0answers
259 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
774 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
932 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 ...