6
$\begingroup$

Is there a way of writing an algorithm with if-, while-statements to find an optimal solution without using linear-programming (LP)/MIP?

If so, what would the benefits be against the LP/MIP?

Is it then possible with the first method to get a solution with an x% margin to the optimal solution, for the sake of speed?

Employee scheduling could be one use-case.

$\endgroup$
  • 5
    $\begingroup$ I think this question is very broad. Maybe you could specify what kind of problem you want to solve? $\endgroup$ – Luke599999 Aug 22 '19 at 15:28
  • $\begingroup$ @Luke599999 employee scheduling could be an example. $\endgroup$ – Georgios Aug 22 '19 at 15:42
  • 3
    $\begingroup$ Algorithms for linear programming are also written with if and while statements, although we typically use optimization software so we don't have to worry about that. Can you clarify why you want a different algorithm? Free LP/MIP is available, or do you require something you can implement yourself? $\endgroup$ – Kevin Dalmeijer Aug 22 '19 at 16:47
  • $\begingroup$ @KevinDalmeijer The only reason why I would use a different algorithm is for the sake of speed. I have read that LP takes usually a lot of time to find an optimal solution, thus I wanted to find another method that delivers a solution that is good enough. $\endgroup$ – Georgios Aug 23 '19 at 7:53
17
$\begingroup$

As mentioned earlier, all algorithms are constructed using loops and conditional statements, including the algorithms employed by LP/MIP solvers. There are plenty of problems where it is more efficient to implement a "direct" algorithm using those constructs, rather than first write and algorithm that translates your problem data into a LP/MIP model, then execute the solver, and then translate the solution data back to your problem data. There are also plenty of problems that can not be modelled (in a straightforward way) by LP/MIP, such as non-linear optimization problems.

For many classic optimization problems such as Shortest Path, Maximum Flow and Minimum Spanning Tree, it is more common to find the exact solution with such "direct" algorithms, rather than by employing a MIP solver. If you need pointers on how "direct" algorithms that do not involve a LP/MIP solver work, you could look at the Wikipedia pages for Prim's algorithm (Minimum Spanning Tree), the Bellman-Ford algorithm (Shortest Path), or the Edmonds-Karp algorithm (Maximum Flow). While these may not be the fastest algorithms for their particular problems, they are relatively easy to understand compared to some of the more sophisticated methods for these problems. Some practical problems, including certain types of employee scheduling, can sometimes be written as a maximum flow problem (e.g. you want to maximize the number of tasks covered by employees that are only able to cover a certain number of tasks). To determine what is possible, it is very important to know the exact details of the problem: a small change in the specification of the problem you want to solve may render an algorithm totally useless. The advantage of the LP/MIP approach is that it is so flexible, and often is fast enough 'in practice', in particular with the powerful solvers that exist nowadays.

The question whether it is possible to get within a x% margin of the optimal solution is a different approach, and "direct" algorithms based on that idea exist as well. Sometimes these are heuristic methods, e.g. evolutionary algorithms or local search methods. Those algorithms usually do not give you a guarantee, although they often produce good solutions in practice. If you have an algorithm that guarantees the solution produced is within %x of the optimal solution, this is called an Approximation Algorithm. A famous example is the Christofides algorithm for the metric Travelling Salesman Problem, which combines a minimum spanning tree and a matching to obtain a tour that is guaranteed to be at most 50% longer than the shortest possible tour.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Greate examples. Although I had in mind that Greedy Algorithms such the Prim's algorithm, do not deliver the global optimum. Nevertheless, this could be a method of getting a solution, much faster than with the linear-programming approach, if I got it right. $\endgroup$ – Georgios Aug 23 '19 at 8:06
  • 5
    $\begingroup$ @Georgios Greedy algorithms can be optimal, depending on the problem. Prim's algorithm is optimal. $\endgroup$ – yassin Aug 23 '19 at 12:44
10
$\begingroup$

