Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 4 down vote favorite

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.

Thanks!

share|improve this question

1 Answer

up vote 2 down vote

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.

share|improve this answer
Thanks! What are "combinatorial origin"?? – Tim Sep 26 '12 at 13:09
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. – Arnold Neumaier Sep 26 '12 at 13:57
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? – Tim Sep 27 '12 at 12:13
@Tim: No. It is just a matter of the point of view. Different people have different opinions of what subsumes what and/or how much the fields intersect. You don't go wrong by treating them essentially as synonyms. – Arnold Neumaier Sep 27 '12 at 14:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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