Optimization Problems vs Optimization Sub Problems

Question

Especially in the case of Discrete and Combinatorial Optimization Problems - I am trying to better understand the the idea of "subproblems" within the "main problem":

At a very superficial level, I can understand the idea of a "subproblem" : A complicated optimization problem might be too difficult to solve directly. Therefore, if we can "break" this complicated problem into smaller problems (provided these smaller problems are easier to solve than the original complicated problem), we can instead solve these smaller subproblems and as a result, indirectly solve the original complicated problem.

Example 1: As an example, I might not be able to add two large numbers together. However, I know how to add smaller numbers together. So I might be able to "break" this addition problem into smaller subproblems. For example:

• Original Problem 541 + 329 = 870
• Subproblem 1: 500 + 300 = 800
• Subproblem 2: 40 + 20 = 60
• Subproblem 3: 1 + 9 = 10
• Subproblem 1 + Subproblem 2 + Subproblem 3 = 800 + 60 + 10 = 870 = Original Problem

Example 2: As another example, I might not be able to carry all my groceries from my car to my house in one trip (original problem). So instead of struggling and inevitably being unable to carry all my groceries in one trip, I might be identify subproblems as a function of the maximum weight of groceries I can carry, and solve the original problem by solving a series of subproblems (i.e. making multiple trips instead of a single trip).

Now, I am trying to extend these ideas to understand the relevance of subproblems in combinatorial and discrete optimization problems (e.g. mixed integer programming). For instance, I have heard that almost all algorithms for discrete optimization problems always try to solve these problems by identifying subproblems but I am not sure why this is.

Logically, I can understand why this is the case as discrete/combinatorial optimization are too difficult to solve at once, thus we try to break them into mini subproblems and solve these subproblems individually. I have also heard that in a "constraint mixed integer programming problem," the existence of subproblems are inevitable : an optimization algorithm will treat the problem as a continuous problem when identifying a candidate solution (subproblem 1), and then check to see if this candidate solution satisfies the constraints (subproblem 2). But I am not sure if this analogy is correct.

My Question: Can someone please explain why Subproblems are so "relevant" in Discrete and Combinatorial Optimization Problems?

References:

• https://en.wikipedia.org/wiki/Optimal_substructure
• https://ibs.bfsu.edu.cn/chenxi/IntegerProgramming.pdf

Note: In Machine Learning applications where the task is to optimize a (complicated) Loss Function corresponding to a Neural Network, Optimization Algorithms such as Gradient Descent often (locally and linearly) approximate this Loss Function based on a Taylor Expansion, seeing as this local-linear approximation of the Loss Function is easier to optimize compared to the original Loss Function (e.g. less computationally expensive). Thus, could we say that the Gradient Descent algorithm in Machine Learning applications is identifying a "first subproblem" through the local-linear approximation of the Loss Function, and then solves a "second subproblem" by evaluating the derivative of this local-linear approximation?

Answer 1

I would disagree with the contentions that subproblems are "inevitable" and that algorithms almost always try to identify and exploit them. What is illustrated in your diagram (a branch-and-bound solution tree) does not really involve "subproblems". A more accurate term for the problems at the nodes would be "restricted problems" or just "restrictions".

Subproblems frequently occur when a problem can be decomposed into smaller, more tractable portions. For instance, a multiperiod production problem might decompose into a set of single period subproblems and a master problem that integrates the single period solutions and handles constraints that link them. Besides decomposing over time, in some cases we decompose problems geographically or geometrically. In one project with which I was involved, we were placing a network of sensors in a body of water. The full model was too large to solve, so we approximated the body of water with a bunch of 3D cubes, made the placement of sensors in each cube a subproblem, and then had a master problem that resolved the connection of the separate networks into a single network.

In addition to decomposition, another source of subproblems is models where a portion of the problem does not fit a mixed integer linear (quadratic, whatever) structure. There are techniques that combine a MILP model containing the elements that are easily modeled with an "oracle" that takes candidate solutions, does mysterious things, and either blesses the solution or conjures up a previously unknown constraint that the candidate solution violates. In the latter case, the new constraint is added to the MILP model and solution of the MILP continues or starts over. The oracle is considered a subproblem.