3

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

YcK
  • 79
  • 4
  • 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 – fontanf Oct 25 '21 at 07:57
  • 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. – YcK Oct 25 '21 at 08:07
  • 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 – fontanf Oct 25 '21 at 11:35
  • Thank you for your answer. So do you know any problem in the literature that refers to "unbounded" types? – YcK Oct 25 '21 at 11:38
  • In the classical Operations Research literature, I can't think of any. But maybe problems like finding large prime numbers could be considered as discrete problems which are not combinatorial – fontanf Oct 25 '21 at 14:19
  • @fontanf, many of the practical scheduling problems have fallen into the combinatorial optimization problem. Besides what was mentioned in the references, they might have multiple solutions with the same objective function value. But some of the production planning models, in the real situation, have a unique optimal solution. I think they are not essentially a COP. Would you say your idea about that, please? – A.Omidi Oct 25 '21 at 20:20
  • 1
    @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 – fontanf Oct 26 '21 at 07:53
  • @fontanf, Thanks so much for your reply. For the first part, I mean, many of the COPs have multiple solutions and it is in their essence and w.r.t this, they might be figured out based on. For a second part, I totally agree with you. – A.Omidi Oct 26 '21 at 14:09

1 Answers1

3

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:

A.Omidi
  • 8,832
  • 2
  • 13
  • 49