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.

Filter by
Sorted by
Tagged with
34 votes
4 answers
5k views

Why are optimization problems often called "programs"?

Why are optimization problems often called programs? linear programming geometric programming convex programming Integer programming ...
ziggystar's user avatar
  • 451
29 votes
6 answers
8k views

How to find a closest integer point to the intersection of two lines?

Here's a question that originates from StackOverflow. Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
P Shved's user avatar
  • 391
26 votes
5 answers
1k 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 ...
user42804's user avatar
  • 1,091
25 votes
2 answers
2k views

An Interesting Optimization Problem

You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
Praveen Dhinwa's user avatar
24 votes
3 answers
1k 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 ...
darij grinberg's user avatar
19 votes
4 answers
1k views

Applications of linear programming duality in combinatorics

So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
amakelov's user avatar
  • 987
19 votes
2 answers
2k views

Is the tensor product of polyhedra a polyhedron?

Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
darij grinberg's user avatar
18 votes
3 answers
3k views

Deciding membership in a convex hull

Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$. This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
Mitch's user avatar
  • 657
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,...
Louis Deaett's user avatar
  • 1,513
15 votes
3 answers
989 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? ...
Pedro Ruiz's user avatar
14 votes
3 answers
1k views

The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$

Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum: $$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$ ...
TOM's user avatar
  • 2,218
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
13 votes
2 answers
660 views

Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason. Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$. I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
JSE's user avatar
  • 19.1k
13 votes
3 answers
815 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 ...
12 votes
1 answer
5k views

Closest 3D rotation matrix in the Frobenius norm sense

Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm: \begin{equation} \|R-M\|_F \end{equation} Is there a closed form solution for $R$, or is it ...
Alex Flint's user avatar
11 votes
3 answers
6k views

Random Sampling a linearly constrained region in n-dimensions...

Hi, So here is my problem: Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$ $x_n \le c_n$ and $\sum_{n=1}^N x_n = 1$ find an ...
user1's user avatar
  • 113
10 votes
2 answers
843 views

Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?

Sphere packing problem in $\mathbb R^n$ asks for the densest arrangement of non-overlapping spheres within $\mathbb R^n$. It is now know that the problem is solved at $n=8$ and $n=24$ using modular ...
VS.'s user avatar
  • 1,816
10 votes
2 answers
3k views

How do you tell if a system of linear inequalities has a solution?

A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
user21816's user avatar
  • 683
10 votes
3 answers
6k views

Solving a system of linear inequalities -- what is the dimension of the solution set?

It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$? For the applications I have in mind the ...
Matthew Kahle's user avatar
10 votes
1 answer
2k views

Sum of difference moduli vs. sum of modulus differences

This is a failed attempt of mine at creating a contest problem; the failure is in the fact that I wasn't able to solve it myself. Let $x_1$, $x_2$, ..., $x_n$ be $n$ reals. For any integer $k$, ...
darij grinberg's user avatar
10 votes
1 answer
398 views

Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$. Now add edge-pair ...
Brendan McKay's user avatar
10 votes
0 answers
655 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
9 votes
1 answer
3k views

Inverse of a totally unimodular matrix

A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A ...
qianchi 's user avatar
9 votes
1 answer
6k views

Proving that a binary matrix is totally unimodular

I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...
AaronDefazio's user avatar
9 votes
2 answers
772 views

How did they come up with the MRRW bound?

Among the good asymptotic bounds in coding theory in the MRRW bound. It is obtained by using the linear programming problem of Delsarte's and providing a solution. The LP problem is Suppose $C \...
Breakfastisready's user avatar
9 votes
1 answer
288 views

Definition of packing property

Definition 1: A clutter $C$ is said to have the packing property if $C$ and all of its minors satisfy the König property. where, vertex cover of $C$ is a set of vertices that have non-empty ...
user177523's user avatar
9 votes
1 answer
1k views

Uniform sampling from general simplex with a twist

