Integer optimization problem

Question

Suppose we are given $Av - x \ge 0$, for a given $n \times n$ matrix A and an $n\times 1$ vector $x$. Find an integer valued vector $v$ of size $n \times 1$ such that $\mathbf{1} \cdot v$ is minimized (in other words the sum of its elements is minimized)

Also, A is symmetric and invertible, if that helps.

Any idea how to attack this problem?

score 1 · Accepted Answer · answered Mar 16 '13 at 03:25

1

Its an Linear programming problem, $$ \min 1^T v$$ $$\text{s.t } Av > x$$ There exist many method for solving Integer LP. Write the above Optimization function in standard form and you can use Simplex method.

Standard Form: $$ -\max (-1^Tv)$$ $$\text {s.t }-Av < x $$

answered Mar 16 '13 at 03:25

Learner

2,696

1

Thanks, it should be called "integer linear programming" to be more exact. – darksky Mar 16 '13 at 03:37

Integer optimization problem

1 Answers1