# Tagged Questions

0answers
36 views

### k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
0answers
51 views

### How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
2answers
52 views

### linear programing : maximize $\sum \limits_{i=1}^{n} C_i$ where $C_i$ is circumference of circle with center at $\{x_i,y_i\}$

given n points on $\mathbb{R^2}$ $\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}$ formulate a linear program to maximize the sum of the circumference of all circles so any two circles won't intersect (two ...
1answer
83 views

### Stock cutting and column generation giving suboptimal answers?

I'm doing a stock cutting implementation. I use the delayed column generation approach. I'm getting suboptimal answers with the following simple case: raws length: 630 in. demands: 10 x ...
0answers
65 views

### Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
0answers
24 views

### String satisfying the condition

Given $N$, $A_0$, $B_0$, $L_0$, $A_1$, $B_1$ and $L_1$, find a sequence S consisting only of characters '$0$' and '$1$'(a total of N characters) such that: The number of '$0$'s in any consecutive ...
0answers
78 views

### Maximum matching in a non-bipartite graph

The problem is the following; I would like to reach maximum matching in a 2-connected graph, but not in an ordinary way - both of the groups of vertices that we get after the matching should remain ...
1answer
403 views

### Number of subtrees of a tree

Define a subtree to be any connected subgraph of a tree. Prove that the number of subtrees of a complete binary tree is not polynomial in the number of nodes. Give an example of a class of trees ...
0answers
173 views

### Strange but practical Bin packing problem

I am trying to solve the following MILP through LP solve. A link for the original problem is here I am re-iterating the problem as follows: I am trying to write an application that generates drawing ...
1answer
147 views

### formulate this scheduling problem as linear programming problem

Sorry if this very silly, but i am something new to optimization theory: We have $m$ identical Machines and $n$ jobs. A job $j$ can be done in any of the identical machines in $p_{j}$ time units. ...
1answer
184 views

### Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
1answer
88 views

### Minimim steps required based on game logic

I have the following simple game logic. You start with G gold and 0 experience at Time = 0 minutes. There are different types of houses what you can build, each with his own properties. House A ...
5answers
494 views

### Find a convex combination of scalars given a point within them.

I've been banging my head on this one all day! I'm going to do my best to explain the problem, but bear with me. Given a set of numbers $S = \{X_1, X_2, \dots, X_n\}$ and a scalar $T$, where it is ...
0answers
152 views

### Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron. Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
3answers
221 views

### 0-1 knapsack like - the set of all non-contained affordable binary selections

This is my first question here, so please go easy on me :) The following problem is – I think - similar to the 0-1 knapsack problem. It's simplified somehow in that each item has only a cost ...
0answers
159 views

### intuitive explanation of Primal-Dual algorithms

I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...
1answer
325 views

### Minimal set of inequalities

I have a set of $m$ linear inequalities in $R^n$, of the form $$A x \leq b$$ These are automatically generated from the specification of my problem. Many of them could be removed because they are ...
1answer
127 views

### Maximizing a linear combination of certain integers

Consider some tuple $x = (x_1, ..., x_k) \in \mathbb{N}^k$ of $k$ non-negative integers such that $x_1 > x_1 > ... > x_k$ and suppose that $A \subset \mathbb{N}^k$ is such that there exists a ...
2answers
503 views

### Minimizing Sum of Product

I'm given 3 multisets $A$, $B$, and $C$ each with $n$ elements. Now I'm to form $n$ (say $D_1$ to $D_n$) multisets of 3 elements each from $A$, $B$, and $C$, such that each of these $n$ multisets ...
1answer
245 views

### What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
1answer
893 views

### Two-Phase Method (Linear Programming)

In Linear programming, when is it beneficial to use the Two-Phase Method? Why not just use the Simplex Method? (edit: typo)
1answer
230 views

### Lower bound for the complexity of linear programming

Since it is known that you can sort $n$ numbers by solving a certain kind of linear program - doesn't this imply a lower bound on the complexity of solving linear programs in general via the lower ...
1answer
1k views

### Finding all n×n permutation matrices

If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions? Here's Wikipedia on doubly stochastic matrices.
3answers
1k views

### What is linear programming?

I asked this question on Stack Overflow but it was closed as "not programming related". So I think this is probably the best place for it... I read over the wikipedia article, but it seems to be ...