Yes, there are optimization algorithms that do not use LP/MIP solvers as a component. Most of these are problem specific algorithms, for example the Dijkstra algorithm for the shortest path problem. The power of LP and MIP is that you have one algorithm to solve many different kinds of problems fairly reliable. Problem specific algorithms can be better in some cases, but its also a lot more effort to implement, test and debug them than just modeling a problem and using a solver.

Constraint programming is an alternative to MIP that has a similar range of problems it can solve. Specifically for scheduling problems, a constraint programming solver might do better than MIP, but your mileage may vary.

I guess there are algorithms for employee scheduling out there. I would expect most of them to be heuristics, i.e. not guaranteeing optimal solutions and probably not a dual bound, which probably is what you mean by x% margin.

A problem might also be that employee scheduling can have all kinds of side constraints that make it difficult to implement one algorithm that many different people can use. This again is a strength of LP/MIP.

As Orguz Toragay pointed out, it is always possible to enumerate all solutions and keep the best. As soon as problems are larger than a hand full of variables this will quickly be impossible because of combinatorial explosion.

Lastly, there are many problem specific algorithms that use LP/MIP solvers (or CP, or SAT, or ...) as part of them to get dual bounds or solve sub-problems. That is probably the first thing to try if LP/MIP does not perform well enough for ones use case.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Could you provide a paper/tutorial/example of a problem where LP/MIP solver does not perform well and where we use a mix of a specific algorithm with solvers ? $\endgroup$ – Antarctica Sep 9 '19 at 19:28
  • $\begingroup$ A classic example is the traveling salesman problem (TSP). Out of the box MIP solvers do bad on TSPs, but the best TSP (Concorde, math.uwaterloo.ca/tsp/concorde.html) depends on fast simplex (LP solvers). Similarly, many airlines are using column generation algorithms that use LP and MILP solvers as part of a larger solution method for their problems that can't be tackled directly with MIP solvers. There are probably many more examples, but I can't point to a specific paper right now. $\endgroup$ – Philipp Christophel Sep 10 '19 at 7:43
8
$\begingroup$

A Construction Heuristic like First Fit Decreasing gets an ok solution for Employee Rostering. But of course, metaheuristics (such as Tabu Search) improve a lot on that solution.

First Fit Decreasing (a greedy algorithm) is relatively simple (just a few while/for and if statements), something like:

  1. Iterate the shifts based on start dateTime.
  2. For each shift, iterate through every employee and assign it the employee that gives the best overall score (= hard and soft constraint penalty), keeping the shifts already assigned in mind (but without changing those).
| improve this answer | |
$\endgroup$
8
$\begingroup$

Is it possible? Probably. Is it likely? Not really.

LP/MILP is a thoroughly studied field so it is very unlikely that a homebrew solution will outperform a commercial (or even open source) solver even for specialised cases (with very few exceptions). The algorithms used by modern solvers are very powerful (especially dual simplex), and come with decades of black magic, know-how and acceleration heuristics that are not always found in the literature.

Other people have covered the algorithmic perspective however my point of view is more on the implementation side since I develop optimisation solvers for a living, so I will share my thoughts on why linear solvers are highly likely to be superior to homebrew algorithms.

  1. Quality of implementation

A solver like CPLEX or GUROBI comes with many years of high quality implementation from people who really know what they are doing to ensure that it switches algorithms dynamically, employs acceleration heuristics, and scales well for large problem sizes. A typical example would be their in-house matrix factorisation algorithms which outperform anything we can find in open source.

  1. Numerical stability

