Questions tagged [integer-programming]
The integer-programming tag has no summary.
251 questions
2
votes
1
answer
50
views
Maximum cardinality matching with a priority order
Problem Setup
Let's say we have a bipartite graph $(U, V)$ where the nodes of the graph are labelled with a positive integer and each edge $(u_i, v_i)$ has $u_i < v_i$. Our goal is to find a ...
- 105
0
votes
1
answer
102
views
Multiply by zero or one in ILP
Suppose $x,y$ are continuous variables, and $z$ is a zero-or-one integer variable, in an ILP instance.
How can I enforce the constraint $x = yz$ with linear inequalities? Equivalently, I want to ...
D.W.♦
- 169k
1
vote
2
answers
88
views
How to invert feasibility of an ILP without solving it
Given an ILP, e.g., $Ax\leq b$, is there some transformation you can apply to it to obtain another ILP that's feasible iff $Ax\leq b$ is infeasible? In particular, a transformation that doesn't ...
- 23
1
vote
1
answer
235
views
Can this Integer Linear Programming problem be solved in polynomial time?
I have $n$ binary variables, and $m$ constraints. Each constraint can be stated as: "exactly $b$ of the variables in $S$ are equal to 1", for some positive integer $b$ and subset of the ...
- 13
2
votes
2
answers
122
views
Generalizations of integer-programming for the polynomial hierarchy?
Integer programming is known to be NP-complete. We also know that each class in the polynomial hierarchy contains elements not contained in the ones below, so Integer programming is not complete for ...
- 4,284
2
votes
2
answers
261
views
Approximation algorithm for binary (linear) programs
I am interested in solving the following problem:
$$
\max c^\top x \qquad\text{s.t.}\\
Ax \le b\\
x \in \{0,1\}^n
$$
One can assume that $c$, $A$ and $b$ have integer entries if that simplifies things....
- 555
2
votes
1
answer
177
views
Proof of NP-hardness: Is the problem of finding the minimum edge-weighted subgraph with at least M pairwise connectivity NP-hard?
Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and a positive integer $M$, the problem asks to determine the minimum-weight set of edges $S\subseteq ...
- 61
2
votes
2
answers
276
views
Approximation algorithms for integer convex quadratic programs over a linear subspace
Consider the problem
$$
\min_x \frac{1}{2} x^\top Q x + c^\top x \qquad \text{s.t.}\\
Ax=b\\
x \in \mathbb{Z}^n
$$
where $Q$ is a positive (semi)definite matrix.
Clearly, feasibility can be decided in ...
- 555
5
votes
2
answers
162
views
Run-time complexity of solving a system of integer linear equations
Given an integer $n$-by-$n$ matrix $A$ and an integer $n$-by-$1$ vector $b$, what is the run-time complexity of finding an integer solution $x$ to the system $A x = b$?
In general, integer linear ...
- 6,087
0
votes
1
answer
83
views
Regular branch and bound vs integer programming branch and bound
In the context of linear integer programming, we have a branch and bound algorithm described here. This involves solving the non-integer constrained linear program and successively introducing ...
- 397
0
votes
0
answers
58
views
Placement of Tasks from Dataflow Graph on a Physical Graph
I have a dataflow graph where a set of different types of tasks are placed in corresponding types of nodes.
Say the task types are called A, B, and C.
A-type tasks are placed in all the leaf nodes of ...
- 1
3
votes
1
answer
136
views
What is the complexity of minimising a convex quadratic function over the integers?
The problem of interest is
$$
\min_{x\in\mathbb{Z}^n} \frac{1}{2}x^\top Q x + c^\top x
$$
where $Q$ is a positive definite matrix. I am reasonably sure this can't be solved in poly-time, since the ...
- 387
0
votes
0
answers
70
views
Complexity of $a\binom{x}{2} +by = c$
Manders and Adleman showed that it is NP-complete to decide given integers $a, b, c \geq 0$ in binary encoding whether $ax^2 + by = c$ has a solution over the non-negative integers. What is known ...
- 31
1
vote
3
answers
124
views
Which algorithms could be suitable for solving my disjunctive programming problem?
Following a previous post on the cs stack exchange (link to question), I have been searching to no avail for an implementation of a disjunctive programming solver in C# (or wrapped in C#). In this ...
- 13
1
vote
1
answer
177
views
Integrality gap and complexity classes
I would like to know if there exist some complexity classes that are defined according to the integrality gap of their problems?
In particular, is there a class of problems for which their integrality ...
- 269
2
votes
1
answer
377
views
Boolean constraints for a connected component of a graph
Suppose I have an undirected graph $G=(V,E)$, and boolean variables $x_v$ (one for each vertex $v \in V$). These variables select a subset $S \subseteq V$ of vertices, namely the vertices $S=\{v \mid ...
D.W.♦
- 169k
8
votes
2
answers
403
views
Can we compute in polynomial time, an upper bound on an optimal solution of an integer linear program?
Consider the following integer linear program (where $A$ is an integer matrix, $b$ an integer vector, and $c$ a positive integer vector):
$$
\text{minimize}~~~ c\cdot x
\\
\text{subject to}~~~ A\cdot ...
- 269
1
vote
2
answers
534
views
Can the optimization version of a problem be NP-hard while its decision version is in P?
I have formulated an instance of a 0-1 Integer Program (IP), which I am trying to determine the complexity of (can this instance be solved in polynomial time or not). As we know, the 0-1 IP is NP-...
1
vote
0
answers
62
views
Are there any Indicators that this specific Integer Linear Program is solvable in polynomial time
I have a pretty complex problem and I am using a rather complex ILP to solve it. In a special case of the problem the ILP is reduced to the following "simple" ILP. Additionally, I know that ...
- 265
0
votes
1
answer
142
views
Given required total area and capacity, choose an amount for each of three given modules
Suppose you have three modules $m_1,m_2$ and $m_3$, each with a capacity of $c_i$ and area $a_i$. You are also given $A$ and $C$. How can you find some of the solutions to choose an amount of each ...
- 9
0
votes
1
answer
148
views
To write an IP and relax it to LP for finding a multi-set in a graph
I am new to Linear Programming and Approximation algorithms. and I am trying to do this exercise for writing an IP and relax it to LP. What I am given:
A digraph ...
- 25
1
vote
1
answer
344
views
Boolean Integer Linear Optimization/Programming
Trying to solve an ILP optimization problem with a number of potential boolean variables and then express constraints on these variables based on those boolean results.
Let's say I am doing 5 coin ...
- 11
2
votes
1
answer
84
views
minimum number of 2d elements whose sums across both dimensions satisfy some threshold
I have the following problem formulated as a linear integer program:
\begin{align}
& \text{minimize} && \sum_{i \in n} x_i\\
& \text{subject to} && \sum_{i \in n}{a_i}x_i \ge ...
1
vote
1
answer
109
views
Modified set cover to identify "orthogonal" partitions
Setup
I have a non-empty set of elements $U$ that are arranged spatially.
I would like to partition $U$ into $N$ non-empty, disjoint subsets, $A_i$, having up to $M$ elements each. Each subset is only ...
- 11
1
vote
1
answer
119
views
Possible to solve a combinatorial game with integer programming?
I recently had the idea that it would be neat if it were possible to make a SAT solver play combinatorial games. To start, I'm trying a relatively simple case of solving single-stack Misère Nim ...
- 310
2
votes
1
answer
242
views
Integer linear programming formulation of boolean selection
Given a boolean variable $x$ and nonnegative integer variable $s$, I want to select $y = \begin{cases}
0 & \text{if} \ x = 0 \\
s & \text{if} \ x = 1
\end{cases}$.
Currently in the ...
- 21
1
vote
1
answer
98
views
Why do we round from 1/2 when converting the LP to ILP for the weighted vertex cover problem?
I understand that to approximate a solution to the weighted vertex cover, we need to relax the integer linear program to a linear program which can be solved in polynomial time, but why do we round ...
- 13
1
vote
0
answers
134
views
Solution methods for this Weighted Partial Set Cover-ish problem
Given a set of subsets $S_1, ..., S_N$ of a finite universe $E$ of elements $e_1, ..., e_n$ and mapping of those elements to an integer 'weight' $w_1, ... w_n$, select the subset of subsets which ...
- 383
1
vote
1
answer
2k
views
If greater than or equal to zero then binary variable equals 1: integer linear program
I have a variable $d_{i} \in \mathbb{Z}$ with an upper and lower bound. I also have a binary variable $v_{i}$ which I want to $=1$ if $d_{i} \geq 0$; else $v_{i} = 0$. How do I enforce this as a ...
- 23
0
votes
0
answers
41
views
Finding all integer solutions of an equality
I want to generate all solutions of $x_1+x_2+\ldots+x_{100}=6$ where $x_i$s are non-negative integers. Finding the number of such solutions is not difficult. But is there any easy way to get all ...
- 205
1
vote
1
answer
158
views
Can't figure out decision variable
Good Evening, I am trying to solve an exercise related to my algorithm designing course. I have understood the question and what it asks. I am required to formulate an ILP and then relax it to ...
- 25
0
votes
0
answers
138
views
ILP - Maximize the number of pairs of variables with the same value
I have a 0-1 integer linear program for a set of $2n$ variables $S = \{x_1, ..., x_n, y_1, ..., y_n\}$. My objective is to maximize the number of pairs $(x_i, y_i)$ such that $x_i = y_i$, $i = 1, ..., ...
- 143
1
vote
0
answers
87
views
Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?
The standard LP gap example for the held karp relaxation for TSP
min $ c^tx $
$x(\delta(S)) \geq 2 $
$x(\delta(v))=2 $
$x \geq 0$
Is to have two triangles and three long paths connecting the ...
- 155
0
votes
1
answer
342
views
Is integer multicommodity flow problem is NP-hard?
As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?
- 1
0
votes
1
answer
119
views
Encoding a binary sequence with shift in MILP
I would like to know if it's actually possible to encode a (binary) sequence with rotations in MILP/MIP.
Given a binary sequence $(0,1,1,0,0,0,0,1)$ and variables $x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7$
I ...
- 1
1
vote
0
answers
75
views
Selecting sets that maximise the cardinality of the union minus the cardinality of the difference
I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows.
$$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
- 23
0
votes
0
answers
41
views
Selecting five binary vectors that when multiplied elementwise are most similar to another vector
I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows.
$$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
- 23
2
votes
1
answer
80
views
Path that stays within a convex polyhedron
Let $\mathcal{P},\mathcal{Q}$ denote two convex polyhedra in $\mathbb{R}^d$, which can be represented by a set of linear inequalities. Let $A \subset \mathbb{R}^d$ be a finite set of vectors.
The ...
D.W.♦
- 169k
1
vote
0
answers
242
views
Fixed Parameter Tractable for Special Vertex Cover using ILP
The problem I'm trying to solve reads as follows:
Given a graph $G=(V,E)$ ,a parameter $k$ and two values $U^\star, P^\star \in \mathbb N$, where every vertex $v\in V$ has a utility and a pollution $...
- 317
2
votes
2
answers
243
views
Efficient Algorithm to Find the Closest Integer Representation, in the Form $A\times\frac{N}{D}$ for a Value
The Problem
I am working on a problem that boils down to finding the closest representation of an arbitrary number ($x$) in the form:
$$x = A\times\frac{N}{D}$$
Where $A$ is a 32-bit integer, and $N$ ...
- 123
4
votes
1
answer
817
views
Why is it useful to transform 0-1 integer programming problem into SAT problem?
There are several researches studying translating 0-1 integer programming into CNF form. For example, this paper and this C++ library. As the lecture notes here goes, translating 0-1 integer ...
- 43
1
vote
1
answer
76
views
Find optimal play by optimizing orders of each player alternatingly
A zero-sum game for two players allows a player to take no action during a turn. Can I reach optimal play (where both players always choose the best possible action in each turn) by the following ...
- 113
2
votes
0
answers
87
views
Efficient solution to this scheduling problem or integer optimization problem
Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to
$$
P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)}
$$
where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\...
- 225
1
vote
2
answers
299
views
Linear program for min-length pair of edge-disjoint paths problem
Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, ...
- 158
1
vote
1
answer
671
views
Reduction from SUBSET-SUM to 0-1-INT-PROG
The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$.
I am trying to prove that 0-1-INT-PROG ...
- 288
1
vote
1
answer
167
views
Converting 4 variable if else condition to Linear integer program
There are four variables: $x_1, x_2, x_3, x_4$.
If you choose either $x_3$ or $x_4$ or both — then you should choose exactly one of $x_1$ or $x_2$.
If you choose neither $x_3$ or $x_4$ — then there is ...
2
votes
2
answers
588
views
Maximum weight perfect matching in general graphs
Let $G(V,E)$ be a graph (not necessarily bipartite), where edge $e \in E$ has weight $w_e$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows
$$
\...
- 3,413
5
votes
1
answer
1k
views
When LP solution is ILP solution?
For many discrete problems, it's natural to consider their continuous relaxations. A common case is when instead of $x_i \in \{0, 1\}$ we allow $x_i \in [0, 1]$. In certain cases, the original problem ...
user114966
2
votes
1
answer
72
views
Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program
I am trying to solve an LP in which one of the constraints is mentioned below,
$$\max(x_1,x_2) \ge q,$$
where $x_1 \ge 0$ and $x_2 \ge 0$.
Is it possible to do in linear programming?
3
votes
2
answers
287
views
Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$
I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a_1, \ldots, a_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b_1, \...
- 133