All Questions
Tagged with linear-programming linear-programming or
492 questions
2
votes
2
answers
421
views
Algorithm to determine if a union of half-spaces is all of $\mathbb{R}^d$
I have a collection of closed half-spaces $H_1, \dots, H_n \subseteq \mathbb{R}^d$, each given as $H_i = \{x \in \mathbb{R}^d : a_i \cdot x \geq c_i\}$ for some $a_i \in \mathbb{R}^d$ and $c_i \in \...
- 47.1k
0
votes
1
answer
456
views
Is the Simplex Method still polynomial when all inequalities are through the origin?
Hello,
I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, ...
- 1,826
1
vote
0
answers
163
views
Can we reduce the maximization of this integral to the maximization of the integrand?
I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\sum_{i\in I}\sum_{j\...
- 167
0
votes
1
answer
99
views
Finding dual of a scheduling LP formulation
Suppose I have an LP formulation as such:
$\min\ \ \sum\limits_{i,j,t}\ w_{ij}x_{ijt} (\frac{t-r_j}{p_{ij}}+0.5)$
$\sum\limits_{i,t}\frac{x_{ijt}}{p_{ij}}=1\,\forall\ j$
$\sum\limits_{j}x_{ijt}\leq ...
- 5,429
0
votes
1
answer
113
views
How do I solve this integer programming problem with non convex constraints?
I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place.
I have an optimization problem like this
...
- 5,429
0
votes
0
answers
101
views
How can we analytically solve this max-sum-min problem?
Let $I$ be a finite set, and $A_{ij},B_{ij},x_i,y_j\ge0$. I want to find the choice of $x_i,y_j$ maximizing $$\sum_{i\in I}\sum_{j\in J}A_{ij}\min\left(x_i,B_{ij}y_j\right)\tag1$$ subject to $$\sum_{i\...
- 167
0
votes
1
answer
61
views
Variant of the linear programming problem
Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem:
$$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$
$$s.a....
- 5,429
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 ...
CommunityBot
- 1
0
votes
0
answers
35
views
Converting a vector in a cone statement to inequality constraints
I would like to convert the following condition for $x$
\begin{align}
x = N \lambda, \lambda \geq 0
\end{align}
to a pure linear inequality form, i.e. find an $L$ and eliminate $\lambda$
\begin{...
- 356
1
vote
0
answers
25
views
Weird subspace/equality-constrained LP problem/variant of change-making problem
Assume that we have a set, $\mathscr{R}$ containing $m$-dimensional vectors. Solve
$$\sum_{i=1}^n c_i\leq\delta$$
$$\text{subject to } \sum_{i=1}^n r_i c_i=x^\prime \text{ for all }x^\prime$$
where
$0\...
- 11
6
votes
1
answer
861
views
Is Binary Integer Linear Programming solvable in polynomial time?
The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...
- 151k
3
votes
1
answer
1k
views
Finding the closest special orthogonal matrix in Frobenius norm sense
Given a $3\times3$ matrix $M$, if we would like to get the closest $\mathrm{SO}(3)$ matrix $R$ that minimizes
\begin{equation}
\|R-M\|_F
\end{equation}
then $R$ = $UV^{T}$ where $U$ and $V^{T}$ are ...
- 33
3
votes
1
answer
244
views
What importance does the Hirsch conjecture have to Simplex Complexity?
The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has ...
- 24.7k
5
votes
1
answer
315
views
On optimal dual solutions for the minimum weight perfect matching problems in the case of metric weights
Following Lovasz-Plummer (Matching theory, North-Holland 1986, Theorem 9.2.1),
the minimum weight perfect matching problem on a complete graph
$G$ with even number of vertices and weight $w:E(G)\to
\...
- 4,878
3
votes
1
answer
275
views
Uniqueness of l1 minimization
Let $A \in \mathbb{R}^{m \times n}$.
Is it true that $$\min \limits_{Q \in \mathbb{R}^{n \times m}}|I - QA|_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to
$\...
- 3,209
1
vote
0
answers
177
views
Prove that these linear programming problems are bounded by $O(k^{1/2})$ [closed]
The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems:
$$\begin{array}{ll} \text{minimize} &...
- 1,183
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 ...
CommunityBot
- 1
3
votes
2
answers
331
views
Program to solve Optimization Problem
I have an optimization problem, this problem has linear constraints and nonlinear constraints. I solved the linear part by MATLAB but the nonlinear constraints I could not solve it. I downloaded ...
- 1,517
0
votes
0
answers
232
views
What do square roots as minimums have to do with Harmonic numbers?
In an earlier question where I conjectured (and GH from MO confirmed) that the von Mangoldt function is the limit at s=1 of a certain Dirichlet series:
$$\Lambda(m)=\lim_{s\to 1+}\zeta(s)\sum_{d\mid ...
- 1,183
5
votes
1
answer
424
views
What is the LP gap of vertex cover in planar graphs?
What is the LP gap of vertex cover in planar graphs?
The LP I refer to is min $\sum_{e \in E } c_e x_e \ \ $ subject to $ \ \ x_v + x_u \geq 1 \ \ \ \forall uv \in E $
$ c_e \geq 0 $ are ...
- 26
3
votes
0
answers
178
views
Uniqueness of projection under spectral norm
I am considering
$$
\min_{M\in \mathcal{M}} \|X - M\|:=x \neq 0,
$$
where $X$, $M$ are $m\times n$ matrices, $\|\cdot\|$ is spectral norm and $\mathcal{M}$ is a matrix subspace. I wonder to what ...
- 131
1
vote
0
answers
36
views
Linear programming with a convergent coefficient
The following linear programming problem
$x_n = \arg\min c_n'x \mbox{ subject to } Ax<b$
has a changing coefficient $c_n$. We have that $c_n\rightarrow c_*$. What happens to the solution $x_n$? ...
- 19
2
votes
1
answer
243
views
Does quantifier elimination help here?
Suppose we have a quantified linear program
$$\exists z_1,\dots,z_{poly(n)}\in\mathbb R$$
$$\exists u_1,\dots,u_n\in\mathcal P\cap\mathbb R^m$$
$$\forall v_1,\dots,v_n\in\mathcal P\cap\mathbb R^m$$
$$...
- 1,826
3
votes
1
answer
151
views
A question about polytopes related to linear programming
Given linear functions $f_1({\bf x}),\dots,f_n({\bf x})$ on ${\bf R}^m$, let $K = \{(a_1,\dots,a_n) \in {\bf R}^n:$ the $n$ halfspaces $\{{\bf x}: f_i({\bf x}) \leq a_i\} $ have nonempty intersection$\...
- 24.2k
1
vote
0
answers
126
views
Mixed integer formulation of union of polytopes?
Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
- 1,826
0
votes
1
answer
39
views
Gluing simplices through a common point/ realisation of a convex simplicial polytope
Given $m≥d+1$
a positive integer, is it always possible to find m d-dimensional simplices $\Delta_i=\mathrm{Conv}(M,V_{i,1},…,V_{i,d})$ such that
1) they all share the common vertex M
2) the ...
- 14k
1
vote
1
answer
126
views
Quantifier elimination and where is this quantified convex program in the polynomial hierarchy?
I have a quantified convex program of the form that I need to solve
$$\exists(x_{1,1},\dots,x_{1,n})\in\mathbb R^n\quad\forall(x_{2,1},\dots,x_{2,n})\in\mathbb R^n$$
$$\vdots$$
$$\exists(x_{2t-1,1},\...
- 14k
7
votes
2
answers
909
views
Formula for volume of a convex polytope
So I've been searching around the internet for some answers to this, but I currently have a set of linear constraints: $Ax = b, Cx \le d$ for matrices $A \in \mathbb{R}^{n \times m}$, $b\in \mathbb{R}^...
- 984
1
vote
0
answers
24
views
Simple monotonicity property for coordinate descent and linear objective functions
Let $S \subset \mathbb{R}^n$ satisfy $0\leq x_1\leq\dots\leq x_n$ for all $\mathbf{x}\in S$, among other (possibly nonconvex) constraints, and suppose in addition that $\sum_{i=1}^n x_i \geq 1$ for ...
- 4,049
0
votes
0
answers
89
views
Why there isn't lexicographically smallest solution to a bounded linear program?
I am learning computational geometry when I run into this confusion. "A bounded 2D linear program may not have a lexicographically smallest solution", as the book says. I wonder why? I think we can ...
- 1
1
vote
0
answers
37
views
Fast certficate of negativity for objective value of mixed-integer linear program
Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP)
$$
\begin{split}
f^* = &\max \; ...
- 6,853
2
votes
1
answer
270
views
What optimization problems have solutions with few nonzeros?
Consider the following optimization problem, with $n$ variables and $m$ linear constraints:
\begin{align}
\text{maximize} && c_1 x_1 + \cdots + c_n x_n &
\\
\text{subject to} && a_{...
- 14k
13
votes
3
answers
834
views
Famous theorems that are special cases of linear programming (or convex) duality
The max flow-min cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any ...
- 109k
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
1
vote
1
answer
330
views
How good is the LP relaxation?
Consider the optimization problem
\begin{align}
\max_{x\in\mathbb{R}^n}~c^Tx~, \text{ s.t. } Ax=b,~x_i\in\{0,1\}~\forall i
\end{align}where $c,b\in\mathbb{R}_{+}^n$ and $A\in\mathbb{R}_{+}^{n\times n}$...
0
votes
2
answers
102
views
Does Max Flow produce uniform results? [closed]
I am interested in using Max Flow algorithm. I want to simulate transfer of quantity. Anyway, I am unsure of some thing.
Does Max Flow algorithm produce uniformly distributed max flow?
I have ...
- 400
1
vote
3
answers
138
views
Literature request: Function that depends on a linear optimization problem [closed]
my question is about functions of the following form:
$$ f(t) = \max_{\mathbf{x}}~ \mathbf{c^T x} ~ {\rm s.t. \mathbf{Ax} +t \cdot \mathbf{a} \leq \mathbf{b}}, $$
where $\mathbf{x},\mathbf{b}, $ ...
- 1,991
3
votes
1
answer
553
views
Calculate the discrete set of points B which are in the convex hull of the set of points A
This problem is likely best described with the following picture:
Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
- 4,713
7
votes
1
answer
386
views
Which zero-diagonal matrices contain the all-one vector in their columns' conic hull?
Let $A$ be a non-negative zero-diagonal invertible matrix. Which $A$ make the following assertions true, which are all equivalent:
The all-one vector $j$ is contained in the conic hull of $col(A)$.
...
CommunityBot
- 1
0
votes
1
answer
145
views
How to solve this optimization problem efficiently? [closed]
Let, $D\in\mathbb{C}^{1\times M}$ is a row vector with $M$ elements
$V\in\mathbb{C}^{3^M\times M}$ is a given matrix
$T$ is a scalar (real and $>1$)
$\textbf{The problem at hand is as follows:}$
...
- 111
1
vote
1
answer
123
views
LASSO problem but with a maximization instead of minimization
I have the following optimization problem (like the LASSO problem but with maximization instead of minimization):
$\mathbf{maximize}_{\boldsymbol{\alpha}} \|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|...
- 20.2k
-1
votes
1
answer
88
views
sparse data fitting problem [closed]
I am a new learner of optimization, and I am confused by the question below, (how to change a 0-norm constrain into binary and linear constrain ?)
Given a sparse data fitting problem:
$ minimize \...
- 1,517
1
vote
0
answers
74
views
How to minimize n-polytope's bounding box with linear transformation?
I am working on an exact algorithm for integer linear programming for my master's thesis:
$Ax\leq b, x \in \mathbb{Z}^n$
$cx\rightarrow min$
For my idea to work out, I need a guarantee that n-...
- 11
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,...
- 13.6k
1
vote
0
answers
85
views
"Barrier functions" in function spaces [closed]
In general the idea of a "barrier function" (as in the context of "interior point methods") can possibly be thought of as defining a function corresponding to an open subset of $\mathbb{R}^n$ such ...
- 2,246
0
votes
1
answer
490
views
Relax a rectangular linear assignment problem
I wonder if there is any literature on the following problem
$$\begin{array}{ll} \underset{X \in \mathbb R^{m\times n}}{\text{minimize}} & \displaystyle\sum_{i,j} C_{i,j} X_{i,j}\\ \text{subject ...
2
votes
1
answer
502
views
Feasibility Mixed integer Linear programming with quadratic constraints?
Consider the mixed integer program
$$Ax\leq b$$
$$By\leq c$$
$$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer ...
- 1,517
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?
-1
votes
2
answers
114
views
On OR condition in Linear Programming with exponentially many constraints [closed]
Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
- 128k
0
votes
0
answers
99
views
Is this Graph Iteration Already Known?
When attempting to set up an ILP formulation for a weight-minimal cubic spanning tree (i.e. one with vertex degrees either 1 or 3) I needed connectivity constraint, but misremembered the contents of ...
CommunityBot
- 1