This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange. Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
Juanito's user avatar
  • 221
8 votes
2 answers
246 views

Are sums of 0-1 Pareto efficient vectors Pareto efficient?

Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that: The entries of $A$ are $\in \{0, 1\}$. For all pairs of columns $u, v$ of $A$ the entries of $u - ...
Daishisan's user avatar
  • 378
8 votes
2 answers
928 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 ...
Alan Swindells's user avatar
7 votes
2 answers
820 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}^...
Erik's user avatar
  • 81
7 votes
2 answers
960 views

Is a given point in the interior of the convex hull of a given finite collection of points?

Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
Igor Rivin's user avatar
  • 95.6k
7 votes
1 answer
351 views

Does the Hirsch conjecture hold for $n < 2d$?

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 ...
Matthew Kahle's user avatar
7 votes
1 answer
793 views

Has this generalization of a determinant (assigning multiplicities to the rows) been studied?

I'm working on some questions in tropical geometry, and my problem led me to create the following generalization of a determinant: Let $A$ be an $m \times n$ matrix with $m \le n$, and positive ...
Drew's user avatar
  • 1,469
7 votes
1 answer
347 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 ...
Steve Huntsman's user avatar
7 votes
1 answer
219 views

A polytope with a bound on the sum of any $k$ variables

Let $2\le k\le n-1$ and define the polytope $$P_k(n) = \lbrace (x_1,\ldots,x_n) \in \mathbb{R}^n : -1\le x_{i_1}+\cdots +x_{i_k} \le 1 \text{ for all } 1\le i_1\lt\cdots\lt i_k\le n\rbrace.$$ There ...
Brendan McKay's user avatar
7 votes
1 answer
382 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)$. ...
bodhisat'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
6 answers
2k views

Circumference of Convex Shapes

Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
Matthias Goergens's user avatar
6 votes
2 answers
1k views

Linear programming is continuous

Consider an arbitrary linear program: $$\max \vec c \cdot \vec x$$ subject to: $$\textbf{A}\cdot \vec x = 0, \quad \vec a \le \vec x \le \vec b$$ Assume that this program is feasible and bounded. ...
valle's user avatar
  • 864
6 votes
1 answer
674 views

Checking if one polytope is contained in another

I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other. At the moment I am ...
bandini's user avatar
  • 491
6 votes
2 answers
7k views

Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations

Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
Adam Clarridge's user avatar
6 votes
3 answers
1k views

A simple infinite dimensional optimization problem

I'd be grateful for a reference for the following result, which I believe to be true, and should be well-known. Let the continuous functions $f_0,f_1,\cdots,f_n: [0,1]\rightarrow [0,\infty)$ be ...
Guy Katriel's user avatar
6 votes
1 answer
602 views

Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers

Let $a(n)$ be the Dirichlet inverse of the Euler totient function: $$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$ and let the matrix $T(n,k)$ be: $$T(n,k)=a(\gcd(n,k)) \tag{2}$$ It has been ...
Mats Granvik's user avatar
  • 1,133
6 votes
1 answer
670 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 ...
aroyc's user avatar
  • 221
6 votes
3 answers
10k views

Maximum flow with negative capacities?

I'm trying to compute an (s-t) maximum flow through a network which includes a number of arc pairs ((u,v), (v,u)) that have equal, negative capacities (weights). I'm not aware of any efficient ...
Fumiyo Eda's user avatar
6 votes
1 answer
661 views

If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?

I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...
ArtificiallyIntelligent's user avatar
6 votes
1 answer
240 views

Algorithm that solves every Mixed Integer Linear Program (to optimality)?

Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically? I know that you usually ...
J Fabian Meier's user avatar
6 votes
1 answer
1k views

Speed up Linear programming

I have a linear programming problem like this: minimize $c^t X$ under the constraint that $AX \ge b$. I will need to solve this linear programming problem online many times. I need it to be as fast ...
Robert's user avatar
  • 83
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

1
2 3 4 5
10