# 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.

192 questions
Filter by
Sorted by
Tagged with
18 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 vote
185 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.7k
38 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 ...
206 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 ...
• 401
34 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.7k
54 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
131 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
160 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
174 views

• 24.3k