Introduction
Here, I will introduce you to one of the easiest and most commonly used tools for coding linear optimization problems in Kotlin using the S2 library. In addition to providing a brief introduction to optimization and linear programming, it can also be used by readers who have no prior knowledge of Optimization, Prescriptive Analytics or Operations Research to gain a better understanding of what the article will discuss. Also, we will discuss mathematical notations for formulating LPs.
A set of decisions are controlled in a constrained environment in order to find the maximum or minimum value of a given objective. Essentially, an optimization problem involves carefully choosing input values within a set of allowed values to maximize or minimize a real function.
Ultimately, the objective function is to minimize the cost of delivering goods to customers from a warehouse by selecting the optimal route and the optimal set of vehicles (decision variables), given a limited number of drivers and limited time (constraints). In the world of Operations Research and Optimization, this is a generic example of Route Optimization.
In the field of Computer Science, another very popular problem is the Travelling Salesman Problem, where our goal is to find the shortest route between all cities, given their pairwise distances. Essentially, we are minimizing the total distance (or cost) travelled, using binary variables to determine if the traveller should travel from City i to City j, and applying constraints to ensure that the traveller doesn’t visit the same city twice and covers all the cities. In addition, today we’ll handle a similar, but simpler, problem.
A brief introduction to Linear Programming
The concept of linear programming can be viewed as a subset of optimization. It is an optimization technique in which a linear objective function is determined by varying a set of decision variables in order to find the optimal value.
Understanding the problem in hand
The goal is to minimize shipping costs between two different warehouses and four different customers. Warehouses have a limited supply, and customers have a certain demand. Using limited supplies available at each warehouse, we can satisfy customer demands by shipping products from given warehouses, which will reduce the overall shipping cost. Crocs, for example, sells only footwear, and its distributors order the footwear in bulk from the company. The products to be supplied are uniform in nature.
The cost of shipping matrix for Warehouse i to Customer j is as follows. Each value can also be represented as Cij suggesting Cost C to ship from Warehouse i to Customer j.
The customer demands and the warehouse availability is as follows.
Defining the problem
The first step is to formulate the problem using mathematical equations. In order to develop our LP, we need to identify three key components:
Decision Variables
Xij is our decision variable, which indicates that X products should be delivered from Warehouse i to Customer j.
Objective Function
We need to minimize the overall cost of shipping these products, which is our objective function. Therefore, objective function is
Constraints
Supply Constraints: These constraint basically state that each warehouse’s overall supply to all four customers will not exceed its maximum capacity/availability.
Demand Constraints: According to these constraints, the supply done across the two warehouses should match (or exceed) the demand of each customer. In our objective function, we might always try to minimize costs so that we never supply more than is needed, so we can use > instead of =. Some optimization problems cannot be solved with strict equality constraints, so we do this. The situation here, however, is different.Demand Constraints
Let's Code it
%use s2
println("LP problems of different forms")
// construct an LP problem in standard form
val problem1 = LPStandardProblem(
DenseVector(-1.0, -1.0, 0.0, 0.0), // c dense vector for double array
LinearEqualityConstraints(
DenseMatrix( // matrix for array
arrayOf(
doubleArrayOf(7.0, 1.0, 1.0, 0.0), //array
doubleArrayOf(-1.0, 1.0, 0.0, 1.0) //array
)
),
DenseVector(15.0, 1.0) // b
))
println(problem1)
// construct an LP problem in canonical form 1
val problem2 = LPCanonicalProblem1(
DenseVector(-1.0, -1.0, 0.0, 0.0), // c
DenseMatrix(
arrayOf(
doubleArrayOf(7.0, 1.0, 1.0, 0.0),
doubleArrayOf(-1.0, 1.0, 0.0, 1.0),
doubleArrayOf(-7.0, -1.0, -1.0, 0.0),
doubleArrayOf(1.0, -1.0, 0.0, -1.0),
)
),
DenseVector(15.0, 1.0, -15.0, -1.0) // b
)
println(problem2)
/**
* Example 3-4-1.
*
* Linear Programming with MATLAB
* by Michael C. Ferris, Olvi L. Mangasarian, Stephen J. Wright.
*/
println("Solving an LP problem")
// construct an LP problem
var problem = LPProblemImpl1(
DenseVector(4.0, 5.0), // c
LinearGreaterThanConstraints(
DenseMatrix(
arrayOf(
doubleArrayOf(1.0, 1.0),
doubleArrayOf(1.0, 2.0),
doubleArrayOf(4.0, 2.0),
doubleArrayOf(-1.0, -1.0),
doubleArrayOf(-1.0, 1.0)
)
),
DenseVector(-1.0, 1.0, 8.0, -3.0, 1.0)), // b
null, // less-than constraints
null, // equality constraints
null) // box constraints
// construct the simplex tableau for the LP problem
var table0 = SimplexTable(problem)
println("simplex tableau for the problem:")
println(table0)
// solve the LP problem using the 2-phase algorithm
val solver = LPTwoPhaseSolver()
val solution = solver.solve(problem).minimizer() as LPBoundedMinimizer
println(String.format("minimum = %f%n", solution.minimum()))
println(String.format("minimizer = %s%n", solution.minimizer()))
Thank you so much I hope you learned something new and exciting.