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

Question

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?

Answer 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.

Answer 2

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).