I wonder what relation and difference are between combinatorial optimization and discrete optimization? Thanks!

Originally by reading Wikipedia, I thought discrete optimization consists of combinatorial optimization and integer optimization, where the combinatorial one is to search over a finite set of solutions, and the integer one is to search over a countably infinite set of solutions.

But after reading the table of content of Bernhard Korte and Jens Vygen Combinatorial Optimization: Theory and Algorithms, I saw they include integer programming in their combinatorial optimization book. Now I am confused.



The three topics are roughly the same (as one can reformulate the same problem in many ways), just looked at from different perspective, and hence typically treating different parts of theory and practice in different depth.

  • Combinatorial optimization emphasizes the combinatorial origin, formulation or solution algorithm of a problem.
  • Discrete optimization emphasizes the difference to continuous optimization.
  • Integer programming emphases the usage of integer (or binary integer)-valued variables in formulation or solution.

  • $\begingroup$ Thanks! What are "combinatorial origin"?? $\endgroup$
    – Tim
    Sep 26 '12 at 13:09
  • $\begingroup$ combinatorial origin: if the problem is one of graph theory, or arranging objects in a particular way. Many important discrete problems that at first sight don't look combinatorial can be naturally phrased in terms of graphs. $\endgroup$ Sep 26 '12 at 13:57
  • $\begingroup$ Thanks! Do you think that (1) discrete optimization consists of combinatorial optimization and integer programming, and (2) the latter two don't overlap with each other although sometimes they can convert to each other? $\endgroup$
    – Tim
    Sep 27 '12 at 12:13
  • 1
    $\begingroup$ Do you know any reference explaining this? $\endgroup$
    – mosh442
    Dec 13 '17 at 9:21
  • 1
    $\begingroup$ @mosh442: This is well-known folklore. $\endgroup$ Dec 13 '17 at 15:54

Good question! Here is my view of it. There is a hierarchy as follows: integer programming $\subset$ discrete optimization $\subset$ combinatorial optimization.

So combinatorial is the broadest field. Any problem that involves making decisions out of a discrete set of alternatives I would classify as a combinatorial problem. The problem definition here could be very complex.

Now, let say we can formulate the problem using discrete variables, i.e., precisely state the decision variables of the problem and formulate it using an objective function along with a finite number of constraints in those variables. In that case, I would classify the problem as a discrete optimization problem.

Finally, I would say that integer programming deals more with the algorithmic aspect of integer programming. For instance, comparing different formulations, developing algorithms, analyzing problems and algorithms complexity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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