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
13 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
1 vote
0 answers
132 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 ...
- 13.9k
0 votes
0 answers
126 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
79 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
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
-3 votes
1 answer
116 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
2 votes
1 answer
253 views
Integral hull of a polyhedron is polyhedron
$\DeclareMathOperator\Convexhull{Convexhull}$Let $Q \subseteq \mathbb R^n$ be a rational polyhedron and let $Q_I=\Convexhull(Q \cap \mathbb Z^n)$. By finite basis theorem, we have $Q=P+C$ for some ...
- 31
3 votes
1 answer
159 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
4 votes
2 answers
217 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
7 votes
2 answers
320 views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds: $$ \langle x_k, \theta_k \rangle &...
1 vote
0 answers
61 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,645
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
2 votes
4 answers
321 views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
4 votes
1 answer
289 views
How to maximize the variance of a subset of integers?
$\DeclareMathOperator{\Var}{Var}$Given the set of numbers $\Omega := \{1, \ldots, n\}, n \in \mathbb{Z}^+$, how can I choose a subset, $A$ of $\Omega$ , such that $\min(\Var(A), \Var(\Omega \setminus ...
- 169
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\...
- 142k
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
147 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
153 views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
1 vote
1 answer
216 views
Mixed integer program and continuous Diophantine approximation
Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem. $$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$ subject to ...
0 votes
0 answers
65 views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,131
5 votes
1 answer
251 views
Efficient counting of integer solutions to linear system
In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
- 161
1 vote
0 answers
200 views
Minimum of the maximum element frequency given the family size and the universe size
[Crossposted at math.stackexchange]. Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$. I have written and solved ...
- 1,186
0 votes
2 answers
708 views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem? $$ \begin{array}{ll} \underset {y, z} {\...
- 21
0 votes
0 answers
239 views
Software for computing polytopes
As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
- 1
2 votes
1 answer
1k views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost. It may be formulated as linear programming in a following way: $$\boxed{\begin{gather} \min\limits_{f_{ij} \in \mathbb R} &...
- 1,211
0 votes
0 answers
83 views
A question on a quantitative form of Farkas' lemma
Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
- 6,386
2 votes
1 answer
261 views
Is matrix B obtained from matrix A?
Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
- 49
0 votes
1 answer
530 views
What is the best way to choose initial basis when applying simplex method to an equality form of LP?
Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...
- 1
0 votes
1 answer
261 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
0 votes
0 answers
220 views
Solve NP-hard type problems with linear programming
I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force. I ask this ...
2 votes
1 answer
381 views
Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?
According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard. However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
- 123
5 votes
0 answers
73 views
Implementation of Friedman's algorithm of reconstructing simple polytopes
In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
2 votes
0 answers
144 views
Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$
Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
3 votes
0 answers
142 views
Techniques for solving linear inequalities
For $n$ real variables $x_1, \ldots, x_n$, I have a bunch of inequalities of form $2 x_i > x_j + x_k$ or $2 x_i < x_j + x_k$, where $i,j,k$ are distinct. My goal is to determine whether this set ...
- 231
1 vote
1 answer
183 views
Optimization on non-convex set
Let $\Omega$ be an open bounded subset of $\mathbb{R}^2$ and $f\in L^2(\Omega)$ be a given function. Consider the optimization problem $$\mathrm{min} \int_\Omega u(x) f(x) \,dx\,,$$ where a minimum is ...
- 11
27 votes
5 answers
2k views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows: $$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$ For example, if $m=3$, the matrix is $$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
16 votes
3 answers
1k views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets. Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$. Can $\text{Proj}(P)$ have more than $f$ facets? ...
- 163
1 vote
0 answers
125 views
Linear Program Optimal Value
If $f(A,b,c)$ is the optimal value of a linear program $\min c.x$ subject to $A.x \leq b ; x \geq 0.$ Does $f(A,b,c)$ have a piecewise polynomial/rational upper bound in $(A,b,c)$ on the domain of ...
1 vote
1 answer
114 views
$A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance
Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the ...
- 111
1 vote
1 answer
177 views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
- 13.9k
0 votes
1 answer
55 views
Calculating vertex potentials from optimal matchings
Question: can the solution to the dual of a Linear Program be calculated directly from the solution of the primal Linear Program? If yes, what are known algorithms and their bounds on complexity. As ...
- 13.9k
0 votes
1 answer
780 views
Method for (binary) optimization under constraints
I would like to know if there is a method to solve the Problem. Problem: Maximize the following function: $$f(p_{1,i},p_{2,i},\dotsc,p_{m,i})=\sum_{i=1}^{n}\begin{bmatrix}p_{1,i} & p_{2,i} & \...
- 3
0 votes
0 answers
124 views
Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points
Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$ \begin{align} \max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
- 671
4 votes
2 answers
392 views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 269
1 vote
2 answers
216 views
How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?
I am looking for an algorithm to solve the following optimization problem $$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$ where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$. ...
- 175
25 votes
3 answers
2k views
Is the Ford-Fulkerson algorithm a tropical rational function?
The Ford-Fulkerson algorithm Let me recall the standard scenario of flow optimization (for integer flows at least): Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
- 35.5k
8 votes
2 answers
1k views
Minesweeper as a linear algebra problem
I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear ...
- 361
1 vote
0 answers
421 views
Closed-form solution of a particular linear program
(Note: I asked a similar question at math.stackexchange but the present one is more precise.) I have a linear program of the form: $$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$ $...
- 1,186
1 vote
1 answer
210 views
Linear programming with "nice" matrices
Consider the following linear programming problem \begin{array}{ll} \text{minimize} & \mathrm 1^{\top} \mathrm x\\ \text{subject to} & v\le \mathrm A \mathrm x \le u\\ & \mathrm x \geq ...
- 706