Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
28 views

Integer Linear Programs: An instance or not?

Given a set of integers $\{x_0, x_1, ... , x_{n-1}, x_n\} \subseteq \mathbb{Z}$, a set of integer variables $\{y_0, y_1, ... ,y_{n-1}, y_n\} \subseteq \mathbb{Z}$ and an integer $m \in \mathbb{Z}$ is ...
-2
votes
0answers
18 views

Hello,Unable to solve linear programming relaxation problem [duplicate]

Hollywood. A lm producer is seeking actors and investors for his new movie. There are n available actors; actor i charges si dollars. For funding, there are m available investors. Investor j will ...
2
votes
0answers
22 views

Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming

I have recently been working on an applied project where I have to solve optimization problems. I have found that it is much easier to solve an integer linear program (ILP) as opposed to a ...
2
votes
0answers
37 views

How can k-means be reduced to Integer Programming

The k-means algorithm reduces to computing the objective function: $ \underset{\textbf{S}}{\operatorname{argmax}} \sum_{i=1}^k \sum_{\textbf{x}_j\in\textbf{S}_i} \lVert \textbf{x}_j - \mathbf{\mu}_i ...
3
votes
0answers
71 views

Formulating Integer Program for passing packages on a cycle

Can't seem to figure out the IP formulation for this. Question Suppose there are $n$ people connected in a circular fashion as demonstrated by the diagram. Individuals need to send packages to each ...
2
votes
1answer
103 views

Advantage of MTZ problem formulation of TSP

In class, we saw the Miller-Tucker-Zemlin formulation of the Travelling Salesmen Problem (TSP). MTZ is a way of formulating the TSP as an integer linear programming instance. I understand how MTZ ...
0
votes
1answer
47 views

How to reformulate my problem as a mixed-integer quadratic problem

I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the ...
0
votes
0answers
66 views

Is this problem a knapsack problem?

I have the following problem. Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$ subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ ...
1
vote
0answers
86 views

Is this NP-Hard problem? [closed]

I have the following problem. maximize $\sum\limits_{k=1}^Lx_k$ subject to: $\mathbf{x}^T\mathbf{A}~ \tilde{\mathbf{x}_i} \geq 0,~~ \forall~ i\in\{1, 2, \cdots, L\}.$ where, $~\mathbf{x}^T = (x_1, ...
5
votes
2answers
238 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}$). ...
8
votes
1answer
368 views

Poly-time reduction from ILP to SAT?

So, as is known, ILP's 0-1 decision problem is NP-complete. Showing it's in NP is easy, and the original reduction was from SAT; since then, many other NP-Complete problems have been shown to have ILP ...
14
votes
0answers
654 views

Is it NP-hard to fill up bins with minimum moves?

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$. You start with $b_j$ balls of type $j$. Each ball of ...
3
votes
3answers
2k views

Are all Integer Linear Programming problems NP-Hard?

As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
2
votes
0answers
32 views

Why are optimization problems always NP-hard and not NP-complete and what does this mean for other levels of the polynomial time hierarchy? [duplicate]

I have read that optimization problems cannot be $\mathcal{NP}$-complete, but are always classified as $\mathcal{NP}$-hard. When a problem is NP-complete, I know it is contained in $\mathcal{NP}$P. ...
8
votes
1answer
112 views

Hardness of Approximating 0-1 Integer Programs

Given a $0,1$ (binary) integer program of the form: $$ \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} &A\vec{x} = \vec{b} & \quad \forall i\\ &x_i\ge 0 & \quad \forall ...