4
$\begingroup$

I have seen one explanation about the difference between discrete and combinatorial optimization problems in such a way that "all combinatorial optimization problems are also discrete optimization problems but the converse is not true" [1].

I am not aware of the existence of such a problem. Also, looking at the literature, from vehicle routing to the scheduling problems, all of them are discrete (of course, some of them are mixed-integer). Could you enlighten me about how it is possible for a problem that is discrete, but not combinatorial?

[1] https://link.springer.com/chapter/10.1007/978-1-4613-0303-9_3

Improve this question
$\endgroup$
8
  • $\begingroup$ From the paper you mention, the difference is that a combinatorial problem has a finite set of solutions, while a discrete problem might have a infinite number of solutions $\endgroup$
    – fontanf
    Oct 25 at 7:57
  • $\begingroup$ Could you extend your explanation "infinite number of solutions"? If a problem has constraints and boundaries, the problem will have a finite set of solutions. Otherwise, I don't know whether there is a method in the literature to solve this type of problem. $\endgroup$
    – YcK
    Oct 25 at 8:07
  • $\begingroup$ Yes, if all variables are integer and bounded, then the number of solutions is finite. In practice, it is often the case. It is still possible to apply a branch-and-bound algorithm with unbounded variables, but there's no guarantee it will terminate $\endgroup$
    – fontanf
    Oct 25 at 11:35
  • $\begingroup$ Thank you for your answer. So do you know any problem in the literature that refers to "unbounded" types? $\endgroup$
    – YcK
    Oct 25 at 11:38
  • 1
    $\begingroup$ @A.Omidi I'm not sure that I understand what you mean. Why wouldn't they be COP if it is possible to enumerate all their solutions? Then, I'm not sure it's so important to determine if a problem has the tag COP or not. And I think that it is easy to find border cases where the problem has continuous decisions, but easily deduced from the discrete decisions, so which could or couldn't be considered as part of the decisions $\endgroup$
    – fontanf
    Oct 26 at 7:53
3
$\begingroup$

Based on some googling:

The versatility of the combinatorial optimization model stems from the fact that in many practical problems, activities and resources, such as machines, airplanes, and people, are indivisible. Also, many problems have only a finite number of alternative choices and consequently can appropriately be formulated as combinatorial optimization problems — the word combinatorial refers to the fact that only a finite number of alternative feasible solutions exists. Combinatorial optimization models are often referred to as integer programming models where programming refers to “planning” so that these are models used in planning where some or all of the decisions can take on only a finite number of alternative possibilities.

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

References:

Improve this answer
$\endgroup$

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.