Questions tagged [integer-programming]
The integer-programming tag has no summary.
251 questions
0
votes
2
answers
233
views
Interview question (constant-time algorithm, ILP)
A juice machine has three buttons small, medium large. Each size adds an amount of juice in a range to the cup. Eg small might add from 10-20 mL, medium from 30-35 mL, large from 40-50 mL. The exact ...
- 11
1
vote
1
answer
5k
views
Expressing conditional in linear program [duplicate]
I have two variables $A$ and $B$, with $A$ being binary and $B$ is a real number where $B \ge 0$. My conditions are:
if B > 0
A = 1
else
A = 0
...
- 229
-1
votes
1
answer
3k
views
Prove that Integer linear programming (ILP) is in NP
Help is needed, I've tried to solve it by myself but I could find any reasonable solution which is solid enough. this is what I've wrote:
Consider a 0-1 ILP, where each variable x1,x2...,xn can ...
- 131
0
votes
0
answers
66
views
How to monitor and alter the value of decision variables using if then else
Assuming I have two 0-1 decision variables X[a,b] and Y[i,j,e,d] where :
X[a,b] = 1 if a is in b 0 otherwise
Y[i,j,e,d] = 1 if (i,j) is matched with (e,d) 0 otherwise.
I need to ensure that if ...
- 113
2
votes
3
answers
593
views
Modification of dynamic programming for a knapsack problem
We have the following recursive function for the dynamic programming problem for a knapsack problem:
\begin{align}
V(i,w)=&max[ V(i-1,w), v_i +V(i-1,w-w_i)], \quad 1\leq i \leq n, 0\leq w \leq W \...
- 45
4
votes
1
answer
1k
views
Is 0-1 integer linear programming with only equality constraints NP-Hard?
We know that 0-1 integer linear programming is NP-Hard. What about 0-1 integer linear programming with only equality constraints? If so, how to prove it?
$$\mathsf{min\ c^T x }$$
$$\text{ s.t. } \...
- 61
1
vote
3
answers
476
views
Solving a discrete optimization problem
Assume that $x_1,\dots,x_n$ are $n$ integer variables which takes values in a subset of given numbers, say $x_i\in\{5,6,\dots,5000\}$. Let $f_i(x_i)$ and $g_i(x_i)$ both be non-decreasing non-negative ...
- 115
2
votes
1
answer
602
views
Aggregate planning with inventory
I am lost in formulating a mathematical model for my linear integer program. My problem is; how to include inventory and backlogging.
The following is given:
1100 units can be produced each month
...
- 45
1
vote
2
answers
395
views
Linear programming with inequality constraints treated lexicographically
I'm trying to solve optimization problems of the form: $\min\{cx|Ax\preceq b,\;x\geq 0\}$, where $\preceq$ means lexicographic order; that is, the set of linear inequalities need only to be satisfied ...
- 11
3
votes
1
answer
90
views
Estimate complexity of integer sequence enumeration
I would like to seek help on the complexity of the following problem. Given positive integers $m$, $n$, $D_1$ and $D_2$, find all sequences $a_1\lt a_2 \lt \dots \lt a_n$ are there such that:
each $...
- 43
1
vote
0
answers
45
views
Exploiting solution property in MIP
I am having to solve integer programming problem that has the following property:
For feasible solution $x$ maps to a large set $S(x)$ or other admissible solutions and I can find the best solution ...
- 151
2
votes
0
answers
64
views
Static management of dynamic memory
I have some issue but I can't identify a way to solve it. I wanted to ask you what kind of problem it is?
We have a resource - contiguous computer memory. Also we have users which require some ...
- 121
2
votes
1
answer
114
views
Choose N pairs of (job, time slot) with a constraint on the number of different jobs
I am making a solver to choose the best assignment to a set of people for an event, given their availability (chosen in a set $T$ of time slots), jobs preferences (among $J$ possible jobs) and some of ...
- 123
0
votes
1
answer
177
views
how to express an intertemporal implication constraint in integer linear programming (ILP)?
I want to express the following locigal expression in an IP:
$$x_{di} \wedge x_{d'j} \Rightarrow \sum_{\substack{d'' \in D\\ i < k <j}} x_{d''k} = \sum_{i<k<j} a_{k} \ \forall \ d, d' \in ...
- 103
3
votes
2
answers
464
views
Model disjunction in a $\{0,1\}$ integer linear program
How can I model logical OR as an integer linear program?
$$(y_3 + y_4 + y_5 + y_6 = 2) \lor (y_2 = 1)$$
where $y_i \in \{0, 1\}$, $1$ = True and $0$ = False.
- 131
0
votes
1
answer
880
views
Efficiency of 0-1 linear programming w.r.t. number of binary variables
I am working on a problem in which I have to solve 0-1 linear programs, that is linear programs where some of the variables are binary, i.e. either 1 or 0.
Lets say I have a fixed number of $n$ ...
- 140
0
votes
0
answers
40
views
Scheduling problem with performance based selection
I would like to solve a scheduling problem where, I am able to maximize the number of consecutive shifts a employee may have, therefore minimizing the likelihood of them not showing up for a single, ...
- 1
1
vote
0
answers
229
views
How to model the constraint of a circle placement problem mathematically?
I have a circle with radius $R$ and $N$ points on a 2D plane with known locations $(x_i,y_i), i=1,2,..N$. I want to place the circle such that it maximizes the number of covered points.
Let $d_i=(x_i-...
- 41
1
vote
1
answer
134
views
Computational Complexity of Integer Linear Program [with Fixed number of 'Pure Constants']
This is a follow up to the previous Question: Conditions for Linear Diophantine Equations to always have a solution
It was established in the above's answer that obtaining or testing for the ...
- 799
3
votes
1
answer
352
views
Conditions for Linear Diophantine Equations to always have a solution
Given a set of $n$ linear equations in $v$ integer variables, where $v > n$, we can say that this system of equations will always have an integer solution.
Over $\mathbb N$, is there any such ...
- 799
2
votes
1
answer
5k
views
Converting if-then-else condition to integer linear programming with equality constraints
I have an if-then-else condition with three binary variables $A$, $B$ and $C$:
if A = 1
then B = 1
else
B = C
How do I express this as an ...
- 229
5
votes
2
answers
1k
views
Approximate subset sum with two-dimensional vectors
Consider the following optimization problem:
Given $n\leq 10^3$ vectors $v_i\in\mathbb{R}^2$, all of which are small, i.e., $\|v_i\| \leq 1$, find a subset $S$ of them that minimizes
$ \| w + \...
- 195
2
votes
1
answer
175
views
Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function
A boolean-valued function defined in the set of positive integers, $\mathcal Z$.
$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$...
4
votes
1
answer
321
views
Efficient algorithm for simple constraint satisfaction problem
There are
$k$ Boolean variables $x_1, x_2, \dots, x_k$.
$m$ arbitrary subsets of these variables such that sum of each set equals to $1$ (i.e., only one variable is $1$, the others are $0$). E.g., ...
- 83
1
vote
1
answer
93
views
Maximizing the boolean combination of given real numbers with dependencies
Let $x_i,x_{ij}\in\mathbb{R}$ and $b_i\in\{0,1\}$ for all $i,j\in\{1,2,\ldots,n\}$ and $j>i$. I want to know which of all the possible boolean combinations make(s) the following expression maximal: ...
- 257
2
votes
3
answers
363
views
Integer linear programming formulation of formula in DNF
I have multiple sets, e.g.,
$$\{1, 2\}, \{2, 3, 4\}, \{1, 4\}$$
Each variable $1, 2, 3, 4$ is binary. I need to represent the following condition without additional variables
$$(1 \land 2) \lor (2 \...
- 185
1
vote
1
answer
120
views
How to model this constraint using integer linear programming?
Suppose we have $S=\{1,2,\ldots,n\}$, a binary variable $x$ and an integer $p$. I would like to model the following constraint using integer linear programming:
If $x = 1$, then there must exists a ...
- 259
1
vote
1
answer
132
views
Maximizing the boolean combination of given real numbers
Let $x_1, x_2, \dots, x_n \in \mathbb R$ and $b_1, b_2, \dots, b_n \in \{0,1\}$. I want to know which of all the possible boolean combinations is maximal. For example, if $x_1 = 2$ and $x_2 = -2$,
$$...
- 257
2
votes
1
answer
356
views
Expressing a logical constraint in integer programming
Let $x$ be an integer such that $x \in [ - 10,10]$ and $b$ a binary variable. Apply integer programming to express $b = 1 \leftrightarrow x \ge3$
My work:
\begin{equation}
\begin{cases}
\...
- 142
1
vote
2
answers
268
views
Expressing the condition as a set of linear constraints
Express the condition "$x = 0$ if and only if $y = 0$" as a set of linear constraints, where $x,y$ are integers such that $ - 5 \le x \le 8$ and $0 \le y \le 1$
- 142
2
votes
2
answers
572
views
Casting to boolean in integer linear programming
I have variables $x \in \{0,1,\dots,5\}$ and $y \in \{0,1\}$, where
$$y = \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$
My problem is to maximize $y$. How can I ...
- 21
1
vote
1
answer
87
views
Using integer programming to find a solution without optimizing it
Oftentimes I find myself wanting to use integer programming to find a solution to a particular problem, without caring about optimizing a certain variable at all.
I've found that most packages that ...
- 14k
1
vote
1
answer
525
views
Set Cover and additional constraints
Consider the following bipartite graph:
Each node in red color represents a warehouse $w = \{ 1,2,3\} $. For this example we have three warehouses located at different locations. Each warehouse has a ...
- 113
3
votes
1
answer
4k
views
Express a "complex" IF-Statement to Linear Programming
In our current project we need to model the following if-statement in linear programming:
If T1 < b < T2 then z = s else z = 0
where T1 and T2 are two ...
- 33
5
votes
2
answers
1k
views
Minimum spanning tree formulation as integer program
The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a ...
- 223
3
votes
1
answer
1k
views
From CNF to ILP?
Can we transform a CNF to ILP without introducing new variables?
My question can be seen as a follow up to Express boolean logic operations in zero-one integer linear programming (ILP) as the ...
- 33
3
votes
1
answer
437
views
Solving for the minimum cost, colored, set cover
Formulation
This problem has four entities:
A universe: $U = \{1, 2, ..., n\} $ of $n$ elements, indexed with $u$
A set of available colors: $C \in \{1, 2, ..., m\} $ with $m$ colors, indexed with $c$...
- 383
4
votes
2
answers
317
views
Discrete assignment problem with penalties
I came across a problem were you have to plan an optimal assignment pattern. Let's say you have $j=1,\ldots,n$ tasks during $i=1,\ldots,m$ time periods.
It's an single agent problem where we have to ...
- 143
4
votes
5
answers
10k
views
"Greater than" condition in integer linear program with a binary variable
How can one model the following condition in an integer linear program?
$$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$
where $A \in \{0,1\}$ and $B, C \in \...
- 91
5
votes
2
answers
999
views
Does integer programming $\in$ NP imply $NP=CoNP$?
Although it is relatively simple to see that integer linear programming is NP-hard, whether it lies in NP is a bit harder. Therefore, I'm wondering whether the following reasoning shows that $ILP\in ...
- 8,472
1
vote
1
answer
826
views
Linear programming, Checking a constraint based on condition
I have a constraint $X \ge Y$ in a Linear programming formulation, where both $X$ and $Y$ are binary. I want to check this constraint on a condition like:
...
- 229
3
votes
1
answer
3k
views
Converting If-else condition to Linear Programming
I have a constraint in a linear programming formulation with two variables: $X \ge Y$
To which I want to apply the following if-else conditions:
...
- 229
9
votes
3
answers
2k
views
Boolean variable true iff equation is satisfied in ILP
Assuming $y$ is a boolean variable in an ILP program (that is $y \in Z$, s.t. $0 <= y <= 1$) and $x_1$, $x_2$ are bounded integer variables between $0$ and $M$. I want to encode the following ...
- 327
2
votes
0
answers
165
views
Given a digraph and a root, find a tree that minimizes the sum of edges
Instance: a directed graph $G = (V, A)$ with weights $w_a\in\mathbb{R}$ on the edges and a root $v\in V$.
Solution: A directed tree with root $v$.
Objective: Minimize total weight.
My formulation:
...
4
votes
2
answers
2k
views
How to solve the feasibility problem in 0-1 integer programs?
I have an NP-hard 0-1 integer program that I need to solve. The issue with this problem is that even finding a feasible solution (ignoring the objective function) is NP-hard.
Let us look at two ...
- 703
9
votes
1
answer
517
views
How to partition a set into a given number of disjoint subsets subject to some conditions?
I am given a set $A\triangleq\{1,\ldots,k\}$, an integer $s\leqslant k$, and non-negative integers $a_{ij}$. My problem is to find $s$ disjoint subsets $S_j$ of $\{1,\ldots,k\}$ such that:
$\bigcup_{j=...
- 1,000
3
votes
1
answer
1k
views
How to solve an ILP problem with conditions in an objective function?
I have came accross this link.
I have an integer linear programming (ILP) problem
$$\max_{(x_1, x_2,\ldots, x_n)}\sum_{i=1}^n x_i\cdot f(x_i),$$
$$\text{subject to } \begin{cases}
..., &(1)\\
L≤...
- 175
4
votes
0
answers
307
views
Subset sum with wider constraint
The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$:
$
max \displaystyle\sum_{i} x_i, x_i \in \{0,1\}
$
subject to
$
\displaystyle\sum_{i} w_ix_i \leq W
$
for a ...
- 41
10
votes
3
answers
4k
views
Finding all solutions to an integer linear programming (ILP) problem
My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this ...
- 101
3
votes
1
answer
195
views
An integer linear program
I have the following problem:
Given positive integers $a, b, c, d, n$, compute the maximum possible value (which is garuanteed to be less than $10^9$) of the function $$f(x,y) = cx + dy$$ where the ...
- 467