All Questions
Tagged with linear-programming reference-request
21 questions
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997
17
votes
3
answers
6k
views
The cone of positive semidefinite matrices is self-dual? (reference needed)
I'm seeking a reference for the following fact.
The cone of positive semidefinite matrices is self-dual (a.k.a. self-polar).
This result is relatively easy to prove, has been known for a long time,...
- 1,513
7
votes
1
answer
374
views
Sampling uniformly from the vertices of a polytope
I'm looking for a reference on how to sample uniformly (and preferably efficiently, elegantly, etc.) from the vertices of a polytope. I gather that enumerating vertices is hard. I also note the MO ...
- 15.4k
5
votes
1
answer
183
views
Resource Constrained Routing with Refueling
What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...
- 13.2k
5
votes
2
answers
2k
views
Bounding the minimal maximum norm of a solution of a linear system.
I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear ...
- 191
4
votes
1
answer
2k
views
solving multiple linear programming problems with the same set of constraints
Hi,
I need to solve a set of linear programs of the form:
Problem $i$: $\quad \max c_i \cdot x$ s.t. $ A x \leq b$.
The $c_i$'s are different vectors so each problem has a different objective ...
- 560
4
votes
1
answer
204
views
Reference: Packing under translation is in NP
I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...
- 479
4
votes
0
answers
203
views
$\ell^1$-norm minimization duality
I am looking for an explicit description and discussion of the dual of the $\ell^1$-norm minimization problem $\lVert A x\rVert_1\to\min$, where $A$ is a matrix, and $x$ belongs to the $n$-simplex $\...
- 17k
3
votes
1
answer
266
views
Strong polynomial algorithm for linear programming
What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?
- 781
3
votes
1
answer
340
views
Name search for special Linear Integer Program
I am looking for a name for the following question in literature!
(and if you know it, then it would be great)
I couldn't find it and due to wide audience here, presumably you know more. Thank you
$...
- 31
3
votes
0
answers
87
views
Additional symmetries of the Traveling Salesman Polytope
Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
- 13.6k
2
votes
3
answers
753
views
Reference Request for Integer factorization with LP/ILP
Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...
- 13.2k
2
votes
2
answers
3k
views
Linear programming with infinitely many constraints
I wish to study the following linear program
$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \geq 0\...
- 283
2
votes
1
answer
509
views
Under what condition does Courant–Fischer–Weyl min-max principle hold in general?
From Wikipedia:
Let $A$ be an $n \times n$ Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient $R_A :
\mathbf C^n \setminus \{0\} \to \...
- 155
2
votes
1
answer
301
views
books on very large scale linear optimization
Recently in my material science research, I have encountered problems of very large scale linear optimization. I read the introductory book "Introduction to Linear Optimization (Athena Scientific ...
- 867
2
votes
0
answers
148
views
Generalization of Farkas' Lemma to Hermitian Matrices
I recently stumbled upon a well-known version of Farkas' Lemma which, roughly speaking, I would like to generalize from real vectors to hermitian matrices, as it seems promising for something else I ...
2
votes
0
answers
39
views
In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?
I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
- 21
1
vote
0
answers
493
views
Complexity of Nested Linear Optimization
My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint:
$$\max(\...
- 13.2k
0
votes
0
answers
145
views
Bound on solutions of $Ax \ge b$
Let $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m \times 1}$.
One can show that if there is a solution of $Ax \ge b, x \in \mathbb{R}^n$ then there is one such that $\|x\|_{\infty} \le c (\|A\|_{...
- 439
0
votes
0
answers
165
views
Minimum circumscribed ellipsoid of $\mathcal H$-polytope
Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows
$$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$
I ...
- 235
0
votes
0
answers
46
views
linear inequalities and reference request
I have proved and am using the following simple lemma in my current research problem:
Let $\{a_1,...,a_m\}$ and $\{b_1,b_2,...,b_n\}$ be set of positive numbers such that $\sum_{i=1}^m a_i < \sum_{...
- 1,269