Questions tagged [linear-programming]
Linear programming is the study of optimizing a linear function over a set of linear inequalities. The Simplex Method, Ellipsoid Method and Interior Point Method are popular algorithms to solve linear programs.
498 questions
0
votes
0
answers
28
views
What to do with new LP formulations for optimal permutations
Question:
what, besides publishing, should I do with a new interpretation of how to formulate hard problems for optimal permutations with constraints on the cycle structure?
Currently I have ...
- 14k
0
votes
0
answers
19
views
Sufficient condition for shortest path expansion by Minimum Mean Cost Cycle
Let $G=(V,A)$ be a directed graph, such that for any two vertices $v,w$, there exists a vertex $u$ such that $(v,u),(u,w)\in A$. Let $s,t\in V$, and let $c:A\rightarrow \mathbb{N}_{\geq 1}$ be arc ...
- 157
3
votes
1
answer
247
views
Where does Concorde spend its time
Concorde is the de facto standard for calculating exact solutions for the Traveling Salesman Problem.
Question:
what is known about the fractions of computation time that are spent on ensuring that ...
- 14k
0
votes
0
answers
127
views
All possible images of a vector after averaging
For a given $x \in \mathbb{R}^n$, is there a name given for the set of all possible $y\in \mathbb{R}^n$ that can be obtained by iteratively selecting a subset of entries $S\in \{1,\dots,n\}$ and ...
- 4,131
0
votes
0
answers
222
views
Combinatorial code design
I would like to know the feasibility of the following linear programming problem related to coding theory.
Given a natural number $d$, binary entry matrix $X:=[x(i,j)\in B],\ B:=\{0,1\},\ i\in B^d,\ j\...
- 2,363
0
votes
0
answers
85
views
Polynomial solution to linear feasibility problem with polynomial constant term
Let $A \in \mathbb{R}^{m \times q}$. Let $b:\mathbb R^n \rightarrow \mathbb R^{m}$ be a polynomial function homogeneous of degree 2 (i.e., $b(z) = H (z\otimes z)$, for some matrix $H$), of a variable ...
- 26
-3
votes
1
answer
117
views
Find vector with values in [0, c_max] such that it sums to K [closed]
General problem
I am trying to find an analytical solution to the following problem: Given a vector $v$ with non-negative entries, find a way to normalize it into a vector $v'$ such that:
If $v_i <...
- 3
1
vote
0
answers
62
views
Details on the usage of projective transformations in Karmakar's algorithms
The question is related to this algorithm in linear optimization. In the algorithm, projective transformations are used as said by wikipedia:
Since the actual algorithm is rather complicated, ...
- 1,665
3
votes
1
answer
162
views
Hermite-type convex interpolation
Let $f : [0, 1] \to \mathbb{R}$ be a smooth strictly convex function.
Let $0 \leq x_1 < \dots < x_n \leq 1.$
I am interested in whether there exists a polynomial $p$ such that it is convex on $[...
- 105
3
votes
0
answers
110
views
Which function does this cross section optimize?
I often notice tankers of the type illustrated in the figure below.
The cross section is neither circular nor elliptical. Is it a "notable" geometric shape?
Which function or property does ...
- 285
4
votes
2
answers
220
views
Simpler proof of arborescence packing and isolating cut equivalence
Let $G$ be a directed graph with specified vertex $v$. We define a $v$-cut in $G$ to be a set of edges whose deletion from $G$ results in a graph where some vertex $w\neq v$ cannot be reached by a ...
- 599
15
votes
3
answers
2k
views
Maximum minimum difference between $f(k+1)$ and average of $f(0), \dots, f(2k+1)$
Consider the set of increasing functions over nonnegative integers such that $f(0)=0$ and $f(1)=1$. Find the function $f$ that maximizes $$\inf_{k \in \mathbb{Z}^{+}} \left[ f(k) - \frac{1}{2k+1}\sum_{...
- 431
1
vote
0
answers
93
views
Efficiently solving a linear system with singularities
I have a problem which can be efficiently written, with some abuse of notation, as an 18 x 18 matrix equation $\mathbf{A}\mathbf{x} \geq \mathbf{1}$ over the non-negative integers $\mathbf{x}\geq \...
- 161
1
vote
1
answer
148
views
Continuity of Solutions to Linear Programs
Suppose I have a linear program of the form $\max c^Tx$ such that $Ax \leq b$. I am curious as to the continuity of the solutions to such a linear program under perturbations of the entries of $A$.
...
- 143
1
vote
1
answer
138
views
A combinatorial linear programming problem
$\newcommand\S{\mathscr S}$Let $\S$ be a collection of nonempty subsets of a finite set $S$ such that $A\not\subset B$ for any distinct $A$ and $B$ in $\S$.
Does then there always exist a function $f\...
- 143k