In this post I present a Groovy framework for Linear Programming (hereafter LP) reductions. The term 'framework' denotes that its expressive power covers the reduction of any problem P into LP.
Given a Problem P with a domain D and range (or solution domain if you wish) R, we say that a problem P reduces to LP, if you can use an algorithm that solves LP to solve P. The reduction includes 3 steps (a nice visual representation can be found at page 9/46 of this):
1. given an instance x of P, map it to an instance y of LP;
2. solve y by an algorithm (in this case Simplex) for LP, to derive a solution, let's denote it with LP(y);
3. map LP(y) to the solution of x.
The mapping functions that are needed by steps (1) and (3) are passed as inputs in the form of Groovy closures, while step (2) is delegated to Apache Math3 Simplex implementation by default, although abstractions for replacing this with the solver of your wish are provided.
Of course, not any possible combination of map functions in step (1) and (3) lead to a reduction. You need to prove that a certain combination is proper. The framework presented here does not verify the combination is proper (there are certain limitations even if we wished to do so), but assumes it is proper.
Specifically for B=LP:
1. LP is polynomial. The ellipsoid algorithm solves this polynomially, although the simplex algorithm (which is exponential in the worst case) is much faster in practice.
2. The expressive power of LP and its massive application in the financial sector (e.g. see operations research) has led to very efficient, commercial simplex implementations offered by many business analyst vendors, like IBM.
Given a Problem P with a domain D and range (or solution domain if you wish) R, we say that a problem P reduces to LP, if you can use an algorithm that solves LP to solve P. The reduction includes 3 steps (a nice visual representation can be found at page 9/46 of this):
1. given an instance x of P, map it to an instance y of LP;
2. solve y by an algorithm (in this case Simplex) for LP, to derive a solution, let's denote it with LP(y);
3. map LP(y) to the solution of x.
The mapping functions that are needed by steps (1) and (3) are passed as inputs in the form of Groovy closures, while step (2) is delegated to Apache Math3 Simplex implementation by default, although abstractions for replacing this with the solver of your wish are provided.
Of course, not any possible combination of map functions in step (1) and (3) lead to a reduction. You need to prove that a certain combination is proper. The framework presented here does not verify the combination is proper (there are certain limitations even if we wished to do so), but assumes it is proper.
Background
Generally, algorithmic reductions are very useful for both theoretical and practical reasons. For instance, if A reduces to B polynomially (i.e. the mapping functions are polynomial) and B is a polynomial problem, then A is polynomial as well (for more details about the significance of reductions you can read this or this). In addition, if you have an efficient implementation for an algorithm B, but not for A, you can leverage this implementation.Specifically for B=LP:
1. LP is polynomial. The ellipsoid algorithm solves this polynomially, although the simplex algorithm (which is exponential in the worst case) is much faster in practice.
2. The expressive power of LP and its massive application in the financial sector (e.g. see operations research) has led to very efficient, commercial simplex implementations offered by many business analyst vendors, like IBM.
Source code, Dependencies, License
The lp-reduction framework is an open source project licensed under Apache License, Version 2.0.
The code is hosted by github under the lp-reduction repository.
Gradle is used for building and dependency management.
The only compile time dependency is the Apache Commons Mathematics Library, while testing is done with Spock.How it works
The implementation is straightforward as the main class (LPReduction) suggests:
Step (1) is implemented by 'mapToLP' method. It takes as input an instance x of P and returns the LP instance y. To do so it calls the 'vars'/'objFunc'/'constraints' closures that are defined as class fields in order to create the LP variables/objective function/constraints respectively. How they are initialized will be clarified later with an example.
Notice that the LPInstance class has two more boolean fields, namely 'max' and 'nonNegative'. The former indicates whether this is a maximization (default option) or a minimization (set max=false for this) problem.
Moreover, it is possible that an LP instance has empty (technically any constant, usually 0) objective function and in this case it is often called constraint satisfaction problem. This happens when you only need to know if there is a solution that simultaneously satisfies all the constraints, without having any quantity to maximize/minimize. This case is handled by the line:
objFunc ? objFunc(x) : new LPFunction([:], 0)
which means "if the closure objFunc is set (i.e. not null), call it, else use the empty objective function (i.e. f(x)=0)".
Step (2) is implemented by 'solve' method, which takes as input an LP instance y and returns its solution. If no solver is set (default option), the Apache Math3 Simplex is used to solve y, else the user provided solver is used. To allow this LPSolver interface provides the proper abstraction:
The solution is modeled by Solution class:
The whole reduction is implemented by 'reduce' method. Obviously, it runs the first two steps as explained above and then it calls the 'result' closure to map the solution of the LP instance y to the solution of P for x.
Notice that the LPInstance class has two more boolean fields, namely 'max' and 'nonNegative'. The former indicates whether this is a maximization (default option) or a minimization (set max=false for this) problem.
Moreover, it is possible that an LP instance has empty (technically any constant, usually 0) objective function and in this case it is often called constraint satisfaction problem. This happens when you only need to know if there is a solution that simultaneously satisfies all the constraints, without having any quantity to maximize/minimize. This case is handled by the line:
objFunc ? objFunc(x) : new LPFunction([:], 0)
which means "if the closure objFunc is set (i.e. not null), call it, else use the empty objective function (i.e. f(x)=0)".
Step (2) is implemented by 'solve' method, which takes as input an LP instance y and returns its solution. If no solver is set (default option), the Apache Math3 Simplex is used to solve y, else the user provided solver is used. To allow this LPSolver interface provides the proper abstraction:
The solution is modeled by Solution class:
The whole reduction is implemented by 'reduce' method. Obviously, it runs the first two steps as explained above and then it calls the 'result' closure to map the solution of the LP instance y to the solution of P for x.
The Max Flow Reduction Example
The code below exercises the lp-reduction framework for reducing the Max Flow problem to LP. You can read here what the Max Flow problem is and how an instance of it can be mapped to an LP instance.
As shown above, you can initialize an LPReduction object fields with the 'with' Groovy keyword. After defining the LPReduction object, you can exercise it as shown in MaxFlowSpec.groovy. Notice that the code inside the closures vars/objFunc/constraints/result can be written in Java instead of Groovy. However, you can not replace the entire closure with a Java 8 lambda as Groovy is not compatible with lamdas.
The full code can be found github under the lp-reductions repository.
As shown above, you can initialize an LPReduction object fields with the 'with' Groovy keyword. After defining the LPReduction object, you can exercise it as shown in MaxFlowSpec.groovy. Notice that the code inside the closures vars/objFunc/constraints/result can be written in Java instead of Groovy. However, you can not replace the entire closure with a Java 8 lambda as Groovy is not compatible with lamdas.
The full code can be found github under the lp-reductions repository.
The Graph Realization Reduction Example
The following code exercises the lp-reduction framework for reducing the Graph Realization problem to LP.
Notice that in its original version the Graph Realization is a decision problem, i.e. is there any graph with the given sequence, YES or NO? In practice, it is often useful to ask for a graph with the given sequence if such a graph exists. To define the decision version you need to define the result closure as:
result = { Solution s-> s.state==LPIState.FEASIBLE }
while for the modified version you need to define it as
result = { Solution s -> s.state==LPIState.FEASIBLE ? s.at : null }
After defining the LPReduction object, you can exercise it as shown in GraphRealizationSpec.groovy.
result = { Solution s-> s.state==LPIState.FEASIBLE }
while for the modified version you need to define it as
result = { Solution s -> s.state==LPIState.FEASIBLE ? s.at : null }
After defining the LPReduction object, you can exercise it as shown in GraphRealizationSpec.groovy.
