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
12 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
-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
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
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
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
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
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
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
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
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
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
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
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 &...
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
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
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
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
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
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
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
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
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
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}$ (...
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
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
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
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 ...
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
0 votes
0 answers
73 views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 1
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
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
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
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
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
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
0 votes
1 answer
142 views
Constrained linear optimization problem on $C^1$
I am dealing with a problem of the form ($a<b$) $$ \displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
1 vote
0 answers
61 views
Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?
Suppose that $P$ is a polyhedron represented by $$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$ and $P$ contains interior points. Moreover, the ...
- 33
0 votes
0 answers
182 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
112 views
1-degree SOS proof refutes Linear Programming
I am trying to understand Sums-of-Squares proof systems. A degree $d$ Sums-of-Squares refutation for a set of polynomial equations $P = \{p_1(x) = 0, ..., p_m(x) = 0\}$ is defined as $\sum_{i=1}^m g_i(...
1 vote
1 answer
161 views
Adding linear constraint to the domain
I don't know if it is a well-known problem, but I have been struggling to come up with an algorithm. I have a set of linear constraints $Ax\le b$, $b\ge 0$ ($b$ and $A$ are given, $x$ is a variable). ...
1 vote
0 answers
125 views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61
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
251 views
Best projection on non-convex discrete set with two constraints
I want to compute the projection of a vector $\left( x\right) _{1\leq i,j\leq n}\in \lbrack 0,1]^{n\times n}$ on the following discrete set $$ S=\left\{ x\in \{0,1\}^{n\times n}:x_{i,j}+x_{j,i}\leq 1;\...
- 47
2 votes
1 answer
94 views
Counting the number of pair of d-uplets with upper bounded distance
Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ ...
- 55
0 votes
1 answer
178 views
Is there a redundant constraint in linear programming? [closed]
From wikipedia: But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice). (In order to do that, ...
- 3