Linear Programming Solver
Jorunn Collet
I'm pretty new to linear programming, I did solve my first problem with lpsolve (binary dll called from Java, via the JavaILP wrapper to have a more object-oriented code) and it was very fast (50 ms).
ojAlgo separates between model and solver. The model uses BigDecimal internally. The model analyses the problem and calls different solvers depending on problem characteristics. The solvers can work with whatever number type they want. The built-in ojAlgo solvers work with primitive double.
Another endorsement for COIN-OR. We found that the linear optimiser component (Clp) was very strong, and the mixed integer component (Cbc) could be tuned quite well with some analysis. We compared with LP-Solve and GLPK.
Try the SCIP solver. I have used it for MILP problems with over 300K variables with good performance. Its MILP performance is much better than GLPK. Gurobi has also excellent performance for MILP problems (and typically better than SCIP (May 2011)), but it might be costly if you are not an academic user. Gurobi will use multicores to speed up the solver.
If, on the contrary, the problems are small, then the time for copying the problems from python's memory to the solver (back and forth) is not to be neglected anymore: in that case you may experiment some noticeable performance improvements using a compiled language.
Nevertheless you can be lucky and your model works fine with GLPK, Coin or the like, but in general open source solutions are way behind the commercial solvers. If it was different, no one would pay 12.000$ for a Gurobi license and even more for a CPLEX license.
I am surprised that nobody has mentioned MIPCL ( -cpp.appspot.com/index.html). This solver claims to be open source under LGPL license (source: -cpp.appspot.com/licence.html), thus it is also suitable to be used in non-open-source applications. But what is missing to be really open source is the source code of the solver itself.
In the Mixed Integer Linear Programming Benchmark with 12 threads and a time limit of 2 hours MIPCL managed to solve 79 instances. Only the commercial solvers CPLEX, Gurobi and XPRESS managed to solve more under the given constraints (86 or 87 instances, respectively).
Also in terms of the chosen performance metric (again using 12 threads) MIPCL is faster than the benchmarked SCIP derivates (FSCIPC, FSCIPS) and the open source solver CBC. Again only the commercial solvers CPLEX, Gurobi and XPRESS outcompete MIPCL significantly in terms of performance.
I have used DICOPT using the NEOS server ( -server.org/neos/solvers/minco:DICOPT/GAMS.html) to solve large (approx 1k variables and 1k constraints) mixed integer non-linear programs and found it excellent.
Whilst, as others have pointed out, commercial solvers are much faster and more capable than the free alternatives it's important to consider how much of an optimality gap you can accept. For large problems with many integer variables you may get much faster solve-times if you can accept 1% or even greater optimality gap (defaults tend to be around 0.01% or less).
I would agree with others that using a platform that generates solver-independent problem files (such as *.mps, *.lp files) is worthwhile as you can then try out other solvers. I'm using PuLP and am finding it, and the free COIN_CBC solver, excellent. Although limited for problems with many integer variables.
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization).
More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polytope where this function has the largest (or smallest) value if such a point exists.
Linear programming can be applied to various fields of study. It is widely used in mathematics and, to a lesser extent, in business, economics, and some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proven useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.
In the late 1930s, Soviet mathematician Leonid Kantorovich and American economist Wassily Leontief independently delved into the practical applications of linear programming. Kantorovich focused on manufacturing schedules, while Leontief explored economic applications. Their groundbreaking work was largely overlooked for decades.
The turning point came during World War II when linear programming emerged as a vital tool. It found extensive use in addressing complex wartime challenges, including transportation logistics, scheduling, and resource allocation. Linear programming proved invaluable in optimizing these processes while considering critical constraints such as costs and resource availability.
Despite its initial obscurity, the wartime successes propelled linear programming into the spotlight. Post-WWII, the method gained widespread recognition and became a cornerstone in various fields, from operations research to economics. The overlooked contributions of Kantorovich and Leontief in the late 1930s eventually became foundational to the broader acceptance and utilization of linear programming in optimizing decision-making processes.[2]
Kantorovich's work was initially neglected in the USSR.[3] About the same time as Kantorovich, the Dutch-American economist T. C. Koopmans formulated classical economic problems as linear programs. Kantorovich and Koopmans later shared the 1975 Nobel prize in economics.[1] In 1941, Frank Lauren Hitchcock also formulated transportation problems as linear programs and gave a solution very similar to the later simplex method.[4] Hitchcock had died in 1957, and the Nobel prize is not awarded posthumously.
From 1946 to 1947 George B. Dantzig independently developed general linear programming formulation to use for planning problems in the US Air Force.[5] In 1947, Dantzig also invented the simplex method that, for the first time efficiently, tackled the linear programming problem in most cases.[5] When Dantzig arranged a meeting with John von Neumann to discuss his simplex method, Neumann immediately conjectured the theory of duality by realizing that the problem he had been working in game theory was equivalent.[5] Dantzig provided formal proof in an unpublished report "A Theorem on Linear Inequalities" on January 5, 1948.[3] Dantzig's work was made available to public in 1951. In the post-war years, many industries applied it in their daily planning.
Dantzig's original example was to find the best assignment of 70 people to 70 jobs. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the observable universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the simplex algorithm. The theory behind linear programming drastically reduces the number of possible solutions that must be checked.
The linear programming problem was first shown to be solvable in polynomial time by Leonid Khachiyan in 1979,[6] but a larger theoretical and practical breakthrough in the field came in 1984 when Narendra Karmarkar introduced a new interior-point method for solving linear-programming problems.[7]
Linear programming is a widely used field of optimization for several reasons. Many practical problems in operations research can be expressed as linear programming problems.[3] Certain special cases of linear programming, such as network flow problems and multicommodity flow problems, are considered important enough to have much research on specialized algorithms. A number of algorithms for other types of optimization problems work by solving linear programming problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. Likewise, linear programming was heavily used in the early formation of microeconomics, and it is currently utilized in company management, such as planning, production, transportation, and technology. Although the modern management issues are ever-changing, most companies would like to maximize profits and minimize costs with limited resources. Google also uses linear programming to stabilize YouTube videos.[8]
Suppose that a farmer has a piece of farm land, say L km2, to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, F kilograms, and pesticide, P kilograms. Every square kilometer of wheat requires F1 kilograms of fertilizer and P1 kilograms of pesticide, while every square kilometer of barley requires F2 kilograms of fertilizer and P2 kilograms of pesticide. Let S1 be the selling price of wheat per square kilometer, and S2 be the selling price of barley. If we denote the area of land planted with wheat and barley by x1 and x2 respectively, then profit can be maximized by choosing optimal values for x1 and x2. This problem can be expressed with the following linear programming problem in the standard form:
Linear programming problems can be converted into an augmented form in order to apply the common form of the simplex algorithm. This form introduces non-negative slack variables to replace inequalities with equalities in the constraints. The problems can then be written in the following block matrix form:
760c119bf3