**25**

votes

**6**answers

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

**24**

votes

**2**answers

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

**23**

votes

**4**answers

2k views

### Why are optimization problems called “programming”?

Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...

**14**

votes

**2**answers

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

**14**

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?

**11**

votes

**3**answers

776 views

### Deciding membership in a convex hull

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

**11**

votes

**2**answers

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

**10**

votes

**1**answer

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

**10**

votes

**1**answer

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

**10**

votes

**1**answer

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

**8**

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.

**7**

votes

**1**answer

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

**7**

votes

**1**answer

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

**7**

votes

**3**answers

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

**7**

votes

**2**answers

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

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

**6**

votes

**1**answer

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

**6**

votes

**1**answer

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

**6**

votes

**1**answer

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

**6**

votes

**1**answer

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

**6**

votes

**0**answers

118 views

### A specific case of the $p$-center problem

Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...

**5**

votes

**1**answer

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

**5**

votes

**2**answers

411 views

### Multiplicative gradient descent?

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$?
I know ...

**5**

votes

**1**answer

354 views

### Examples of Polyhedra with Large Shadows

Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...

**5**

votes

**2**answers

4k 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 $...

**5**

votes

**1**answer

118 views

### Resource Constrained Routing with Refueling

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...

**5**

votes

**1**answer

436 views

### Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...

**5**

votes

**1**answer

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?

**5**

votes

**2**answers

369 views

### relation between solution of a linear program and its perturbation

I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$:
$$
\max_j c' x_j
$$
Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...

**5**

votes

**0**answers

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

**5**

votes

**0**answers

178 views

### A linear optimization problem on a graph

Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...

**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 http://arxiv....

**4**

votes

**2**answers

261 views

### point in polytope

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

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

**4**

votes

**2**answers

307 views

### Minimax theorem on a non convex domain

A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$:
$$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{...

**4**

votes

**4**answers

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

**4**

votes

**3**answers

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

**4**

votes

**2**answers

548 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

**4**

votes

**1**answer

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

**4**

votes

**2**answers

149 views

### combinatorial and linear duality

Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual $\...

**4**

votes

**3**answers

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

**4**

votes

**1**answer

137 views

### Basic result in semi-infinite linear programming

Consider a standard linear program of the form $$\textrm{minimize}_x~~~~ c^Tx~~~~ s.t. \\ Ax = b \\ x \geq 0$$ with $x\in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. It is well known that, if ...

**4**

votes

**2**answers

556 views

### Simplified knapsack problem

There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...

**4**

votes

**2**answers

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

**4**

votes

**1**answer

238 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

511 views

### Bounding the minimal maximum norm of a solution of a linear system.

I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear ...

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

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

**4**

votes

**1**answer

162 views

### Constrained optimization (QCLP) over $x$ with the constraint $x = Az$

I have a problem that looks very much like a (norm-constrained) linear program, but with an extra constraint that is unusual for me. The problem is, given a matrix $A$ and a vector $w$,
$$ \min_{x \...

**4**

votes

**0**answers

135 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 & \...