This might be a silly question but by 'solving' an optimization problem do we mean if an optimal solution exists we find such a solution and its optimal value and if it 'doesn't exist' (for example the optimal solution is $\pm\infty$ or there is no feasible solution, etc) we say there is no optimal solution? (i.e it's like a decision problem but if the answer is yes we should also specify the optimal solution and its value) Or does it mean we try to find an optimal solution but if we fail, it doesn't mean there's no optimal solution? I think the answer is the first one. I was reading about https://en.wikipedia.org/wiki/Exact_cover (it's actually a decision problem that is NP-complete) and I thought the CSP (a.k.a feasibility problem) associated with exact cover problem must be NP-complete as well. But after that I wondered whether solving the CSP is like a decision problem or not, so I asked this question. Another way to express my question is this: By solving an optimization problem do we mean a method (probably an algorithm) that is sound (i.e if it returns a solution it is indeed an optimal solution) and it terminates, or a method which is both sound and complete and terminates? (as a result, if it doesn't return a solution (i.e returns failure) it really means there is no optimal solution.) (complete means if at least one optimal solution exists the method will return such a solution.) I think the answer is the second one.
1 Answer
I think that the correct definition of "solving" is finding an optimal solution or proving that none exists. Trying and failing to find an optimum (because, say, the solver times out either before it finds a feasible solution or before it proves optimality) would properly be referred to as "attempting to solve" the problem.
That said, not everyone picks nits as close to the ground as I do. So you will likely encounter at least occasional uses of "solving" that include trying and failing, or partially succeeding (finding a feasible solution but not proving optimality).
There may also a bit of a distinction between "solving" in an academic context and a real-world context. In the real world, it is often more important to find a "good" solution in a "reasonably short" period of time than to find a proven optimum, especially in cases where the bulk of the solution time is spent proving optimality of a solution that has already been found.
