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
Filter by
Sorted by
Tagged with
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?
didest's user avatar
  • 1,015
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 ...
Fedor Petrov's user avatar
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 & \...
Jerry Jiannan Lu's user avatar
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 ...
Carrie Nuttall's user avatar
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\...
Robert Lowell's user avatar
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 ...
Matt's user avatar
  • 61
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 $$...
Fetchinson0234's user avatar
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) = ...
user109711's user avatar
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 ...
TOM's user avatar
  • 2,218
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....
Victor Miller's user avatar
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 ...
David Harris's user avatar
  • 3,397
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 $\...
R W's user avatar
  • 16.6k
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....
D. Rusin's user avatar
  • 381
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 ...
user6546's user avatar
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 ...
Bogdan's user avatar
  • 781
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 $...
M. Winter's user avatar
  • 12.5k
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+\...
Math_Y's user avatar
  • 311
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 ...
Gilles Mordant's user avatar
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 ...
Doris's user avatar
  • 131
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 ...
Turbo's user avatar
  • 13.6k
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,\...
Kuifje's user avatar
  • 225
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 ...
CodeGolf's user avatar
  • 1,837
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,...
rajaditya_m's user avatar
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 ...
Wisdom's Wind's user avatar
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 ...
usero's user avatar
  • 131
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 (...
Jay Lemmon's user avatar
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}$ (...
Diego Fonseca's user avatar
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 ...
Dmitry's user avatar
  • 221
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\|_\...
Turbo's user avatar
  • 13.6k
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 ...
dineshdileep's user avatar
  • 1,371
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-...
teddy's user avatar
  • 121
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 $...
Sean M. Cook's user avatar
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 ...
Frederik vom Ende's user avatar
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$...
Dehao 's user avatar
  • 21
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$ ...
wfe2016's user avatar
  • 21
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$$ ...
KOF's user avatar
  • 121
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 ...
A.2's user avatar
  • 123
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} \...
matematicaActiva's user avatar
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 ...
user3433489's user avatar
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 ...
Hans-Peter Stricker's user avatar
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 ...
Bogdan Grechuk's user avatar
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 ...
Jiayi Liu's user avatar
  • 909
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 ...
Daniel's user avatar
  • 21
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 ...
user306101's user avatar
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 ...
User133713's user avatar
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) ...
Artemy's user avatar
  • 650
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 ...
ABIM's user avatar
  • 4,989
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, ...
Jean Lille's user avatar
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-...
Leonid Dworzanski's user avatar
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 ...
Ali's user avatar
  • 117