Tagged Questions

0
votes
1answer
49 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 ...
0
votes
0answers
27 views

Example of delayed column generation

Can someone point me to a small example of how delayed column generation works for the cutting stock problem. I have found several sources that describe it abstractly but I still don't understand ...
0
votes
0answers
19 views

SLP solution algoritm to implement/use in Java

Starting from the vector $\mathbf{s}_0$, determine $\mathbf{s}$, the solution of: $$ \left\{\begin{array}[ll] \text{min} & \nabla f(\mathbf{x})^\mathrm{T} \mathbf{s} \\ \text{s.t.} & ...
2
votes
1answer
79 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 ...
4
votes
5answers
143 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 ...
2
votes
0answers
53 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 ...
3
votes
3answers
187 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 ...
-5
votes
1answer
94 views

What approach can be used to solve this? [closed]

The problem can be found here. The game is simple. You initially have ‘H’ amount of health and ‘A’ amount of armor. At any instant you can live in any of the three places - fire, water and air. ...
2
votes
0answers
113 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 ...
2
votes
0answers
71 views

Branch-and-Price algorithms for IP/MIP

I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
3
votes
1answer
96 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 ...
2
votes
1answer
68 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 ...
0
votes
0answers
41 views

Object selection algorithm to fulfill multiple value criteria

Sorry if I don't explain this too well, but here goes: I'm trying to find an algorithm that will randomly select objects with different attributes to match specific criteria. The best way to explain ...
0
votes
0answers
115 views

Gram-Schmidt orthogonalization process for Hermite functions

I am trying to do Gram-Schmidt orthogonalization process for functions. I need to use this process on [-1,1] for the Hermite functions with n=1,2,...40: $$ h_n(x)=(-1)^n\gamma_ne^{x^2/2} ...
1
vote
2answers
223 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 ...
3
votes
1answer
154 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) ...
1
vote
1answer
695 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)
1
vote
1answer
188 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 ...
4
votes
1answer
631 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.
6
votes
3answers
892 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 ...