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