/LPFramework

LPFramework is an abstraction to programmatically formulate mixed-integer linear optimization (MILP) problems, which can then be solved using open-source/commercial solvers.

Primary LanguageKotlinMIT LicenseMIT

Linear Programming Framework

This project is an attempt to generate a common API for modeling (mixed integer) linear programs in Java/Kotlin, which can then be solved using multiple open-source or commercial solvers. The project currently supports the following solvers:

How it works

The project defines a generic API to define a linear optimization problem. The problem is encapsulated in an LPModel object, which can be initialized independently of the solver in question.

val model = LPModel("Test Instance")

The syntax supports three types of variables:

  • Boolean (Integer variables with only 0 or 1)
  • Integer
  • Double

and variables can be defined as follows:

model.variables.add(LPVar("X", LPVarType.BOOLEAN))         // variable defined with default bounds
model.variables.add(LPVar("Y", LPVarType.INTEGER, 0, 10))  // variables defined with explicit bounds

Variables can also be grouped into specific categories with string keys, which makes it easier to access them at a later point in time:

model.variables.add("some-group", LPVar("Z", LPVarType.DOUBLE, -2.5, 6))

Constraints can be defined by setting up terms on the Left/Right-Hand Side (LHS) expressions, coupled with an operator:

// Constraint : X + Y >= 2Z + 3
val c = LPConstraint("Constraint 1")
c.lhs
  .addTerm("X")
  .addTerm("Y")
c.rhs
  .addTerm(2, "Z")
  .add(3)
c.operator = LPOperator.GREATER_EQUAL
model.constraints.add(c)

The model also has the option to use named constants. Constraints can be defined against named constants, and their values can be specified at a later point in time:

// Constraint 2 : aX + bY + cZ <= 4
val c = LPConstraint("Constraint 2")
c.lhs
  .addTerm("a", "X")
  .addTerm("b", "Y")
  .addTerm("c", "Z")
c.rhs.add(4)
c.operator = LPOperator.LESS_EQUAL
model.constraints.add(c)

// Add constants
model.constants.add(LPConstant("a", 1))
model.constants.add(LPConstant("b", 2))
model.constants.add(LPConstant("c", 3))

Finally, objective functions can be defined as an expression, and an optimization direction (Minimize / Maximize):

// Objective function => Maximize : X + Y + 2Z
model.objective.expression
  .addTerm("X")
  .addTerm("Y")
  .addTerm(2, "Z")
model.objective.objective = LPObjectiveType.MAXIMIZE

In order to solve a model, include an instance of the lp-solver in the classpath as a runtime dependency, and solve a model as:

val solver = Solver.create(model)
solver.initialize()
val status = solver.solve()

Project Structure

The core of the Linear Programming framework is divided into three modules:

  • lp-api defines the constructs used to describe a linear optimization problem.
  • lp-solver is an abstract interface to a solver, which is implemented for each of the three frameworks in
  • lp-rw implements mechanisms to import/export models and computed results to different file formats.

Additionally, some sample problem instances can be found in the lp-solver-sample module.