4
$\begingroup$

I am using or-tools linear solver. and my problem ends up having no optimal solution. how can I tell the solver to find a suboptimal solution?

$\endgroup$
6
  • $\begingroup$ no optimal solution, or no solution at all ? $\endgroup$ – Kuifje Mar 30 at 8:06
  • $\begingroup$ this condition "status == pywraplp.Solver.OPTIMAL" is false. $\endgroup$ – Hisham Al Kayed Mar 30 at 8:09
  • $\begingroup$ and no solution is returned at all ? $\endgroup$ – Kuifje Mar 30 at 8:14
  • $\begingroup$ how can i check if a solution exists? i checked the status of the solver and it is "INFEASIBLE". $\endgroup$ – Hisham Al Kayed Mar 30 at 8:30
  • 5
    $\begingroup$ Ok, so in this case, there is no solution at all, and a fortiori no optimal solution. You cannot find a "suboptimal solution" as you state with the exact same constraints. You need to find out which constraints are being violated. $\endgroup$ – Kuifje Mar 30 at 8:37
2
$\begingroup$

"Sub-optimal" is a global optimisation term. In global optimisation, we refer to a "sub-optimal" solution as a solution that is optimal, i.e., it satisfies KKT, but is not the global solution (its value is not the best it can be, hence the term sub-optimal).

It is important to note that the counterpoint to "sub-optimal" is not "optimal", it is "globally optimal". Thus, sub-optimal solutions can be locally optimal if the problem is continuous nonlinear (they satisfy the KKT conditions).

If the solver reports that the solution is not optimal, then you have the following options:

  • Relax the constraint violation tolerance
  • Relax the integrality tolerance (if MIP)
  • Try different starting points (if nonlinear)
  • Check your model for inconsistencies

The last two are by far the most likely causes for not finding optimal solutions. Since you are solving linear problems, my money would be on the last one.

On a side note, MIP problems don't generally satisfy the KKT conditions (since derivatives are not defined) so calling their solutions "optimal" is an abuse of terminology, the right term is "feasible", and "best feasible" for the global solution. Nevertheless, the convention is to call those solutions optimal as well.

Update: There seems to be quite a bit of contention w.r.t. what the right terminology is, so even if this is out of scope of what the OP needed to know, I will elaborate on terminology and its origins below, just for the sake of correctness:

The most general definition of an optimisation problem, is to solve the problem of finding the best feasible solution.

From Wikipedia:

In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions.

This is a very broad definition that covers pretty much everything. Also notice that the word "optimal" does not appear here. This is not a coincidence.

Types of solutions

In optimisation, we can have two types of solutions based on constraint satisfaction:

  • Feasible solutions, and
  • Optimal solutions.

Based on objective value, we further have:

  • Best feasible solutions, and
  • Globally optimal solutions

A feasible solution is just that - a solution that satisfies all the constraints.

An optimal solution is something stronger. Both for linear and nonlinear programming, a point is optimal if and only if it satisfies the KKT conditions for optimality. You can find many references to this, e.g. here. For linear programming the conditions degenerate to simpler expressions, but it's KKT nonetheless.

Note that by "KKT conditions" I refer to all KKT conditions, i.e., the necessary and sufficient conditions, including the second-order conditions, along with the regularity conditions.

