24k views

### Why is linear programming in P but integer programming NP-hard?

Linear programming (LP) is in P and integer programming (IP) is NP-hard. But since computers can only manipulate numbers with finite precision, in practice a computer is using integers for linear ...
3k views

I want to express the following constraint, in an integer linear program: $$y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases}$$ I already have the integer variables $x,... • 159k 14 votes 2 answers 690 views ### Does every NP problem have a poly-sized ILP formulation? Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem ... • 253 5 votes 2 answers 822 views ### How to reduce the low-rank matrix completion problem to integer programming? Consider the low-rank matrix completion problem: Given an integer$k$and a subset of entries of some$n \times n$matrix, fill in the rest of the entries so that the resulting matrix has rank at ... • 51 5 votes 2 answers 338 views ### Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel Given integers$n,m$, I want to find a$m \times n$binary matrix$X$such that there does not exist any non-zero vector$y \in \{-1,0,1\}^n$with$Xy=0$(all operations performed over$\mathbb{Z}$). ... • 143 5 votes 1 answer 716 views ### Nesting algorithm for rectangular-based, fixed-orientation polygons I'm looking for an algorithm that is closely related to the 2-dimensional nesting problem (also known as lay planning, bin packing, and the cutting stock problem). The main differences between this ... • 151 4 votes 1 answer 250 views ### Maximum minimal set coverage Suppose we are given a universal set$U$and a family of subsets of$U$, denoted by$F$(elements in$F$are subsets of$U$). We assume that all elements in$F$can cover$U$, i.e.,$U\subseteq \...
• 215
332 views

I'm trying to make an algorithm to calculate what combination of cards from what buyers I should get to get the cheapest deal. Taking the shipping costs into consideration. It's for a website called ...
• 143
849 views

### Schedule tasks from a weighted list with time frame constraints

I'm attempting to create an automatic scheduler from a list of tasks I have available. Here are the key points: Each task has been given a priority beforehand and the algorithm should try to maximize ...
• 143
82 views

### Optimising an exhaustive search for a card game

I'd like to search for a combination of resources that when used, would produce at least up to a threshold of different kinds of materials. For the majority who are not in the know, I'll use an ...
• 143