1
$\begingroup$

If some or all of the unknown variables are required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem.

If understand correctly, the feasible region of a ILP problem is not a convex set. Being not a convex set, ILP problems are in many practical situations NP-hard.

What's the relation between the non-convex sets and the hardness of the problem?

2 Answers 2

1

In a linear problem, the maximum along a line segment in the domain of your problem is at one end of the line segment. In particular, then, if your region is convex, then the maximum for your problem is definitely on the "boundary" of your domain. If the boundary is polygonal and convex, then the maximum will be at one of the vertices of the polygon.

  • 0
    Consider the simple napsack problem: Maximize $\sum_{i=1}^n v_ix_i$ where $\sum w_ix_i\leq W$ and $0\leq x_i \leq 1$. The number of points you need to check in the integer case can be up to $\binom{n}{n/2}$ points, while the real linear programming problem is requires only that you sort the $v_i$.2012-10-03
0

In general convex optimization problems are "easy". If a problem class is NP-hard and admitted a reasonably-sized convex formulation then one would be able to solve problems in this class quickly; many people don't believe this is true (i.e., P $\not=$ NP).