I have an objective function to be maximized $obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$ With multiple constraints of the form: $\min_{y \in 0,1} (\sum_{i \in A} \a …

Let $M$ be a lattice polygon on a plane (i.e. its vertices are integer points $(i,j)\in\mathbb Z^2$). Let us define lattice width in a direction $v=(m,n)\in\mathbb Z^2$ as $w_v(M) …

Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent. An induced subgraph $H$ of $G$ is ca …

(I've posted this question at Math.SE but got no answer, so I hope I can get a solution here.) This problem looks familiar, but I don't remember its solution: $$ \min_k \ \ \frac …

What are the easiest brute force algorithms for solving closest and shortest vector problems? I want to find an arbitrary, but small ($\lesssim 20$) number of lattice vectors clos …

Have there been attempts to factor integers with Linear Programming? Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, …

Hi all. Let A,B and C be three real variables. I must write the following if-then-else condition with linear inequalities: if A≤B then C=0 else C=B-A Is this possible by adding …

Hello, recently I've been studying the problem of integer representation as sum of three squares. Most of the articles that I've found study the function $r_m(n)$ which counts the …

Given two sets of nonnegative integer numbers: $X = {x_1, x_2, ... x_n}$ $Y = {y_1, y_2, ... y_m}$ Need to find partition of $X$ on $m$ disjoint subsets, such as sum of elements …

Hi all. Let $a$ and $b$ be two real variables such that $0 \le a \le a_{max}$ and $0 \le b \le b_{max}$. I must write the following if-then-else condition with linear inequalities …

I have a matrix A \in Z^{n \by m}, where m > n and a vector b \in Z^n. Then, under what conditions does an integer solution exist to the equation Ax = b. Is there a way to bound …

Consider the following integer program $$ \begin{align} \max &\sum\nolimits_{i}\sum\nolimits_{j} U_i(j)\cdot x_{i,j}\ \text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\rig …

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that t …

I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a …

I have been looking into the problem $\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current fo …