Why is Discrete Optimization "Difficult'?

Question

I have the following question about why Combinatorial and Discrete Optimization Problems are Considered to be "Difficult":

• For continuous optimization problems (e.g. Loss Functions in Machine Learning Models) - we are often told that these problems are difficult because when the objective functions are non-convex, the function can have "saddle points" which can "trap" the optimization algorithm before it reaches its intended destination:

• Recently, I have learned that the objective functions in discrete combinatorial optimization problems (e.g. Traveling Salesman) can also be non-convex. This is because even though the objective function corresponding to Traveling Salesman is linear and therefore convex, when integer constraints are applied to the objective function, the feasible region and the optimization problem ends up becoming non-convex (this is because the set of integers and therefore integer constraints automatically turn a problem into a non-convex problem):

My Question:

• Intuitively, in the case of continuous optimization problems with non-convex functions, we can understand why these functions might be difficult to optimize. We can imagine the optimization algorithm getting stuck in the saddle points.

• Mathematically, we can also understand why continuous non-convex functions and saddle points can pose an obstacle - In a saddle point, the first derivatives of the function are 0. Since optimization algorithms that are commonly used for optimizing continuous functions (e.g. gradient descent) iteratively move towards their future destination (k+1) based on the current value (k) of the gradient (i.e. derivative), if they are in a saddle point and the derivative at a saddle point is zero - the optimization algorithm will become perpetually stuck in the saddle point and can't move forward (without some "intervention", e.g. stochastic momentum):

• The same way, is there any visual or mathematical or visual intuition that we can use to understand why Combinatorial and Discrete Optimization Problems are difficult? For instance, what would be the equivalent of "saddle point" obstacles in discrete and combinatorial optimization problems?

Answer 1

Comparing with local minima / saddle points of continuous problems is a bit of a red herring. It's like wondering why people in the stone age had it tough to find food, and comparing with “on Sunday we had such a terrible dinner, because the fridge had broken over night and the shops were all closed”. These are issues that aren't even meaningful from the stone age perspective. Fridge? Luxury! We used to dream of having a broken fridge...

In the discrete setting, you just don't have gradients available. You can't follow paths leading downwards (even to a local minimum), because there are no paths, because the domain is disconnected. All you can do is jumping between separate points. Sometimes you may of course be able to exploit heuristics, but in general you won't get around a lot of trial and error.

Another way to look at it is that a discrete problem can be seen as a continuous problem with a very strong penalty term that only vanishes at the integers. That penalty is nonconvex, so even if the rest of the objective is simple linear, the overall problem has lots of bad narrow local minima.

Answer 2

I doubt that there is any visual aid to understanding the difficulty of discrete optimization problems that is as intuitive as the saddle point is for continuous non-convex optimization. The branch-and-bound/branch-and-cut algorithms most commonly used problems partition the integer-feasible solution space into smaller and smaller chunks. This is usually represented by an inverted binary tree where nodes are subproblems (original problem restricted to a smaller chunk of the solution space). You could make a comparable sequence of images in the solution space (for a 2D problem) by adding cuts that would slice and dice the feasible region, but that evades the key point.

What makes an integer program difficult or not is a combination of problem size (number of variables/constraints), how quickly the algorithm finds better (not necessarily optimal) solutions, and how tight the bounds of the subproblems (restricted feasible regions) are. Other than problem size, your main concern is being able to prune nodes high up in the search tree, so that you need to solve fewer subproblems. "Easy" problems have tight subproblem bounds and fast improvement of the incumbent, resulting in a lot of pruning high in the tree. "Difficult" problems have more pruning deep in the tree, making the portion of the tree actually explored bigger. You could put images of a tree pruned high up and a tree pruned lower side by side to show the difference in number of nodes visited, but I'm not sure how informative that would be.

Answer 3

Here is 2D geometrical interpretation of why discrete optimization is hard (in the linear case).

As one knows, when solving a continuous (linear) optimization problem, the set of constraints represents a polyhedron, and the optimal solution is typically on one of the vertices of this polyhedron. Continuous optimization is "easy" partially because these vertices can be identified easily. In the image below, the green polyhedron represents the feasible set of solutions for a given problem in two dimensions. The equations of the green lines are known, and therefore identifying the vertices is relatively easy.

On the other hand, if variables are integer (so optimization is now discrete), the set of feasible solutions is represented by the filled circles, and in terms of optimization, this is equivalent to working with the convex envelope of these filled circles, the blue polyhedron. Part of the difficulty comes from the fact that the equations of the blue lines are not known. The green part between the green lines and the blue lines is the gap between continuous and discrete optimization.

Discrete optimization techniques try to approach these blue lines and include the following ideas (roughly speaking) :

• iteratively divide the polyhedron into pieces (branch-and-bound). The number of times the polyhedron must be divided can grow exponentially.
• add equations on the fly (cutting planes), hoping that the gap between the new polyhedron and the blue polyhedron shrinks. The number of such equations can also grow exponentially.
• both ideas are used jointly (branch-and-cut).

