22
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Interesting answers so far! I notice that using "point" instead of "solution" would make all weird intepretations disappear. However, "point" may have unwanted connotations and not convey the right impression. Using "solution" instead of "point" is certainly good marketing! $\endgroup$ – Dirk Jul 10 '19 at 7:51
  • 1
    $\begingroup$ A lot of the confusion arises from the fact that in normal English usage, "solution" means something like "the right answer". But in optimization, a "solution" can be suboptimal or even infeasible, as you and others have noted. $\endgroup$ – LarrySnyder610♦ Jul 10 '19 at 13:33
  • $\begingroup$ I think that the rest of mathematics (and probably also the rest of science?) also uses "solution" in the same way as plain English. $\endgroup$ – Dirk Jul 10 '19 at 13:56
  • 1
    $\begingroup$ We like to go against the flow. :) $\endgroup$ – LarrySnyder610♦ Jul 10 '19 at 13:59
  • $\begingroup$ MaxFlow? MinFlow? $\endgroup$ – Dirk Jul 10 '19 at 14:08
14
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ What is an infeasible optimal solution? $\endgroup$ – Dirk Jul 10 '19 at 18:38
  • $\begingroup$ @Dirk when optimality conditions are fulfilled, eg complementary slackness in linear programming, but the solution does not satisfy all the constraints, eg nonnegativity does not hold. $\endgroup$ – Marco Lübbecke Jul 10 '19 at 18:52
  • $\begingroup$ I thought that the constraints are part of the optimality conditions (that the case for the KKT conditions, for example). Do you mean that just some part of the optimality conditions have to be fulfilled? Or does this only occur for a special class of optimization problems? $\endgroup$ – Dirk Jul 10 '19 at 19:16
  • $\begingroup$ you are right, primal feasibility is part of the definition. this is because KKT and complementary slackness make statements about primal and dual solutions being optimal, respectively. When I find the time I write up an exmaple from linear programming.... $\endgroup$ – Marco Lübbecke Jul 10 '19 at 19:34
8
$\begingroup$

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...

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ very interesting, @Geoffrey, practitioners list a lot of constraints that their solutions should fulfill, we build solutions that fulfill all these constraints (sometimes we even prove that they are optimal) and then the practitioners tell us that their solutions are better. How come? Because their solutions often violate their constraints... $\endgroup$ – Marco Lübbecke Jul 10 '19 at 7:41
  • 1
    $\begingroup$ That is very familiar! "Hard" is often relative (except for physical constraints like 1 person being at 2 locations at the same time). And of course, don't forget about the hidden constraints that they didn't mention because they are either too obvious or too complex to explain in the problem description. $\endgroup$ – Geoffrey De Smet Jul 10 '19 at 11:57
  • $\begingroup$ @MarcoLübbecke I don't know if this is how you or others use it, but when I talk about building "something" for the user, that "something" is the model. That model provides the solution and we can then, compare our solutions and their values. $\endgroup$ – EhsanK♦ Jul 10 '19 at 12:58
  • 1
    $\begingroup$ @EhsanK hm. that "something" is a prototype, it needs problem > data > model > algorithm > implementation > solution > plausibility > installation (> iteration) $\endgroup$ – Marco Lübbecke Jul 10 '19 at 13:02
  • $\begingroup$ Sure @MarcoLübbecke. I was mainly referring to your "..we build solutions that fulfill ..." and to me (nitpicking obviously!) that should be "..we build model that.." and then through algorithm implementation, we will have the solutions. But your steps above show that we are on the same page anyway! $\endgroup$ – EhsanK♦ Jul 10 '19 at 14:31
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ :) I agree with the first sentence. The second refers to a particular situation, maybe in a local search, but not generally in math prog, or? The third: I think of eg a SCIP method trysol() where I check a solution not the problem for feasibility. $\endgroup$ – Marco Lübbecke Jul 10 '19 at 9:31
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I distinguish between a solution and its value. So, when I speak of solution I always refer to the argument, not the value. This is why I regularly mark a sentence as wrong that is like "a lower bound on the solution is...", only values can be bounded. $\endgroup$ – Marco Lübbecke Jul 10 '19 at 12:10
  • $\begingroup$ @Marco Lübbeck My point is that the optimal objective value by ittslef, without knowledge of optimal argument value, can constitute a solution to an optimization problem, depending on the user's needs. But yes, if I were referring to a lower bound, I would make clear on what (could be on optimal objective value, could even be on one or more components of optimal argument value). $\endgroup$ – Mark L. Stone Jul 10 '19 at 12:20
  • $\begingroup$ @Marco Lübbecke, vectors can be bounded too; by bound sets. We work with those objects in multi objective optimization. $\endgroup$ – Sune Jul 10 '19 at 14:14
  • $\begingroup$ @sune sure, but the context was "solution or its value"... $\endgroup$ – Marco Lübbecke Jul 10 '19 at 14:19
  • 1
    $\begingroup$ @Marco Lübbecke, I know and maybe I was a bit pedantic. I just consider the outcome vector corresponding to a solution as the objective function value. $\endgroup$ – Sune Jul 10 '19 at 14:49

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.