Questions tagged [integer-programming]
The integer-programming tag has no summary.
93 questions
2votes
1answer
58views
Extension of 0-1 Knapsack problem with weight reduction
Given a 0-1 subset sum instance $\langle n, \{v_i\}_{i=1}^n, \{w_i\}_{i=1}^n, W \rangle$, I'm interested in an extension where one can additionally choose nonnegative scalars $\{c_i\}_{i=1}^n$ such ...
0votes
0answers
106views
$\mathsf{GCD}(a,b)\not\in TC^0$ while fixed dimension feasibility $ILP$ is in $TC^0$ consistent with our knowledge?
The reduction from $\mathsf{GCD}(a,b)$ is to do binary search on the feasibility of program $$r_1<au+bv<r_2$$ $$u,v\in\mathbb Z$$ where $a,b$ are given integers and we do binary search with ...
- 13.5k
1vote
0answers
44views
How to find costs to an integer program that maximize integrality gap
This is a cross-post from the Operations Research stackexchange. Let $A \in \mathbb{Z}^{m \times n}$ and $b \in \mathbb{Z}^m$. For $c \in \mathbb{R}^n$, let \begin{align} \text{ILP}(c) = \max \quad &...
- 190
0votes
0answers
36views
Nonexistence of short integer program sequence which generates squares - II
Is there a way to show within a mixed integer linear program with constant number of integer variables, $poly(\log B)$ number of real variables and constraints of length $poly(\log B)$ (say length $\...
- 13.5k
0votes
0answers
52views
Integer Program where an integer optimal solution is an extreme point of the LP Relaxation
Let RLP $\equiv$ (Linear relaxation of the Integer Program). In general, Integer Programming is NP-hard. $~$And often, an integer optimal solution will lie in the interior of the feasible space of the ...
1vote
0answers
174views
What is a "strongly complementary pair" of primal/dual solutions to a linear program?
While trying to understand this paper by Hammer, Hansen and Simeone, I came across some terminology I was unfamiliar with: the notion of a "strongly complementary pair". For a linear program ...
2votes
0answers
95views
Parallel complexity of fixed dimension fixed constraints integer programming
Papadimitriou in https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf shows ILP is fixed parameter tractable in number of constraints and Lenstra in https://people.csail.mit....
- 13.5k
0votes
0answers
136views
Separation oracle for breaking cycles in directed graph
I am working on a directed graph problem and am collaterally interested to know whether there is a separation oracle for the following set of linear constraints. We are given a directed graph $G$ ...
2votes
0answers
178views
Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?
Given a graph $G=(V,E)$, costs $c \in \mathbb{R}^E$ the TSP problem is to compute a min cost tour of the graph. The LP is min $ c^tx $ $x(\delta(S)) \geq 2 \ \ \ \ \forall S \subset V $ $x(\delta(v)...
- 219
2votes
1answer
161views
Hardness of computing the dimension of an integral polytope?
Given a set of linear inequalities $Ax \leq b$ let $P = \text{conv}\{x \in \{0,1\}^n \mid A x \leq b \}$ be the convex hull of all binary vectors that satisfy the given inequalities. I am interested ...
- 190
2votes
1answer
140views
Do there exist two equivalent objective functions one of which can be approximated but another one cannot?
I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...
user53330
3votes
1answer
377views
How hard is this combinatorial optimisation problem?
Suppose we have multiple intervals $R_1,R_2,...,R_i$ of non-negative integers. These intervals may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th interval $R_h$, ...
user53330
2votes
1answer
294views
Characterization of integral polyhedra
A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$. Equivalently, $P$ is integral if ...
- 649
8votes
3answers
869views
Is that edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard? Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
- 563
6votes
1answer
408views
Is this edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard? Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\...
- 563
