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?