# Tagged Questions

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.

321 views

### Mathematical Programming with other Algebras than Linear

Linear Programming is strongly entwined with linear algebra, as are many of its generalizations under the heading of mathematical programming / convex optimization. What analogies are there for ...
2k views

### Linear programming - uniqueness of optimal solution

Is it possible to build such an objective function for a given set of constraints, so that there will be only one optimal solution? My general problem is to get any vertex of a polytope formed by a ...
2k 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 ...
184 views

### Number of breakpoints in parametric maximum flow problems

The parametric maximum flow problem can be formulated as $$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right),$$ where all $c_{ij}<0$ (so that ...
4k views

### Linear program to maximize the minimum absolute value of linear functions ?

I'd like to compute $\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$. where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$. Can this be solved with a linear ...
1k 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 ...
184 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....
646 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 ...
4k views

### Detection of Redundant Constraints

Suppose I pose the following query to a constraint logic programming system: ?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3. Are there systems that would recognize the last inequality as ...
454 views

### Continuous Transportation Problem

Hi all, I'm trying to formulate an infinite linear program to prove optimality (via duality) for the Continuous Transportation Problem, e.g. the Kantorovich-Wasserstein distance. This is the ...
252 views

### Maximization of a matrix product by iterative methods

This might not be very difficult, but I think I may have gotten a little confused. Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x ...
1k views

### solving multiple linear programming problems with the same set of constraints

Hi, I need to solve a set of linear programs of the form: Problem $i$: $\quad \max c_i \cdot x$ s.t. $A x \leq b$. The $c_i$'s are different vectors so each problem has a different objective ...
2k 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 ...
187 views

### Model for shipping widgets in an optimal way

I am a programmer and have the following requirement. We are trying to figure out the optimal way to ship widgets. Below is the scenario: We need to ship 1,000,000 widgets We have two different ...
559 views

### Set Cover:Greedy vs LP

Hi Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches? thanks
275 views

512 views

### Efficient algorithm for finding the minima of a piecewise linear function

Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by $f(x) = \max_i ( a_i + b_i x )$ We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two lines:...
332 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 ...
4k 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 ...
601 views

### efficient way to compute the inversion of the following matrix

Hi, there I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special ...
818 views

499 views

### When is a triangular matrix totally unimodular?

I have an {0,1}, invertible, triangular matrix, that I would like to show to be totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
248 views

### Feasibility of linear programs

It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?
3k views

Mathematical problem. Suppose we have $2n$ indeterminates $x_1,\dots,x_n$ and $y_1,\dots,y_n$ (which are denoted by $q$ with indices and called abundances below) and $m$ subsets $P_1,\dots,P_m$ of $\... 0answers 604 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 ... 3answers 548 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 ... 6answers 5k views ### How to find a closest integer point to intersection of two lines? Here's a question that originates from StackOverflow (and the SO crowd isn't really qualified to solve it). We're given two lines on the plane, specified by equations ($a x + b y = c$) whose ... 0answers 1k views ### Covariance matrix formula interpretation - what am I missing? I'm reading a paper that outlines the calculation of a covariance matrix like the following:$C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$What is the order of this matrix? My interpretation ... 4answers 3k views ### Linear programming piecewise linear objective I am fairly new at linear programming/optimization and am currently working on implementing a linear program that is stated like this: max$\sum_{i=1}^{k}{p(\vec \alpha \cdot \vec c_i)}s.t. |\...
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$, ...
Problem: 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$)...