For nonlinear programming that's intuitive, as we have the concept of local optimality, however this is also necessary in linear programming, because it's very possible to have a feasible solution that is not on the globally optimal vertex (e.g., a Basic Feasible Solution), or not at a vertex at all (e.g. if we're using interior-point to solve the LP and terminate early). In continuous optimisation, the way we distinguish between merely feasible and "optimal" points, is through the KKT test.

Where we have what type of solution

The most important distinction here is that mixed-integer problems can not satisfy the KKT conditions because derivatives are not defined. Ergo, generally speaking, since "a solution is optimal iff it satisfies the KKT conditions", if the solution can not pass the KKT test (because we can't define derivatives), that solution can not be optimal. Therefore, it can only be some flavour of "feasible".

A second, more subtle point, is that we can (and do) get merely feasible solutions for continuous problems, e.g. when we use derivative-free methods such as evolutionary algorithms, or when we terminate a continuous solver after it has found a feasible point but before proving KKT satisfaction.

With the above in mind, this is the breakdown of what we can get for different types of optimisation problems:

  • LP & NLP: Feasible, optimal, globally optimal
  • MILP & MINLP: Feasible, best feasible

Sub-optimal

Now, circling back to what "sub-optimal" means, it depends on the problem being solved. For continuous problems, it technically refers to a solution that satisfies KKT but is not globally optimal. Some people abuse this terminology to also refer to feasible solutions that are not globally optimal.

In MI optimisation, this literally means nothing because the concept of optimality is not defined. The term "optimal" is still used here because it's too tedious to use different terminology, but it's an abuse of terminology nonetheless.

If the problem is MI, the "sub-optimal" can only refer to:

a feasible solution that is not the best feasible solution.

Intuition

If anyone is still in doubt about the correctness of this, just think about how we prove "optimality" for a mixed integer problem. We fix the integer variables (or relax them to continuous) and then solve those sub-(N)LPs to optimality many times in branch-and-bound. These sub-(N)LPs do satisfy KKT, but the original MI(N)LP problem does not. In fact, the very reason we fix/relax the integer variables is so that we can satisfy KKT.

Because branch-and-bound is a process of intelligent elimination, at some point we can prove that there is no better feasible solution that the one we currently have. However, even though this solution is referred to as "optimal", it will not necessarily satisfy the KKT conditions. In some cases it can, if the solution of the continuous relaxation happens to be integral, but in the general case it will not.

If you are still not convinced, you can always test this yourself. Simply get a solution to a mixed-integer problem and try to prove whether it passes the KKT test.

$\endgroup$
12
  • 3
    $\begingroup$ As optimal refers to best possible objective value, your claim that sub-optimal solutions are "optimal as well" is false, as sub-optimal literally means 'under optimal'. Furthermore, calling solutions to a MIP optimal is not "an abuse of terminology", as MIPs are defined as optimization problems. I do however agree that colloquially when people say "my MIP has no solution", that they mean that the feasible region is empty, or their computer program returns no solution, as OP has experienced. I do agree that most likely the constraints have a mistake in the implementation $\endgroup$ – DaPurr Apr 5 at 9:27
  • 3
    $\begingroup$ " Both for linear and nonlinear programming, a point is optimal if and only if it satisfies the KKT conditions for optimality." Wut? In general, KKT is neither necessary nor sufficient for ootimality. Regarding necessity, aside from continuous differentiability, there is also the matter of constraint qualification. So I completely disagree with your answer (but have not cast a vote yea or nay). $\endgroup$ – Mark L. Stone Apr 6 at 18:45
  • 3
    $\begingroup$ Not exactly a web site I would rely on.From the link in the immediately preceding comment: "KKT conditions is the necessary conditions for optimality in general constrained problem." I stand by my previous comment. $\endgroup$ – Mark L. Stone Apr 6 at 21:42
  • 4
    $\begingroup$ The KKT conditions can never be sufficient in general. That would imply f'(x)=0 is sufficient for a minimum which we know is not the case. So Mark is right. $\endgroup$ – ErlingMOSEK Apr 7 at 11:15
  • 3
    $\begingroup$ Well, if you apply the KKT conditions to min f(x) using the definition en.wikipedia.org/wiki/… then the KKT conditions are not sufficient. If you claim f is convex or some other additional conditions you might be correct. $\endgroup$ – ErlingMOSEK Apr 7 at 12:12
6
$\begingroup$

If your linear program does not have an optimal solution one of three things might be the case:

  1. The solver didn't find the optimal solution, even though it exists. This might be due to runtime or storage space limitations. However this should rarely be the problem, unless you have huge LPs.

  2. There is no optimal solution, because the problem is unbounded and therefore there are arbitrarily good solutions. Think: $\max x$ s.t. $x \geq 0$

  3. There exists no solution at all. Think: $1 \leq x \leq 0$

In cases 2 and 3 check you model: Is this a reasonable result? Is there maybe an error in the model or in the implementation or in the data?

Case 2 is the only case where you can reasonable want a "sub-optimal" solution, which I take to mean a feasible, but not optimal solution. To obtain it, get any feasible solution.

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