Linked Questions

40 votes
4 answers
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 ...
Sasha the Noob's user avatar
15 votes
3 answers
3k views

Cast to boolean, for integer linear programming

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,...
D.W.'s user avatar
  • 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 ...
andy's user avatar
  • 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 ...
Csabo E.'s user avatar
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}$). ...
marshall's user avatar
  • 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 ...
bjornte's user avatar
  • 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 \...
Alex's user avatar
  • 215
4 votes
1 answer
332 views

Card-buying algorithm

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 ...
The Oddler's user avatar
4 votes
2 answers
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 ...
Lindenk's user avatar
  • 143
4 votes
1 answer
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 ...
Felix's user avatar
  • 143
4 votes
5 answers
10k views

"Greater than" condition in integer linear program with a binary variable

How can one model the following condition in an integer linear program? $$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$ where $A \in \{0,1\}$ and $B, C \in \...
Salah's user avatar
  • 91
4 votes
1 answer
81 views

Computing Nash equilibria in discrete auctions

I am trying to compute the (pure strategy) Nash equilibria of some discrete auctions. More precisely, let us define the strategy of each player as a function mapping from every valuation that they ...
afreelunch's user avatar
4 votes
1 answer
190 views

Integer Problem Solving with two boolean selection variables

I am trying to solve a two dimensional combinatorial problem. Hereis my input space {{RA1,RA2},{RB1,RB2},{RC1,RC2}} and i have to choose two out of three elements{A,B,C} and one out of two possible ...
Jiterika's user avatar
3 votes
1 answer
2k views

Converting If-else condition to Linear Programming

I have a constraint in a linear programming formulation with two variables: $X \ge Y$ To which I want to apply the following if-else conditions: ...
asm_nerd1's user avatar
  • 229
3 votes
1 answer
4k views

Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?

Karp's 21 NP-complete problems show that 0-1 integer linear programming is NP-hard. That is, an integer linear program with binary variables. If we set the $c^T$ vector of the objective $\text {...
Mat's user avatar
  • 502

15 30 50 per page
1
2 3 4 5