The linear-programming tag has no usage guidance.

**1**

vote

**1**answer

181 views

### Covering max flow arcs by arc disjoint paths

Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x_a)_{a\in A}$ be a maximum $(s,t)$-flow. Is it ...

**0**

votes

**1**answer

207 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, ...

**2**

votes

**2**answers

546 views

### Sherali-Adams relaxation

I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...

**5**

votes

**1**answer

239 views

### Checking if one polytope is contained in another

Hi,
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 ...

**2**

votes

**1**answer

109 views

### Design constraint systems over the reals

This question is inspired by the discussion at this problem.
Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...

**2**

votes

**2**answers

822 views

### how to model a linear program with step-like cost function in the objective

I have a large linear program with the following details.
d1 to di are the variables, where di is an integer. The constraints are a series of inequalities of the form
d1 < d3 < d7 < d23 ...

**7**

votes

**2**answers

1k 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.

**3**

votes

**0**answers

949 views

### 0,1 solution to system of linear integer equations.

I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...

**3**

votes

**0**answers

189 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 ...

**7**

votes

**1**answer

281 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 ...

**2**

votes

**2**answers

1k views

### Solving a system of equations/inequalities that have trigonometric functions on the left-hand side

Is there any known (symbolic) method that solves a system of equations/inequalities that have trigonometric functions on the left-hand side of the system?
Ex) Find $x,y,\theta \in \mathbb{R}$ that ...

**4**

votes

**1**answer

1k 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 ...

**1**

vote

**1**answer

190 views

### Conditions for differentiability of minima and minimizers of linear functionals?

Let $B$ be a (real) Banach space and $C$ be a compact convex subset of $B$.
For every continuous linear functional $F$ on $B$, define
$V(F)=min_{c\epsilon C} F(c)$ and
$S(F)= { \lbrace c \epsilon C ...

**3**

votes

**1**answer

442 views

### Solving for Hamiltonian path with constraints on allowable routes through vertices

Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the ...

**0**

votes

**1**answer

371 views

### Minimum distance between two data sets

Suppose we have two sets of data, $X$ and $Y$, each of which contains
$10$ positive numbers. Now let us order the data sets $X=\left\{ x_{1},\cdots,x_{10}\right\}$,
$x_{1}\ge\cdots\ge x_{10}>0$ and ...

**1**

vote

**0**answers

797 views

### How to solve simple bilinear equations under extra linear constraints

Hello,
This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy:
$\lambda_i^T ...

**1**

vote

**1**answer

640 views

### Can one efficiently optimize over the inverse of matrix?

Hello,
I have the following problem:
Find a non-negative matrix $L$ (i.e. $L_{i,j} \geq 0$ for all $i,j$), $L \neq I$ so that $A(I-L)^{-1}y \geq 0$ (the inequality must hold for each component), ...

**0**

votes

**0**answers

111 views

### sparsest cut always has solution

Hi!
How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset.
Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...

**1**

vote

**1**answer

237 views

### Approximate Set Cover Problem by Rounding

Here is the simple algorithm for approximating set cover problem using rounding:
Algorithm 14.1 (Set cover via LP-rounding)
Find an optimal solution to the LP-relaxation.
Pick all sets ...

**1**

vote

**1**answer

98 views

### Are there intuitive/classically algorithmic analogues to Semidefinite programs on networks?

Many network optimization algorithms, including shortest path, push-relabel, augmenting path, etc, actually have an interpretation in terms of linear programming.
A famous application of semidefinite ...

**1**

vote

**1**answer

383 views

### Need help to find an efficient algorithm for the following problem!

Consider $x$ an n-dimensional vector with $x_i$ is integer in the range $[0 \dots k], k\in N$.
Given $A_{n\times n}$ is the covariance matrix of $x$.
$u$ is a given n-dimensional vector of real ...

**0**

votes

**1**answer

252 views

### Lovasz theta function - uses

Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?

**3**

votes

**1**answer

285 views

### Partially optimal solutions in integer linear programming

Linear programs with a totally unimodular system matrix are known to have an optimal integer point. They are therefore solvable via relaxing the integer constraints to intervals.
An other interesting ...

**4**

votes

**3**answers

581 views

### Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...

**2**

votes

**0**answers

437 views

### Guessing game with guess cost

This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...

**10**

votes

**1**answer

542 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 ...

**2**

votes

**0**answers

240 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 ...

**3**

votes

**1**answer

319 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 ...

**1**

vote

**2**answers

1k 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 ...

**6**

votes

**3**answers

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 ...

**2**

votes

**0**answers

173 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 ...

**3**

votes

**2**answers

3k 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 ...

**2**

votes

**5**answers

978 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 ...

**5**

votes

**0**answers

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 ...

**3**

votes

**0**answers

593 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 ...

**1**

vote

**1**answer

3k 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
...

**4**

votes

**2**answers

444 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 ...

**2**

votes

**2**answers

239 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 ...

**2**

votes

**1**answer

975 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 ...

**11**

votes

**2**answers

1k 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 ...

**1**

vote

**1**answer

176 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 ...

**4**

votes

**2**answers

490 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

**2**

votes

**1**answer

272 views

### existence of l1 embedding using LP feasibility

hello
Let (A, d) be an n-point metric space
for $t \geq 1$,the task it to find an integer $m$ and an embedding $f : A \rightarrow R^m$ s.t.
$\forall x,y \in A$ : $d(x,y) \leq d_1(f(x), f(y)) \leq ...

**1**

vote

**1**answer

489 views

### Split sum into equal terms

Given a sum of $l$ integers $r_1+...+r_k+...+r_l$ and an integer $t$.
Find indices
$1 < p_1 <...< p_h <...< p_{t-1} < l$
such that in sum
...

**2**

votes

**4**answers

452 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 ...

**2**

votes

**0**answers

290 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 ...

**3**

votes

**3**answers

3k 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 ...

**4**

votes

**4**answers

582 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 ...

**0**

votes

**2**answers

751 views

### Degenerate case of linear programming duality?

Let's say we have a maximization linear program that looks like this: maximize $\vec{c}\vec{x}$, subject to $\matrix{A}\vec{x} \leq 0$, $\vec{x} \geq 0$. If we take the dual, we have "minimize ...

**13**

votes

**0**answers

2k 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?