Questions tagged [integer-programming]
The integer-programming tag has no usage guidance.
239
questions
0
votes
0
answers
37
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 ...
0
votes
3
answers
36
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 ...
1
vote
1
answer
76
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 ...
- 127
1
vote
1
answer
44
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.♦
- 154k
5
votes
1
answer
218
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 ...
- 127
1
vote
2
answers
279
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
33
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 ...
- 235
1
vote
1
answer
51
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 ...
- 11
0
votes
1
answer
102
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
71
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
43
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
39
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
44
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 ...
- 290
2
votes
1
answer
121
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
48
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
87
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 ...
- 313
1
vote
1
answer
683
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
22
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 ...
- 195
1
vote
1
answer
41
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
68
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
65
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 ...
- 83
0
votes
1
answer
125
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
54
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
36
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
19
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
0
answers
42
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.♦
- 154k
1
vote
0
answers
195
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
103
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
3
votes
1
answer
316
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 ...
- 33
1
vote
1
answer
46
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
42
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
169
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
304
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 ...
- 258
1
vote
1
answer
105
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
306
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
$$
\...
- 2,933
3
votes
1
answer
524
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
41
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
191
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
4
votes
3
answers
353
views
Algorithm for solving a mixed integer programming problem in polynomial time?
I have the following mixed integer programming (MIP) problem:
$$
\begin{array}{rll}
\text{Maximize } & z=k \\
\text{subject to }
& a_ik - m_i \geq 0 & (i=1,\dots,n) \\
& b_ik - m_i \...
- 91
0
votes
1
answer
344
views
XOR Statement in integer programming
How can I convert a XOR statement into linear constraints for integer programming ?
The expression is $(x_1 \geq 1)$ XOR $(x_2 \geq 1)$ where $x_1$ and $x_2$ are integer. It means that if $x_1 \geq 1$ ...
0
votes
1
answer
104
views
Convert an IF statement in Mixed Integer Programming
I want to convert an IF statement for my optimization problem. I want to minimize the total price. I want 800 tones of salt and 3 suppliers offer me their prices.
Supplier $1$ offers me $100$ tones at ...
0
votes
1
answer
78
views
Combinatorial optimization algorithm with constraints and objective function
I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function.
.e.g
Say each ...
- 103
0
votes
0
answers
36
views
IF THEN condition in Linear Program
I have the following condition in an LP problem. I have a variable $x_i \in i = 1,2,..7$ and I need to constrain the problem via:
if $x_1$ >5 then $x_2 \leq 30$
I'm stumped on how to formulate that ...
- 1
2
votes
1
answer
52
views
What is the best algorithm to find the optimal path in reducing company's real-estate footprint?
I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.
Here is the problem: A company is in ...
- 23
1
vote
0
answers
35
views
IP Programming - objective function ist not a function BUT a table
Here is a short description of my problem:
Part of my objective function is not a regular function. Instead it's a table.
You can see a short extract here:
So if the height is smaller or equal to 300 ...
- 11
2
votes
2
answers
99
views
Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time
I have a system that consists of binary inequality constraints between variables, plus some indicator variables that can assume only two values:
...
- 23
0
votes
1
answer
133
views
Integer programming with indicators
I have the following question, and I need to write it as an integer programming problem:
A manager of a company wants to by presents to his 100 employers. He can buy the presents from two different ...
- 119
0
votes
0
answers
66
views
Efficient triangular decomposition of an integer
Euclidean division is an iterative process
that has been made super-efficient at the CPU level, right?
Its specification is that if I do (q, r) = f(n, d), I get ...
- 195
0
votes
0
answers
40
views
Formulating if-then constraints in linear binary programming
From a stock of various computer accessories of different brands, the optimization problem requires deciding to keep or discard products. The decision should be made maintaining the following if-then ...
1
vote
2
answers
235
views
Linear programming vs integer linear programming
Given $A,b$, let $Ax \le b$ be an instance of linear programming on the variables $x=(x_1,\dots,x_n)$. Assume that the constraints $0 \le x_i$ and $x_i \le 1$ are included in $A,b$.
Suppose that ...
D.W.♦
- 154k