What is a solution?

Question

Consider a standard optimization problem: Minimize an objective function with respect to constraints. My question is:

What does the term "solution of the optimization problem" mean?

At first I would think that the answer is obviously:

A solution is a point that produces the smallest objective function value among all feasible possibilites.

But then I notice that people also use the following terms:

• feasible solution (this implies that even infeasible points may be considered some kind of solutions),
• optimal solution (this implies that points that are not optimal may be considered solutions),
• approximate solutions.

In light of the above one may even speak of "infeasible, non-optimal solutions" which may well just be any point at all, and this is a rather unusual meaning of "solution" - and I suspect that I haven't read this in any paper yet.

So my question is, maybe, a bit different from what I wrote above. It's more: What is the usual understanding of "solution" without any other qualifier?

^{P.S.: I am not sure about how to tag the question. Maybe there are better ones?}

Answer 1

Great question, @Dirk. People regularly stumble across this, and I believe the notion is not generally agreed upon. Here is how I use it.

Main qualifiers for a solution are feasible and optimal. When nothing is said, I associate with "solution" (without qualifiers) that it is feasible, that is, it satisfies all the constraints. This goes also for "a solution to an optimization problem" where I would not assume that this implies optimality. For optimal solutions I always use the qualifier optimal, always. A solution can be infeasible. This is strange, but often necessary. For example, I can have a vector of variables which has the right dimension, but this vector does not satisfy all the constraints. Some people would not speak of a solution then, but I'd call it an "infeasible solution". I need this often, e.g., when I try whether a given vector of variables is feasible for an integer program (in solvers there is usually even a method to check this). Solutions can even be optimal and infeasible, for linear programs exactly the situation when we would apply the dual simplex method.

Answer 2

I often encounter a clear difference in the point of view of an operator (business) and a programmer (engineering):

• From the business POV: if it's not feasible, it's not a solution. Given that an unfeasible solution is useless to them, it's pretty easy to argue this is also the dictionary definition (an answer to, explanation for, or means of effectively dealing with a problem).

• From the software engineering POV however, for very practical reasons, the state of the collection of optimization variables needs to have a name - and solution is the lesser evil, so it's the best name. And that state can be infeasible, so solutions can be infeasible.

  • For example in TSP, such a state could be [Brussels -> Paris -> Amsterdam -> London -> Berlin]. As your algorithms or a general purpose constraint solver discovers better states (such as [Brussels -> London -> Paris -> Berlin -> Amsterdam]), it finds better solutions. Now, in the beginning, these solutions might not be feasible. Furthermore, there's often one or more working solution(s) that can temporarily become infeasible to escape a local optima. But internally in your algorithms or in the constraint solver, that state will still be referred to as the solution, even in those unfeasible cases, for practical reasons.

In our implementation these even goes a step further, as the user define their own custom solution class:

@PlanningSolution
public class ConferenceSolution {

    private List<Timeslot> timeslotList;
    private List<Room> roomList;
    private List<Talk> talkList; // Assign these to timeslots and talks

    private HardMediumSoftScore score;
}

Obviously, if we create a ConferenceSolution instance for which we assign all those talks in the same timeslot in the same room, that ConferenceSolution instance is definitely not feasible, so the business users won't agree that it's a solution...

Answer 3

I mostly agree with Marco Lübbecke.

I would like to add that "vectors of the right dimension" are sometimes called solution candidates.

Also when we refer to an "infeasible solution" we often mean that a piece of software determined that the problem is infeasible, not an actual vector of values.

Answer 4

Here are two more "dimensions" to the question which have not yet been addressed in any of the other answers, but can be of great significance in practice.

Global optimum vs. local optimum: I will first assume that only globally optimal solutions are of interest.

Let us just consider feasible and globally optimal solutions to the problem. What does the solution consist of? It can be:

1) Optimal argument values, i.e., argopt. This is argmin for minimization and argmax for maximization

2) Optimal objective value

Even if there is a unique argopt, a complete description of the optimal solution consists of the argopt and the optimal objective value. However, there are some problems for which the "user" of the solution does not care about both.

For instance, in worst case engineering analysis, the user may only care about the worst case objective value (or a good enough bound for it), but not care at all the argopt achieving it. The user may choose to use a lower bound on the optimal objective value (for a minimization problem), obtained from convex relaxation in a global optimization algorithm, if the gap is below a specified tolerance; and not have, or care about, an argument value which achieves it. So that problem is "solved" without having an optimal argument value.

On the other hand, if the objective function is only a proxy for (or inaccurate approximation or statistical estimation of) the "true: objective function, then in some cases, only the argopt may be of interest. Furthermore, if the optimal argument value is not unique, there is more than one argopt. The user may or may not care about getting all argopts.

For users only interested in optimal objective value, closeness of an approximate solution to the exact optimal solution is based on closeness of objective values. For users only interested in optimal argument value, closeness of an approximate solution to the exact optimal solution is based on closeness of argument values between approximate and exactly optimal solutions.

As for globally vs. locally optimal solutions. Some users are only interested in globally optimal solutions. Other users consider any locally (or globally) optimal solution to be a "solution". Depending on the user, a solution might consist of a (any) single locally or globally optimal solution, or of all locally optimal solutions.