The tag has no usage guidance.

learn more… | top users | synonyms (1)

6
votes
3answers
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 ...
23
votes
5answers
4k views

How to find a closest integer point to intersection of two lines?

Hello. 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, each of them has at least two integer points ...
10
votes
1answer
277 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 ...
1
vote
1answer
391 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. ...
1
vote
1answer
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 ...
0
votes
1answer
205 views

Linear programming with exponentially many constraints and variables [closed]

From class, I learnt that problems like traveller salesman have a Linear programming representation with exponentially many constraints. Using method of separation, this problem is solved rather ...
4
votes
2answers
473 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
2answers
235 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 ...
2
votes
1answer
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
5answers
931 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 ...
1
vote
1answer
276 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 ...
1
vote
1answer
599 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), ...