The linear-programming tag has no usage guidance.

**4**

votes

**1**answer

230 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

107 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

790 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

913 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

187 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

278 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

188 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

421 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

367 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

765 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

606 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

233 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

248 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

282 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

575 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

431 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

539 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

239 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

171 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

941 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

578 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

441 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

234 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

951 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

175 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

465 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

488 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

437 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

281 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

576 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

723 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?

**1**

vote

**1**answer

477 views

### Linear Programming Cost Function [closed]

I need to add the following to my LP problem:
If the amount of workers hired in period $t$ ($H_t$) is higher than 25, the hiring cost is only 1 instead of 1.2.
Example: if 30 workers are hired in ...

**1**

vote

**4**answers

742 views

### Maximum average value within a rectangular bounding box

The goal is to expedite detection using the sliding window approach. In other words, an object classifier is known and I need to find where the possible locations of this object are in an image. This ...

**1**

vote

**2**answers

917 views

### Inequality-constrained linear-regression, what is the covariance of the estimator?

If you do a linear regression: $||Ax - e ||^2$, where e is iid Gaussian, mean 0 and variance 1, then your answer is $x_{hat} = (A' A)^{-1} (A' * e)$ and the covariance of $x_{hat}$ is $(A' A)^{-1}$
...