The linear-programming tag has no wiki summary.

**1**

vote

**1**answer

185 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

398 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

362 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

717 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

585 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

229 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

382 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

239 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

277 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

559 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

405 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

537 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

236 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

168 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

920 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

183 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

542 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

437 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

232 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

933 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

171 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

446 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

487 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

406 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

275 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

570 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

705 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

466 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

726 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

892 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}$
...

**4**

votes

**1**answer

1k views

### How to find which subset of bitfields xor to another bitfield?

I have a somewhat coding-oriented problem. I have a bunch of bitfields and would like to calculate what subset of them to xor together to achieve a certain other bitfield, or if there isn't a way to ...

**1**

vote

**1**answer

2k views

### what is the difference between the revised simplex method andthe full tableu?

No to sound naive but they look like they include the same steps to me, one's just the algorithmical representation of the other. Thanks in advance.

**2**

votes

**0**answers

265 views

### Recovering a piecewise affine function

Lets say I have an piecewise affine convex function $f(x_1,x_2)$, on which the following operations are possible:
Computing $f(x_1,x_2)$.
Computing a subgradient to $f$ at $(x_1,x_2)$
Computing all ...

**2**

votes

**2**answers

474 views

### Sorting a binary matrix diagonal in polynomial time while preserving rows

Is there a polynomial time solution to sort an arbitrary binary square matrix in polynomial time by rows so that the diagonal contains a 1 if any row contains a 1 in that column?
For example given ...

**0**

votes

**1**answer

870 views

### For Ax = b, x and b unknown vectors, how do I solve the x that maximizes min(b_i)?

Given a matrix $A$, each element $A_{i,j} \geq 0$, find the vector $\vec x$ that maximizes the minimum element in $\vec b$ ($\vec b = A \vec x$). Note that this is not a linear equation system as I ...

**2**

votes

**2**answers

898 views

### Continuous Linear Programming: Estimating a Solution

I have a "continuous" linear programming problem that involves maximizing a linear function over a curved convex space. In typical LP problems, the convex space is a polytope, but in this case the ...

**4**

votes

**1**answer

234 views

### Symmetry of the integer gap

Are there results that bound the asymmetry of the duality gap of an integer program? That is to say, if the difference between the LP solution and the IP (primal) solution is $a$, is there a function ...

**4**

votes

**2**answers

1k views

### Applications of minmax theorem(s)

Intro We suppose $X$ and $Y$ are nonempty sets and f: $X\times Y \rightarrow \mathbb{R}$. A minimax theorem is a theorem that asserts that, under certain conditions,
$$ \inf_Y \sup_X f = \sup_X ...

**1**

vote

**3**answers

2k views

### How to solve Linear Programming problem with tighter Integer Programming constraints

I want to learn a bit about Linear Programming.
After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally ...