Confusion Between Different Types of Optimization Problems

Question

I do not have a background in optimization and I am trying to teach myself more about this topic. I find myself having a lot of trouble understanding the different "types" of optimization problems that exist.

For example, I understand the idea of optimizing continuous functions (e.g. $y = x^2$). For example, we could be interested in finding out the value of $x$ that results in the smallest value of $y$. I also understand that continuous functions can be optimized subject to some constraints.

However, I find myself very confused when trying to sort through the following types of optimization problems:

• Discrete Optimization
• Integer Optimization
• Mixed Integer Optimization
• Combinatorial Optimization

When I think of these problems, the first thing that comes to mind is that they are fundamentally different from optimizing continuous functions. For instance, the inputs of the above list of problems are usually "categorical" in nature. This is why I have heard that problems belong to the above list usually require "gradient free optimization methods" (e.g. evolutionary algorithms, branch and bound, etc.) , since it is impossible to take the derivatives of the objective functions corresponding to these problems.

For example, if you take problems such as the "Traveling Salesman" or "Knapsack Problem" (note: I have heard that these problems belong on the above list, but I am not sure), I would visualize the objective function as something like this:

This leads me to the following question:

• Are 4 types of optimizations on the above list effectively the "same thing"? The way I see it, all 4 types of these problems have "discrete inputs" and in a mathematical sense, "integers" are always considered as "discrete". In all 4 types of problems, we are interested in finding out a "discrete combination" of inputs - i.e. "combinatorical". Thus, are 4 types of optimizations on the above list effectively the "same thing"?

• I have heard the argument that "any optimization problem that can be formulated into a linear problem is always convex (because linear objective functions are always convex)". If we consider continuous optimization problems, we usually say that "convex optimization problems are easier than non-convex optimization problems" because non-convex functions can have "saddle points" that can result in the optimization algorithm getting stuck in these "saddle points". Using this logic, I have seen the objective function of the "Traveling Salesman Problem" being written as a linear function and thus the "Traveling Salesman Problem" being considered as a convex optimization problem. I have also heard the "Traveling Salesman Problem" is a very difficult problem to solve. If the "Traveling Salesman Problem" is convex and difficult to solve, does this imply that there are non-convex discrete/combinatorial problems that are even more difficult to solve?

• I have heard the following argument: Discrete/Combinatorial Optimization Problems are more difficult to solve compared to Continuous Optimization Problems. This is apparently because discrete/combinatorial optimization problems involve "treating the problem as a continuous problem" to first come up with a solution, and then determine if the solution lies within the feasible region, thus effectively solving two optimization problems in one. Is this correct?

• Finally, I have seen both the "Traveling Salesman" and the "Knapsack Problem" being formulated as a linear problem and therefore as convex. Are there any well known examples of non-convex discrete/combinatorial optimization problems?

Answer 1

• I'm inclined to treat "discrete optimization" and "combinatorial" optimization as synonyms, but I'm not sure everyone does.
• "Integer programing/optimization" is a specific approach to modeling and solving a discrete/combinatorial problem. It is not the only approach. For instance, constraint programming can be used productively to solve some combinatorial problems, and it is very different from integer programming both in terms of problem representation (modeling) and in terms of the algorithms used to solve the models.
• "Mixed integer programming/optimization)" generalizes integer programming (slightly) by allowing non-integral real variables in the model. The most common algorithms for IPs make no distinction between IPs and MIPs.
• When dealing with discrete optimization, the roles of linearity and convexity largely have to do with how easy (and perhaps how useful) it is to solve relaxations of the problem where the integrality restrictions are dropped.
• Yes, nonconvex discrete problems can be bigger pains in the posterior to solve than discrete problems with convex relaxations are. Note that this is not guaranteed to be the case with every instance. I could probably conjure up a nonconvex discrete problem A and a convex discrete problem B where A was easier than B. Let's just say that when confronting a new problem I am always rooting (hard) for convexity and (fairly hard) for linearity.
• Discrete problems tend to be harder than their continuous equivalents, in large part because the "move a small amount in this direction" logic of many continuous optimization algorithms is not applicable when the variables are discrete. A small step from an integer is not integer, hence not feasible. I would not, however, agree with characterization of solving the continuous relaxation to see if the solution is in the feasible region and calling that two problems. In branch and bound/branch and cut, for instance, you do solve the continuous relaxation, and assuming it is feasible with an objective value no worse than the current incumbent you do check whether the solution is integer-feasible ... but that check is trivial. (You just look at the values of the discrete variables and see if they are within rounding distance of integer.) The main reason for solving the relaxation, though, is not the hope of finding an integer solution but rather to get what you hope is a fairly tight bound for the objective value in that part of the solution space.

Answer 2

----If the "Traveling Salesman Problem" is convex and difficult to solve: TSP is not convex, it belongs to a class of hard problems, "NP-hard" to be more specific (for more details, see here: https://stackoverflow.com/a/49845003/9125267).

---- Discrete/Combinatorial Optimization Problems are more difficult to solve compared to Continuous Optimization Problems: I have to disagree with this statement since you can enforce the constraint x is binary just by adding the constraint x^2=x and leaving your formulation continuous. The real distinction should be convex vs non-convex.

----Are there any well known examples of non-convex discrete/combinatorial optimization problems?: Mixed-Integer Nonlinear Programs (MINLPs) are used to model non-convex discrete/continuous problems (they include mixed-integer linear and pure integer programs, see classification chart below). There are plenty of examples in the MINLP library: https://www.minlplib.org/applications.html.

For a real-world example, have a look at the Grid Optimization competition: https://gocompetition.energy.gov/about-competition