Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [integer-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1
votes
0answers
24 views

Approximation quality of a simple linearization of binary quadratic program

I am trying to linearize a binary quadratic program by a simple linear inequality i.e. for the given objective $\mathbf{\min_{x \in \{0,1\}^n} x^TAx}$, I want to linearize the objective by using ...
0
votes
0answers
46 views

choosing the best subset where the metric is based on pairwise relationship

I want to model the competition between agents. Say there is a set of agents, and at each time step each agent $i \in \{0,1,\cdots, n-1\}$ can select a nonnegative number $x_i$ from a given range $[0,...
0
votes
0answers
49 views

What is the complexity of Parametric Mixed Integer Linear Programming?

We know $$\forall\bf y\in\mathbb Z^n:K\bf y\leq b$$ $$\exists\bf x\in\mathbb Z^m:A\bf x + B\bf y\leq c$$ is in $\bf P$ if $n,m$ are fixed from Kannan's result (refer page $1$ in reference). What is ...
0
votes
0answers
19 views

The set of weight functions for which the assignment problem has non-trivial solutions

The standard assignment problem is specified with a square matrix ${\bf W}$ of weights (values, costs): $$ V_{\cal P} = \sum_i w(i, b(i)) = \sum_{(i, j) \in {\cal P}} w_{ij}, $$ where $\cal P$ is a ...
1
vote
0answers
11 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 $\...
4
votes
1answer
442 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 ...
2
votes
1answer
291 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
83 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$?
4
votes
1answer
406 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 ...
0
votes
0answers
125 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$ ...
3
votes
1answer
113 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 ...
2
votes
1answer
2k views

Solve a simple system of linear inequalities in natural numbers

I want to find a solution to a system of linear inequalities of the following form \begin{aligned} a_1 + b &\ge a_2 \\\ \vdots \\\ a_4 + c &\ge a_1 \end{aligned} where $a_i \in \mathbb N \...
4
votes
1answer
139 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 ...
2
votes
0answers
60 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$ ...
1
vote
0answers
95 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$...
1
vote
0answers
106 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 ...
0
votes
1answer
44 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
177 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?
13
votes
3answers
825 views

Which Integer Linear Programs are easy?

While trying to solve a problem, I ended up expressing part of it as the following integer linear program. Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ are all positive ...
4
votes
0answers
185 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
204 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
185 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 $...
3
votes
0answers
103 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 ...
1
vote
0answers
59 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
1answer
230 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 ...
7
votes
0answers
273 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 ...
21
votes
3answers
2k 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$...
3
votes
1answer
130 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)...
5
votes
2answers
362 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$ ...
2
votes
1answer
140 views

Can Lenstra's algorithm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k?

It is well-known that Lenstra's famous algorithm (presented in the paper Integer programming with a fixed number of variables) can solve an ILP problem in $O^*(f(k))$ time where k is the number of ...
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 ...
3
votes
1answer
137 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 ...
4
votes
1answer
375 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 ...
1
vote
1answer
269 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 ...
4
votes
0answers
254 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 ...
3
votes
1answer
227 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}^...
1
vote
1answer
209 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
2answers
436 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 ...
2
votes
0answers
389 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 ...
7
votes
0answers
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 ...
2
votes
1answer
77 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 - ...
2
votes
0answers
141 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 ...
1
vote
0answers
914 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
251 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
111 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
150 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)$,...
5
votes
1answer
1k 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
57 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
96 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
186 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 ...