47
It may be that this question had been answered here before, but I couldn't find the answer.
Anyway, the answer is given by the person who coined the name itself: George Dantzig wrote in "LINEAR PROGRAMMING":
Here are some stories about how various linear programming terms arose. The military refer to their various plans or proposed schedules of training, ...
8
From the wikipedia page on mathematical optimization:
The term, programming, in this context does not refer to computer
programming. Rather, the term comes from the use of program by the
United States military to refer to proposed training and logistics
schedules, which were the problems Dantzig studied at that time.
7
This kind of questions arise very often in integer linear optimization. It is well-known that the bitsize of a solution will be polynomially bounded by the sizes of of $A$ and $b$, i.e. by the maximum bitsize of entries of $A$ and $b$, and by $\max(n,m)$. See e.g. Corollary 5.2a in the A.Schrijver's book.
There are many sufficient conditions known for the ...
7
Often called Binary Integer Programming (BIP).
Wikipedia:
Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.
Here is a list of those 21 Karp problems.
You can also find the claim that ...
6
When the term "linear programming" first came into use, computers were still very rare beasts, and the term "computer programming" wasn't that widely used. Here "programming" meant planning. As researchers started to work on other optimization problems, the "programming" term continued to be used and we ended up with "nonlinear programming", "integer ...
6
The statement that you want to prove follows from Dirichlet's Theorem, which says that for any real number $\alpha$ and for any positive integer $Q$, there is a fraction $a/q$ with $|q|\le Q$ such that
$$|\alpha-a/q|\le 1/q(Q+1).$$
Here $\alpha$ is the slope of your line and $Q$ is playing the role of $R$, with $1/(Q+1)$ playing the role of $\epsilon$. Of ...
4
I don't know the answer to the second question (bounding the norm), but for the first, just compute the Smith normal form of A (and transform $b$ appropriately).
4
http://dx.doi.org/10.1016/S0020-0190(00)00010-7
4
The g.f. equals
$$\frac1{1-y}\prod_{i=1}^n \left(xy^i + (xy^i)^{-1}\right).$$
That is, the number of solutions is given by the coefficient of $x^cy^b$.
4
Evaluating the minimum $\delta_k:=\min_{x\neq y}|f(y)-f(x)|$ over distinct strings $x, y\in \{0,1\}^k$ seems a hard diophantine problem. It is quite cheap to prove that $\delta_k$ is $O(1/k)$ and decreasing, so that in particular the infimum over all finite strings is zero; actually, it's zero even among strings $x$ and $y$ with at most $2$ non-zero ...
4
The way I think about Kannan's algorithm (or, for that matter, any of the several "Lenstra-type" algorithms which present similar bounds as the original Lenstra algo from 1983) is that it's designed with the extreme worst-case instances of integer programming (IP) in mind. The goal here is to get a small (i.e., polynomial) bound on the complexity of the ...
4
I looked into that at some point. The original paper says $N^{O(d^2)}$, where $d$ is the dimension and $N$ is the size of the input (sum of bit lengths of matrix entries in $A\overline x\le \overline b$). A followup paper by Barvinok says that more careful analysis improves it down to $N^{O(d)}$, but it seems there is a mistake in the calculation. ...
4
$\def\mr{\mathrm}$As it happens, quantifier elimination for Skolem arithmetic came up recently in my research. The concise description is that every formula $\phi(x_1,\dots,x_k)$ is in $(\mathbb N^{>0},{\cdot})$ equivalent to a Boolean combination of formulas expressing
$$\tag1\bigl|\{p\in\mathbb P:\psi(v_p(x_1),\dots,v_p(x_k))\}\bigr|\ge n,$$
where $\psi(...
4
Copying from http://mathworld.wolfram.com/SumofSquaresFunction.html:
To find in how many ways a positive integer $n>1$ can be expressed as a sum of $k=2$ squares ignoring order and signs, factor it as
$$n=2^{a_0}p_1^{2a_1}...p_r^{2a_r}q_1^{b_1}...q_s^{b_s}$$
where the $p_i$ are primes of the form $4k+3$ and the $q_i$ are primes of the form $4k+1$. ...
answered Jan 21 '19 at 3:19
Konstantinos Kanakoglou
5,5932 gold badges16 silver badges46 bronze badges
3
The problem described is exactly the unbounded subset sum problem. For the proof of NP-completeness of the decision variant as well for the algorithm designed especially for the unbounded subset sum problem see
Kellerer, Hans, Ulrich Pferschy, and David Pisinger. Knapsack problems. Springer, 2004.
3
$\alpha=3/8$ is sharp according to, say this article, the authors refer to
[L. Fejes-Toth and E. Makai, Jr., On the thinnest non-separable lattice of convex
plates, Studia Sci. Math. Hungar. 9 (1974), 191–193.]
3
The key words to look for is "continued fractions" and "Bresenham". See
http://www.cs.tau.ac.il/~nachum/calendar-book/papers/bresenham.pdf
3
The answer to both your questions is Gomory cuts. From a non-interger extreme point $x$ of $P$ it is easy to find an hyperplane $H$ which separate $x$ from $Int(P)$. Such an hyperplane is called a Gomory cut. It can be shown that by applying this procedure a finite number of time one can describe $Int(P)$ as a finite intersection of halfspaces.
I don't have ...
3
Let $A_i$ be the set of allowed values for $a_i$. Then $x$ satisfying the system recurrences represents a zero of the polynomial:
$$f(x) = \sum_{i=1}^n \frac{M}{p_i} \prod_{a\in A_i} (x-a)$$
modulo $M$, where $M=p_1p_2\cdots p_n$. Small zeroes of this polynomial modulo $M$ can be found with the Coppersmith method.
UPDATE. For the given example, we have $p_1=...
3
I sometimes read the claim that Gomory cuts alone (without any branch-and-X) are sufficient for finding integer solutions to linear programs in a finite number of steps. E.g. at the bottom of page 2:
Gomory showed that alternately applying the simplex method and adding cutting planes eventually leads to a system for which the simplex method will give an ...
3
Ok, not really beautiful, but the lines below are a simple SAGE implementation of the map $\partial$, computing both the representing matrix and the elementary divisors. In the implementation I assumed that $P^b_a$ is actually the binomial coefficient $\binom{\lfloor (a+b)/2\rfloor}{\lfloor a/2\rfloor}$ (the order in the question did not seem to make sense).
...
3
I am not sure about only using elementary number theory but here is an approach using the Bateman-Horn conjecture. Maybe one can get by with a bit less using sieve methods but I will leave that to the specialists.
Let $\alpha$ be of the form $210n+160$ where $n$ an integer and assume that $\alpha/10 = 21n+16, (\alpha -1)/3 = 70n+53$ and $(\alpha +1)/7 = 30n+...
3
The answer is $no$.
In the plane, the circle of diameter $d$ greater than $1$ but smaller than $\sqrt2$ and centered at $({1\over2},{1\over2})$ contains no point with integer coordinates, and the square $K_2$ circumscribed about it with diagonals parallel to the coordinate axes contains no such point either. Let $K_3\subset\mathbb{R}^3$ be the Cartesian ...
3
Introduce binary variables $d_1,\dots,d_{N-1}$ and constraints:
$$-d_i \leq a_i - a_{i+1} \leq d_i,\quad i=1,\dots,N-1$$
and
$$a_1 + a_{N} + d_1 + \dots + d_{N-1} \leq 2.$$
3
OK, sorry for the delay. I just don't have too much free time nowadays.
Let $a_0,\dots,a_{n-1}$ be your string. Note that for any $z=e^{it}$, we have
$$
P_a(z)=a_0+a_1z+a_2z^2+\dots+a_{n-1}z^{n}=\frac 1{z-1}\sum_s(z^{n_s}-z^{m_s})
$$
where $[m_s,n_s-1]$ ($s=1,2,\dots,p$) are the groups of successive $1$'s.
Thus, if you have just one group, you have the ...
3
ILP is $NP$-complete, while computing a Grobner Basis is $EXPSPACE$-complete. As one has the containments $NP\subseteq PSPACE\subsetneq EXPSPACE$, one should expect that you can reduce ILP to computing a Grobner basis, but not the other direction.
2
I found this one pretty good:
http://www.cs.princeton.edu/courses/archive/spr05/cos598B/liftproj.pdf
2
It isn't clear from your posting whether you're trying to understand:
Why the inequalities generated by the Sherali-Adams procedure are valid?
or
Why the procedure is complete in the sense that after enough iterations you arrive at the convex hull of the integer solutions of the original integer linear programming problem?
I suppose that you might also ...
2
An example:
$C_1=[(0,0),1]\;,C_2=[(1,0),\frac{4}{5}]\;,C_3=[(2,\frac{3}{2}),\frac{3}{4}]\;.$
Contours show equal distance sums.
$d_{\min}=\frac{3}{4}$ is achieved at $p_{\min} \approx (1.06, 0.80)$.
2
Here is one reference, a 2010 book that may lead to other literature:
Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization,
by Levent Tunçel:
Only top voted, non community-wiki answers of a minimum length are eligible
