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?
"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.
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
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.
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.
If your linear program does not have an optimal solution one of three things might be the case:
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.
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$
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.