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

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

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

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

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

**1**

vote

**1**answer

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

**1**

vote

**1**answer

550 views

### Finding a point farthest away from $k$ points in a polygon

There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.
...

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

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

**3**

votes

**6**answers

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

**2**

votes

**1**answer

110 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

**1**answer

479 views

### optimization of inverse matrix with constraint on matrix elements

everyone! I have this optimization problem with constraint.
$D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter.
$x$ and $v$ are two known p-dimensional vectors.
The ...