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.
161
questions with no upvoted or accepted answers
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
10
votes
0
answers
644
views
Fractional Matching version of Hall's Marriage theorem
Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:
1) there exist a perfect matching in $G$;
2) there exist non-negative weights on edges such that the sum of ...
7
votes
0
answers
1k
views
Closed-form solution of a linear programming question
Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & \...
7
votes
0
answers
1k
views
Infinite Linear Programming
I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ...
6
votes
0
answers
92
views
Finding the optimal mixture of two convex functions
I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\...
6
votes
0
answers
298
views
Variant of orthogonal Procrustes problem
The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both $A$ and $B$ are $n\times d$. Geometrically, $M$ rotates a set of ...
5
votes
0
answers
161
views
Homogeneous linear and quadratic inequalities
I have a bunch of vectors $b_i \in R^n$ for $i = 1,\ldots,N$ and a bunch of (indefinite) matrices $A_j$ for $j = 1,\ldots,M$. Let's consider the set $S \subset R^n$ of $x \in R^n$ vectors such that
$$...
5
votes
0
answers
167
views
A specific case of the $p$-center problem
Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...
5
votes
0
answers
194
views
A linear optimization problem on a graph
Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...
5
votes
0
answers
203
views
A polytope associated with the Hadamard Transform
In an investigation of whether or not a subset $V$ of "Hamming Space" $M_n = \mathbb{F}_2^n$ is a tile (i.e. whether $M_n$ can be written as a disjoint partition of translates of $V$) in http://arxiv....
5
votes
0
answers
559
views
When is polytope compatible with network flow?
A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
4
votes
0
answers
172
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 $\...
4
votes
0
answers
495
views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
4
votes
0
answers
784
views
Is it possible to use linear programming to solve this problem?
I am trying to write software to minimize pricing for cell phone subscription services, ie: choose the optimum plan for each customer in a large group.
Could someone comment on whether this is ...
3
votes
0
answers
251
views
Continuum of Lagrange multipliers, duality gap, and minimax theorem
Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...
3
votes
0
answers
81
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 $...
3
votes
0
answers
116
views
Convex optimization upper bound for a non-linear optimization
Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem?
\begin{align}
\max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
3
votes
0
answers
159
views
A new "adversarial" Wasserstein distance?
Let us consider $\mu_1, \mu_2$ and $\mu_3$ three probability measures living on $[0,1]^{k_1}, [0,1]^{k_2}$ and $[0,1]^k$respectively, with $k_1 +k_2=k$. Let us denote by $\Gamma(\mu,\nu)$ the set of ...
3
votes
0
answers
164
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 ...
3
votes
0
answers
99
views
Are there scenarios under which feasibility bilinear programming is easy?
Given $c\in\Bbb R^{n_1},d\in\Bbb R^{n_2}$, $E\in\Bbb R^{n_1\times n_2}$, $A\in\Bbb R^{m_1\times n_1}$, $B\in\Bbb R^{m_2\times n_2}$ $a\in\Bbb R^{m_1}$, $b\in\Bbb R^{m_2}$ and $t\in\Bbb R$ we know ...
3
votes
1
answer
341
views
Lot sizing problem: how to add these cuts efficiently
Consider the set of constraints of the uncapacitated lot sizing problem:
$$
\{(x,s,y)\in \mathbb{R}^n_+ \times \mathbb{R}^n_+ \times \mathbb{B}^n \;|\;s_{t-1}+x_t = d_t+s_t,\; x_t \le My_t,\; t=1,\...
3
votes
0
answers
70
views
Dependence of optimization problem on the linear constraints
Let $I=\{x_1,\cdots, x_n\}\subset \mathbb R$ be fixed. Given two probability distributions $\alpha=(\alpha_i)_{1\le i\le n}$ and $\beta=(\beta_i)_{1\le i\le n}$ on $I$, and a matrix $c=(c_{i,j})_{1\le ...
3
votes
0
answers
955
views
Testing if a point is inside a convex polytope formed by halfspaces in n-dimension
Assume we have a convex polytope that is formed by the intersection of $k$-halfspaces in $\mathbb{R}^{n}$.
$$
a_{0,0}x^{n-1} + {a}_{0,1}x^{n-2} + ... a_{0,n-1} \leq 0
$$
$$
a_{1,0}x^{n-1} + {a}_{1,...
3
votes
0
answers
3k
views
0,1 solution to system of linear integer equations
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
3
votes
0
answers
220
views
Could SVD be used to optimize the partial inner-products?
Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...
3
votes
0
answers
305
views
Linear complementarity problem: principal pivoting algorithm
I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book (...
2
votes
0
answers
112
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}$ (...
2
votes
0
answers
64
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 ...
2
votes
0
answers
76
views
Polyhedron coordinate bound
Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
2
votes
0
answers
45
views
Notion of distance between linear programs
Consider the linear programming problem
\begin{align}
\max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1
\end{align}
where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
2
votes
0
answers
64
views
Proving the existence of a dual for an infinite linear program
I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...
2
votes
0
answers
47
views
A linear program where coordinate descent works pretty well
I am working with a polytope $P\subset \mathbb{R}_+^n$ with the property that there are at about $n!$ minimizers of $\sum_{i=1}^n x_i$, in the following sense:
Select any coordinate $j$ and set $...
2
votes
0
answers
133
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
275
views
Derivative with multiple summation operators
I have a defined utility function as Eq.(1), and I am seeking the minimized utility subjects to some constraints. The notation used is as following:
\linebreak
$V$ is the set of nodes, $v_i\in V$; $O$...
2
votes
0
answers
43
views
Partitioning $n$-space based on linear combinations
I'm trying to figure out the approximate number of areas the positive $n$-space will be divided into if we partition it as follows: we have $k$ linear functions $F_1$, $F_2$, ..., $F_k$ on $n$ ...
2
votes
0
answers
1k
views
How to find a positive solution to an under-determined linear system (if such a solution exists)?
Like the title says, if an under-determined system of linear equations does have at least one positive solution, how to find it efficiently?
Suppose we have an under-determined system:
$$Ax = b$$
...
2
votes
0
answers
75
views
Making a polyhedron integral by selecting value for a specific co-ordinate of constraint vector
I am currently trying to solve a binary integer programming(maximization) problem, where the first row of the constraint matrix corresponds to the constraints on the total number of 1's in the vector ...
2
votes
0
answers
103
views
Optimization over a convex cone generated by a set is equal to optimization over the set
Within my research I found an important doubt and that prevents me from advancing, the context of my doubt is as follows:
We considerer the following optimization problem
$$
\left\{\begin{array}{cl} \...
2
votes
0
answers
330
views
Linear programming with an infinite matrix
I would like to solve the following infinite linear system subject to $x_i \ge 0$ that minimizes $x_3$.
The third column contains no additional nonzero values beyond what is shown. Though the first ...
2
votes
0
answers
124
views
Unveiling hidden structures
One way to unveil a hidden structure of a undirected graph - given as an adjacency matrix - is to permute the rows and columns until a pattern with a maximal geometrical symmetry is found. (The ...
2
votes
0
answers
283
views
Practical application of envelope theorem for linear programs
Assume that we have solved a (standard) linear program
$$
\text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0,
$$
and would like to know how sensitive is the optimal ...
2
votes
0
answers
61
views
Finding orthogonal basis with constraint
Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$
with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$.
And is there any condition on $V_i,i\leq ...
2
votes
0
answers
70
views
Existence of probability distribution satisfying upper/lower bounds on events
Suppose we have a finite sample space $S$ and some events $A_1, \dots, A_k \subseteq S$. We would like to put a probability distribution on $S$ so that no element has probability greater than a ...
2
votes
0
answers
176
views
Formulating shortest path as submodular minimization
I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.
The answer ...
2
votes
0
answers
147
views
Listing all Lattice Points in a Box
Let $B := [-1,1]^n$ be an $n$-dimensional box. Moreover, let $v_1,\ldots,v_n \in \mathbb{R}^n$ form a basis of $\mathbb{R}^n$, where the entries of the $v_i$ are explicitly irrational. We can assume ...
2
votes
0
answers
198
views
Finding optimal linear transformation for intersection of convex polytopes
I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue) ...
2
votes
0
answers
147
views
Derivation of gradient of SSE in Geodesic Regression
On page 79 (or page 5) of this this paper the gradient of the SSE of the Geodesic model is described explicitly. My question is how are these equitations derived in detail; where can I find the ...
2
votes
0
answers
71
views
Select n vectors from k vectors (in 3D) such that each component of the resultant vector >= each component of a given vector M
this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :)
Let $R = (R_x, R_y, R_z)$ be the resultant vector of the n vectors and $M = (M_x, ...
2
votes
0
answers
89
views
Algorithms to find the solutions of a homogenous matrix equations for non-commutative rings
In one paper from 1980 I found a note that there are no known algorithms for solving
homogenous matrix equations $x \cdot M = 0$ for matrices which elements belong to a non-commutative ring.
(The non-...
2
votes
0
answers
119
views
integrality of a linear program -- binary equality constaints
Consider the following linear program:
$\left\{
\begin{array}{l}
\underset{x}{max} \;\;c^Tx\\
[I, \;B]x = \mathbf{1}\\
x\geq 0
\end{array}
\right.$
where $c$ is a vector ...