For my company, this is the prime reason that we use commercial MILP solvers. Ensuring the quality of numerics, especially when it comes to matrices with numbers that span several orders of magnitude (and just can't be scaled well), is something very few people know how to do properly. Another typical example would be constraint propagation which is notoriously numerically unstable if implemented using normal floating point numbers.

  1. MIP Heuristics

When it comes to pure LP, open source is actually not much worse than commercial for decently sized problems. When integer variables are introduced however, the difference in performance can be 1000x or even more for large problems. The main reason is the MIP heuristics employed by commercial solvers. This information is a closely guarded trade secret.

  1. Finding an integral feasible point

Finding an integral feasible point is actually (if memory serves) NP-complete. People don't notice most of the time because solvers have great heuristics to find these initial feasible points in practice, but implementing that from scratch is quite non-trivial.

Coming back to my very first sentence, it is very possible to build a specialised solution if one knows what they are doing and decides they don't care about e.g. numerical stability for their application because that specific application happens to be well-behaved (for instance skip matrix preconditioning, scaling, or expensive numerics for stable constraint propagation). In any other case, my experience has been that solvers will win nearly every time.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Can you add a source for "finding a feasible point of an LP is NP complete"? $\endgroup$ – Michael Feldmeier Aug 24 '19 at 18:31
  • $\begingroup$ @MichaelFeldmeier I started a question to discuss this. $\endgroup$ – Nikos Kazazakis Aug 27 '19 at 0:58
  • 1
    $\begingroup$ @MichaelFeldmeier I updated the answer :) $\endgroup$ – Nikos Kazazakis Aug 27 '19 at 10:28
  • $\begingroup$ @nikaza I am very interested in making developing solvers for a living. Is there any way to contact you ? $\endgroup$ – Antarctica Sep 8 '19 at 0:56
4
$\begingroup$

Without using mathematical modeling you can(!) (except for the problems with continuous variables and/or infinitely many dimensions) enumerate all the candidates in the feasible solution space to find the best solution (which will be exact, optimal one). For sure you can write a code using if, while or for loops and evaluate all the candidates. Computational power to evaluate all the points in the feasible solution is one of the main drawbacks of enumeration. To avoid the computational burden, mathematical modeling has been used instead of enumeration although it is not guaranteed to solve all the problems optimally (local minima).

For your second question: Yes it is possible to define a margin from the optimal solution and find with enumeration the answers in that margin. But the question is if you have the optimal solution of a problem why do you need to find all the answers in a specific margin using other methods like enumeration. If you don't have the answer, how its possible to define a margin from optimality?

| improve this answer | |
$\endgroup$
  • $\begingroup$ So you mean yes it is possible but slower if I understood it right? So is there no other way to find a solution which is good enough but not optimal without using a LP? I know that I could use Heuristics but it is not possible to set a margin if I am not mistaken. The only reason for setting the margin is to speed up the finding of a solution. $\endgroup$ – Georgios Aug 22 '19 at 15:50
  • 1
    $\begingroup$ @Georgios yes you are right. You can also consider ML methods to approximate the solution but the problem with that approach is also the same (to find good and accurate results you need a fairly big train set, which means many instances of the problem to be solved). Some of Metaheuristic methods, by the way, gives you the opportunity to set a margin (percentage improvement in each step). $\endgroup$ – Oguz Toragay Aug 22 '19 at 15:56
  • 4
    $\begingroup$ I disagree that you can always enumerate all the candidate solutions, since there are plenty of problems with an infinite number of feasible solutions (e.g. continuous optimization problems) and even problems where a solution is infinitely dimensional (e.g. optimal control problems). For linear programming, we know that the optimum must be at one of the (finitely many) vertices, so enumeration is possible, but it is important to realize that in general this is not case. $\endgroup$ – Rolf van Lieshout Aug 23 '19 at 11:05
  • $\begingroup$ @RolfvanLieshout thanks for your comment, I will update my answer accordingly... $\endgroup$ – Oguz Toragay Aug 23 '19 at 12:21
  • 1
    $\begingroup$ You might also consider editing the second part of your question. You do not need to know the optimal solution to compute a valid optimality gap, all you need is a lower bound (in the case of a minimization problem). In the case of mixed integer linear programming, such bounds are derived from solving the linear relaxation. This is the reason that when you set the optimality tolerance of any solver to 0.05, it is guaranteed that the solver will terminate with a solution no more than 5 percent away from the optimum, even though the exact optimum is not known. $\endgroup$ – Rolf van Lieshout Aug 23 '19 at 13:50

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.