Questions tagged [integer-programming]
Integer programming regards optimization problems, where one seeks to find integer values for a set of unknowns, that optimizes the objective function. A common subset of this type of problems are integer linear programming problems, where all inequalities, equalities and the objective function are linear in the unknowns.
191
questions
2
votes
1
answer
234
views
Nonexistence of short integer program sequence which generates squares
Is there a way to show within an integer program with constant number of variables and constraints of length $poly(\log B)$ (say length $\leq10^{1000000}\log B$), it is not possible for a variable to ...
- 13.8k
0
votes
0
answers
19
views
Lagrangian duals for the generalized assignment problem
I'm new to integer programming and I'm reading the book GTM 271: Integer Programming written by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli.
I have trouble solving exercise 8.6:
Consider ...
- 1
1
vote
2
answers
188
views
Direct algorithm for an integer program
Let $p$ be a prime and let $h_1,h_2\in\{1,2,\dots,p-1\}$ be integers.
Is there any direct algorithm to solve for following in polynomial in $\log p$ time?
$$\min (x_1-x_2)^2$$
$$x_1,x_2,k\in\mathbb Z$$...
- 13.8k
0
votes
0
answers
39
views
Max-flow modeling with unified vehicle and commodity variables
I am working on a network flow problem that involves routing through a time-space network. The network consists of:
A single source node and a single demand node.
A fleet of vehicles with specified ...
- 101
3
votes
2
answers
211
views
Is there a closed-form solution for $\max_D \operatorname{Tr}(ADBD)$
Is there a closed-form solution for
$$\max_D \operatorname{Tr}(ADBD)$$
where $D$ is a $N\times N$ diagonal matrix with $m<N$ number of $1$'s and the rest are $0$'s, and $A$ and $B$ are real ...
- 433
0
votes
0
answers
35
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 12.8k
0
votes
0
answers
58
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
- 3
0
votes
1
answer
139
views
How to integrate an indicator function/constraint into the cost function of a linear program?
I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.
In $F_2$, I want it to be included only when its expression ...
- 3
3
votes
0
answers
161
views
Why is this constrained quadratic-over-linear integer program separable?
Consider the following splitting problem. Given $Y$ balls of which $X\leqslant Y$ of them are blue balls. The goal is to split the balls by placing them in $K$ baskets based on the following quadratic-...
- 31
2
votes
1
answer
211
views
Can we say this nonlinear integer programming problem is NP-hard?
I was wondering if the following nonlinear integer programming problem is NP-hard or not.
$$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$
such that $\sum_{i=1}^{n}...
- 21
3
votes
1
answer
137
views
How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?
For an $n \times n$ matrix $M$, the $\infty\to 1$ and cut norms are given by
$$\|M\|_{\infty \to 1} := \max\limits_{x, y \in \{\pm 1\}^n} \sum\limits_{i, j} m_{i, j} x_i y_j, \qquad \|M\|_{\square} :=...
- 745
0
votes
1
answer
80
views
Algorithm to find a number B with same modulus as A with prime P and specific binary positions set to zero
Given a prime $P$, an integer $A$ $(0\leq A<P$), and a set of legal positions (encoded as a binary mask $\text{mask}$), is there an efficient algorithm to find a number $B$ that has the same ...
- 3
1
vote
1
answer
107
views
Existence of some lattice path connecting all given lattice paths
My daily work concerns analysis on metric spaces and some time ago it turned out that the problem I am dealing with boils down to a certain combinatorial problem. I've checked a lot of examples and it ...
- 127
2
votes
0
answers
208
views
Modular inverse computation - avoiding Euclidean algorithm
Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know ...
- 13.8k
1
vote
0
answers
91
views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61