Answer 4

I am not sure about saddle points but, many of the integer programs are hard to solve in their essence. It comes back to how a modeler might be modeling a specific problem. For example, in the following trivial problem, there are only three integer variables, but many of the open-source solvers like CBC and some of the commercial solvers cannot solve this in a reasonable amount of time or without some specific tricks.

\begin{array}{l} \text{minimize} \quad x_{3}\\ \text{subject to:} \\ \ 12x_{1} + 9x_{2} - x_{3} = 0\\ \ x_{1,2} \in (-inf,+inf) \\ \ x_{3} \geq1, \quad x_{1,2,3} \in Z\\ \end{array}

Also, there are lots of such an example that can be found by googling. If you are willing to know how long does it take to solve an optimization problem the complexity theory would be a very good starting point.

Answer 5

Let's state the obvious both non-convex continuous problems and non-convex discrete problems can in general be used to encode NP-hard problems when one searches for a global optima. I suspect that discrete optimization is generally considered hard because solving a discrete problem means something different than solving a continuous problem. In continuous optimization one is usually happy if one reaches Karush–Kuhn–Tucker (KKT) conditions or even a local minima. Many solvers (like KNITRO, Ipopt, WORHP) stop when such a condition is reached. In discrete problems finding a local optima while satisfying constraints is a bit more trivial, so solving took the meaning of "solving to global optimality". "Solving to global optimality" for continous problems can be just as hard but that is not what most NLP solvers do on continuous problems.

Saddle points also exist in discrete optimization. However translating them such that finite difference along one dimension is 0 is not very helpful as that makes assumption that the function is defined over a grid of points. The a better analog for saddle points is that you are at some value $x$ which has two neighbors $y,z$ which are better than $x$ but $y$ and $z$ are not neighbors with each other. In this case the difficulty is not getting stuck in a saddle point, it is usually not difficult for continuous optimization either as that that can be detected by NLP solvers, but the challenge is to choose which way to go down.

For some problem classes you can embed $x,y,z$ in to a grid and get a visual metaphor however sometimes you can't do that well as discrete points with connections (also called graphs) might not embed well in euclidean geometry. For an example of such a space try to think about the space of all words of any length that can be formed from English letters connected when their edit distance (replacement, insertion and deletion) differs by one. There is no way to fit this well into an finite euclidean space.

Answer 6

Many kinds of discrete optimization problems are about as easy as continuous optimization problems in common scenarios where regions are large relative to the spacing between candidate points. What makes things hard are scenarios involving really long skinny regions whose boundaries might extend far beyond any candidate points that are actually inside them.

Suppose one has two pairs of lines and regards each as having a "region of interest" which is entirely below both of its lines; one wants to find which line's region of interest extends further up in the Y direction.

To solve the continuous problem, one could simply compute where the two lines in each pair intersect; whichever pair has the higher intersection point has the region that extends further up. To solve the discrete problem, however, it's not necessary to compute where the lines intersect, but for every candidate Y value below that one must compute whether there exists an integer value between the two X coordinates. For the case with only two pairs of lines, this may be doable, but in higher-dimensional problems with more constraints, things can get intractibly complicated.

Note that if regions are large relative to the space between candidate points, the optimal candidate point will generally be pretty close to what would be the optimal vertex for the continuous problem, and one would thus be able to ignore most of the vertices and candidate points near them. In the "interesting" problems, however, many regions will be sufficiently skinny that it's not possible to prune many vertices or candidates while still guaranteeing that one won't prune what should have been the optimal solution.

Answer 7

Unknown variables are drawn from a limited information in discrete optimization. By contrast , the feasible set in continuous optimization is usually uncountably infinite. Also, the smoothness of a continuous objective function makes it possible to use objective and constraint information at a particular point to deduce information about the function's behavior in a neighborhood. By contrast, in discrete case, the behavior of objective and constraints may change significantly as we move from one feasible point to another.

Answer 8

This may or may not help but I found that the knapsack problem does a good job showing how discrete problems can be harder than their direct continuous counterparts.

Another domain that helped me understand a bit more intuitively is integer programming versus linear programming.

Answer 9

Problems with non-convex feasible regions tend to be hard to solve to a global optimum because hill-climbing algorithms are not guaranteed to work. A hill climbing algorithm, though typically fast, will stop at a local optimum. (There are lots of hilltops. A hill-climbing algorithm will find one of them and stop). In a problem with a convex feasible region and a convex objective, a local optimum is also a global optimum. (There is only one hilltop.) So for noncovex problems you are forced to use intelligent enumeration algorithms such as branch-and-bound to find a guaranteed global optimum. Their compute time may grow exponentially with problem size. A feasible region is convex if for any two feasible points, any point on the continuous straight line connecting them is also feasible. A problem with discreteness constraints on the variables is clearly not convex.