11
$\begingroup$

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:

enter image description here

  • 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):

enter image description here

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

enter image description here

  • 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?
$\endgroup$
3
  • 5
    $\begingroup$ What do you know about intractability and NP-Completeness? Many combinatorial optimization problems are NP-Complete (actually NP-Hard.) Some combinatorial optimization problems have known polynomial-time algorithms and aren't hard to solve at all. $\endgroup$ Feb 5, 2022 at 22:36
  • 7
    $\begingroup$ There is no equivalent. The first intuition to develop is that these are entirely separate disciplines of mathematics that solve entirely different types of problems. There should be little expectation that they share any features in common. Trying to learn one by looking for analogies in the other is a doomed strategy. Like a fisherman asking what the equivalent of the fishing line is when you're trying to hunt a bear. When all you have is a hammer, everything looks like a continuous optimization problem. The only way to develop your intuition is to study discrete optimization. $\endgroup$
    – J...
    Feb 6, 2022 at 12:51
  • 1
    $\begingroup$ For intuition, note that even determining whether a given system of linear constraints has any integer-valued feasible point is NP-hard. You can think of the hard cases for integer linear programming problems as having very sparse and unrelated integer feasible points. So, nothing approaching a "neighborhood" structure that you could exploit, nor any "pseudo-continuous" properties that would enable, say, hill climbing or any discrete sort of gradient. The hard cases of discrete optimization behave much more like circuits, and can even simulate circuits, with all their complex behavior. $\endgroup$
    – Neal Young
    Feb 8, 2022 at 1:27

9 Answers 9

11
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Analogs for gradients exist in purely discrete domain, gradient descent is quiet similar to en.wikipedia.org/wiki/Hill_climbing on discrete domain. You can very much follow a path. $\endgroup$ Feb 6, 2022 at 14:31
  • 2
    $\begingroup$ @worldsmithhelper As I said: “sometimes you may of course be able to exploit heuristics”. Discrete hill climbing makes the assumption that the objective function varies slowly enough that you can solve the problem essentially as if it were continuous. To stay with my analogy, the fridge is broken but we still have lots of crushed ice. Not comparable with the true “stone age” situation – in general discrete optimisation, you can't make any such assumption, though in many real-world applications they are available but IMO that's just a consequence of the real world being continuous. $\endgroup$ Feb 6, 2022 at 15:33
  • $\begingroup$ Why is it that you don't recognize the result of hill-climbing as a solution to a discrete problem? That is what one does in continuous optimization (KKT conditions). Thus the reason why discrete optimization is hard is not that finding an optima is hard but that finding an optima means something different between discrete(global unless specified to be local) and continuous(local, or maybe only KKT or first order unless specified to be global). Thus a gradient existing is a red herring. $\endgroup$ Feb 6, 2022 at 15:41
  • 1
    $\begingroup$ @worldsmithhelper You seem to be making multiple arguments here simultaneously that may or may not make sense individually, but at any rate they don't really fit together. $\endgroup$ Feb 6, 2022 at 17:55
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

enter image description here

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).
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ That example is a piece of cake for Gurobi, CPLEX, MOSEK, not as easy for GLPK, and really puts a hurting on CBC and intlinprog. $\endgroup$ Feb 5, 2022 at 18:25
  • $\begingroup$ It is definitely true. The strange thing is that some of the commercial solvers after struggling to solve the problem cannot turn out the right optimal solution!!! $\endgroup$
    – A.Omidi
    Feb 5, 2022 at 18:56
  • $\begingroup$ For the Pseuso-Boolean based ILP solver Exact gitlab.com/JoD/exact/-/issues/3 this problem is trivial. $\endgroup$ Jun 23, 2022 at 12:40
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ I disagree the discrete $\Rightarrow$ non-convex. Consider $min_{x \in \mathbb{N} }x$ or $min_{x \in \mathbb{Z}} x^2$. Those problems are very much convex (although not convex over $\mathbb{R}$). It is just that you can't choose any $\lambda \in (0,1)$ and instead need to choose $\lambda$ such that $\lambda x + (1-\lambda) y $ is in $\mathbb{Z}$. Extending the concept of convexity in this way is well behaved and leads to the same properties with regard to set operation, minkowsky sums, convex hulls ... . $\endgroup$ Feb 6, 2022 at 14:58
  • $\begingroup$ @worldsmithhelper technically a binary variable can be posed as a quadratic non-convex constraint, i.e. $x(1-x) = 0$, and integers can be posed as binary sums, so you can always transform an integer program to an equivalent non-convex continuous program, although that's much harder to solve in practice. $\endgroup$ Feb 7, 2022 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.