0
votes
0answers
20 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
0
votes
1answer
71 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 ...
0
votes
1answer
39 views

Designing an algorithm to determine if a linear combination of k-1 sets is contained in the k-th set .

I am trying to solve the following problem - given $k$ sets : $A_1,A_2,...,A_k$ containing $O(n)$ integers each I need to design an algorithm that will determine if there is such a group of elements ...
1
vote
0answers
38 views

convexity in oriented matroid theory

I would like to try to solve the following problems. If someone knows how to prove at least part (a), could you show me the proof? I am having a LOT of trouble understanding oriented matroid theory. ...
1
vote
0answers
150 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 ...
0
votes
1answer
139 views

Optimal Solution Set To Linear Programs

I have the following assignment question, and I am not quite sure how to proceed. Q: Consider the following LP (P): $\max\{{c^Tx:Ax=b, x \geq 0}\}$, where $A$ is an $m$ by $n$ matrix. Prove or ...
0
votes
1answer
150 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 ...
1
vote
0answers
21 views

Sufficiency of the condition for this linear programming problem to have solutions.

I'm looking for $x_1,x_2,x_3$ which satisfy the following constraints: $$ \begin{align*} &x_1,x_2,x_3\geq 0\\ &x_1+x_2\geq a\\ &x_2+x_3\geq b\\ &x_3+x_1\geq c\\ &x_1+x_2+x_3=1 ...
0
votes
1answer
77 views

Solution for assigning independent tasks to independent individuals

I have $n$ tasks that I wish to delegate to $m$ independent individuals, where $m$ is a factor or divisor of $n$. Each of the tasks $T_{1} ... T_{n}$ is independent. From the following two extremes, ...
6
votes
0answers
85 views

Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture states that the graph (i.e. $1$-skeleton) of a $d$-dimensional polytope with $n$ facets has diameter at most $n - d$. It was known for a long time that it sufficed to prove it ...
3
votes
1answer
73 views

The Hirsch conjecture in $3$-dimensions

What I am wondering is if the Hirsch conjecture has a simple proof (just a few lines) in $3$ dimensions, perhaps by using Steinitz's theorem or Kuratowski's theorem and some kind of induction ...
4
votes
1answer
325 views

Linear programming for combinatorics/graph theory

I just went to a graph theory talk talking about various fractional graph parameters (but focusing on one). These were defined using linear programming. A question was asked, "How can we learn more ...
3
votes
2answers
174 views

How many ${0, 1}$ solutions would this system of underdetermined linear equations have?

The problem: I have a system of N linear equations, with K unknowns; and K > N. Although the equations are over $\mathbb Z$, the unknowns can only take the values 0 or 1. Here's an example with N=11 ...