fslaborg / flips

Fsharp LInear Programming System

Flips : F# LInear Programming System

Full Documenation can be found here.

Flips is an F# library for modeling and solving Linear Programming (LP) and Mixed-Integer Programming (MIP) problems. It is inspired by the work of the PuLP library for Python and the excellent Gurobi Python library. It builds on the work of the outstanding Google OR-Tools library and the OPTANO library.

F# is a great language to work with but many of the existing APIs for modeling Optimization problems are heavily influenced by Object-Oriented concepts. While there is nothing wrong with OO, this is an attempt to take a functional-first approach to the problem.

This library tries to make the modeling of Optimization Models (LP/MIP) clean and simple. The idea was to make it straightforward for an Operation Researcher or Optimization domain expert to express their ideas in F#. These practitioners are used to working with Mathematical constructs like Sets, Sigma-notation, and summations. Reducing the mental distance between the mathematical formulation of problems and the F# representation was a key design goal.

F# developers should also find it comfortable to use this library. Over time I will be adding tutorials and training material on how to model Optimization Problems using this library. With a little training any F# developer will be able to add the powerful tool of Optimization to their repertoire.

Installation

To use Flips, simply add the nuget package to whatever project you are working on. The library comes with the CBC solver for Mixed-Integer Programming and the Google GLOPS solver for Linear Programming which are both free and open source.

Flips also supports the Gurobi and IBM CPLEX commercial solvers through the use of the excellent OPTANO library. You will need to get a separate license to use these libraries. The installation of these commercial libraries is not covered in this documentation since installation can depend on deployment and use case. Please refer to these vendors for commercial support in using their product. Flips currently only supports the latest version of each of these libraries.

License

All of flips projects are available as open source under the terms of the MIT license

flips's Issues

Add support for Gurobi solver

Packaging of new projects of dev branch as 2.9999-alpha-1

Consider having the continuous integration on dev branch to publish nuget with alpha packages.

This would allow anyone to play with the API without requiring to build the assemblies / nuget, instead, just referencing the published nuget as an artifact of the continuous integration pipeline.

I'm not familiar with azure actions and nuget publishing but maybe it can be done?

Model Compose Time regression tests

In order to ensure that we do not have regression in the compose time of models, we should have tests for a variety of model sizes. Ideally this would integrate with BenchmarkDotNet to make sure we are not adding significant runtime or memory allocations.

Logarithm function in Objective Function

hi, as the title says, my objective function is some thing like

1.0log(x1) + 2.0log(x2)
s.t. 1<= x1,x2 <= 10
x1 + x2 <= 20

seems flips is quite suitable but the log(x1) gives me error as Decision does not have member Log.
Wonder if the log function is supported by flips. I looked through the code and does not find any place to handle it. Not sure if it can be supported. If not, can you advise any dotnet package that can handle my problem above? Thank you very much.

Benchmark problems with answers

We should have a battery of tests with known solutions to ensure that the modeling of problems is accurately mapping to and from the backend solvers.

Add support for hierarchical optimization

Create Constraint Builder

Create a Computation Expression for generating sets of Constraints while automatically generating sensible names for constraints

Cannot get the package into a project via the Nuget package manager

When I attempt to add this as a project, I get the following error:

Could not install package 'Flips 1.2.0'. You are trying to install this package into a project that targets '.NETFramework,Version=v4.7.2', but the package does not contain any assembly references or content files that are compatible with that framework. For more information, contact the package author._

I also try to download the zip directly and build. When I do this, I can run the console test, however when I try to run the script flips-master\Flips\Scratchpad.fsx , I get the following errors:

error FS0229: Error opening binary file '..\flipsmaster\Flips.Examples\bin\x64\Release\netcoreapp3.1\google-ortools-native.dll': C:\Users\thrallL\Downloads\flips-master\Flips.Examples\bin\x64\Release\netcoreapp3.1\google-ortools-native.dll: bad cli header, rva 0
and

error FS3160: Problem reading assembly 'flips-master\Flips.Examples\bin\x64\Release\netcoreapp3.1\google-ortools-native.dll': Processing of a script fragment has stopped because an exception has been raised

Update sum and sumAll to work with Decision

There's a pain point when calling sum and sumAll for collections that hold Decision. The addition of the Decision type results in a LinearExpression. This does not work with the built in Sum methods which expect addition to be Monoidal.

Since SMap is the preferred container type for this library, I propose adding an override for Sum in the Slice Maps that deals with this scenario. This does not fix this for other collection types but it does for the primary use case.

Add documentation and examples for new SliceMap operators

Add addition operator for slice maps

Unnecessary printfn in Optano solve

Namespace / module formatting of tests.fs

What is an advantage of separating the namespace and module as is done in tests.fs?

flips/Flips.Tests/Tests.fs

Lines 1 to 3 in 73e4065

	namespace Flips.Tests
	module Types =

I don't know of any that apply to that file.

The alternative is to combine them like this.

module Flips.Tests.Types

An advantage of combining them is that there is one less level of indentation in the rest of the file.

I am willing to create a PR that combines them and reduce the indentation by one level in the rest of the file.

OPTANO Solve

The OPTANO based solve is not working

Addition/Subtraction of float for Decision

The Addition/Subtraction of float for Decision is not supported and it should be

Create Expression Evaluation Function

Need a function which: Solution -> LinearExpression -> float
This is needed to cleanly map back to the input values

Fill out tests for SliceMaps

Not all of the operations that can be performed on SliceMaps have test for them

Add support for CPLEX solver

LinearExpression.GetHashCode giving stack overflow exception

this one does a stack overflow:

#r @"C:\dev\src\github.com\matthewcrews\flips\bin\netstandard2.0\Flips.dll"
(Flips.Types.LinearExpression.OfFloat 1.0).GetHashCode()

this originates from:
https://github.com/matthewcrews/flips/blob/e6c9141a1cc1f9cee715cf20a2378b4be818c66c/Flips/Types.fs#L261-L262

there are few other implementation that looks the same.

current work around is to change the implementation to the rather crude hash (sprintf "%A" this) but this will be problematic.

Sourcelink

Add sourcelink to enable go-to-definition

LP File not generated for OPTANO solvers

When specifying an LP Output file, the file is not created when using OPTANO solver.

LP and MPS export files don't have the objective function in them

This seems related to the fact that the objective is set at the same time as solving, which happens after the calls to write the files happen:

https://github.com/matthewcrews/flips/blob/7951951714ae86f4a11397cf7af7eb3fa5fa7bd9/Flips/Solve.fs#L165-L169

Going to make a PR with a fix.

Create gens for the domain

Need to create Gens for the basic types to enable property based testing

Gens for

• DecisionType
• DecisionName
• Decision
• LinearElement
• LinearExpression

About F# code formatting guideline

If I would like to contribute to this (great) project, what F# code formatting style should I follow?

I am looking at this guideline. But it seems you are not exactly following it.

Extensibility: pre-run callback to initialize the underlying solver settings

Some problems require access to the underlying solver object to adjust specific settings before running the solver.

In the case of CPLEX, those parameters are defined in key / value pairs, where the key is a string, and the value may be one of:

• BooleanParam
• DoubleParam
• IntParam
• LongParam
• StringParam

https://perso.ensta-paris.fr/~diam//ro/online/cplex/cplex1271/refdotnetcplex/html/T_ILOG_CPLEX_Cplex_Param.htm

Investigate what other solvers do for similar concern and identify an approach to offer ability to adjust those settings pre-run.

Additional reference for cplex parameters:

https://www.ibm.com/support/knowledgecenter/ko/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/introListAlpha.html

https://www.ibm.com/support/knowledgecenter/ko/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/homepages/refparameterscplex.html?view=embed

SMap Addition incorrect

Add projections for the element-wise multiplication

Add some quality of life operators and features:

1. Extend the .* operator to handle SliceMaps of different dimensions.

For example:
SMap<'Key,'Value> .* SMap2<('Key1, 'Key2),'Value>
SMap<'Key,'Value> .* SMap3<('Key1, 'Key2, 'Key3),'Value>
etc.

2. Add the ability to "ReKey" a SliceMap to change the order of the dimensions in which the values are stored

3. Add the - operator to the Domain and SliceMaps

Adding zero constraints creates error

When using the Model.addConstraints function, an error is raised when the seq is empty

Add SMap6

There have been a couple of models that have gone up to the limit in the dimensions of SliceMaps. Adding SMap6 protects against coming up against the bounds.

preserve constraint names in google or-tools wrapper

When exporting the LP through the google or-tools wrapper, the constraint don't preserve the names.

https://github.com/matthewcrews/flips/blob/7951951714ae86f4a11397cf7af7eb3fa5fa7bd9/Flips/Solve.fs#L56-L74

The work around for now is to implement what Equality and RangeConstraint are doing in their Extract method.

I'm going to attempt this in a PR.

related: google/or-tools#2231

Publish a new nuget package compatible with FSharp.Core 5 and support for netstandard 2.0

I was looking to try the library using #r "nuget: Flips" but there is a warning because fsi uses FSharp.Core 5, and it seems netstandard2.1 isn't usable from .net framework.

Is it possible to retarget the library to netstandard2.0 and mark the nuget package compatible with fsharp.core 5?

Add subtraction for Domain types

Create the Solve module

Need to create the solve module which

• Translates a Model to the underlying solvers types
• Solves the underlying model
• Translates the solution to a Solution type

Model SliceMap interaction as trees

The LinearExpression update showed that there are significant performance improvements that can be made by modeling the expressions as tree structures. This made building them much faster. It would be good to give SliceMaps the same treatment because at the moment, they are slow for anything of significant size.

sourcelink all the things!

If you follow the advice over at the dotnet/sourcelink repo and

• Add a PackageReference to Microsoft.SourceLink.GitHub with PrivateAssets="All", and
• Make sure to either add your pdbs to your nuget package or embed them in the assembly with DebugType set to embedded (my preference), then

Users will be able to go to definition in editors like ionide, and debugging sessions will be able to step into your actual library code regardless of editor choice. Pretty nice for like a two line change.

Added DecisionMap builders

For convenience there should be functions for building DecisionMaps which follows the expected convention to help drag people down the pit of success.

Add support for constraint programming

I've used the CP-SAT Solver to optimize job scheduling (thousands of jobs that run daily) that takes into account specific dependencies, resources, and time constraints. It was a massive pain to understand how to use the Google.OrTools.Sat namespace as their documentation is quite sparse.

It would be nice to have it supported with this library. In particular it was a nightmare converting this into something usable.

Add Property tests for SliceMaps

Add element-wise addition for SliceMaps

Performance regression for adding large number of Constraints

The fix for adding empty list of Constraints created a performance regression in time to build a model

Consider adding a gh-page

As you add more features the README is going to get pretty big. As an example you can see the docs I have for Fable.Jester, and the elmish-book.

Add Slice Maps

One of the most useful features in formulating an optimization problem is creating a slice of an indexed collection. Being able to take slice across different dimensions is common in the formulation of Mathematical Optimization problems.

Create property based tests

Need to create Property based tests for the basic Domain types.

Key things to test:

• Addition operator of all types is associative and commutative
• Multiplication operator is associative and commutative
• Model type does not accept mismatched Decisions (Decisions with same name must have same type)

Flips 3.0 Design Proposal

Thinking some more about this, it would make sense to split the library into the domain / types parts (everything to build a Model object) and then have separate libraries for each solver which implement translation of Model back and forth with specific solver backends and provide the same simplified API as currently in the Solver module.

Using discriminated unions for the solver type and putting it in the Settings record is not the right approach.

The split between the three stages would remain :

• formulation
• runtime
• result extraction

but the runtime part would be opened up, while remaining simple for the simplest use cases:

// formulation
let formulation : Model =
   Model.create ...

// runtime
let solver = Flips.Solver.GoogleOrTools.Solver.createSolver Flips.Solver.GoogleOrTools.SolverSettings.basic
let result = Solver.solve formulation solver 

// result extraction
match result.Status with
| Optimal ->
  result.Decisions
  result.Objectives
| _ -> ...

For the specific solver settings, studying how Feliz model typed DSL over HTML format in a way which is convenient to use.

I think such API would benefit more advanced use case, also the benefit of splitting the assemblies / nuget packages, then you can reference only the model in projects dealing with formulation and handling the results back, and break down the dependencies in solver specific packages into Flips.Solver.* runtime packages.

Proposed assemblies:

• Flips everything up to Model
• Flips.Solver the abstraction defining the SolveResult and interface for running the solver with settings and mapping the results back to the Model
• Flips.Solver.GoogleOrTools backend using google-ortools, implementing the interfaces in Flips.Solver
• ...

Change composition rules for Decision

Right now it is clunky to get the result from the Solution type since the values for the Decisions are in a Map<DecisionName,float. While the reasoning for this was to ease the composition for the model, it makes actually extracting the results clunky.

I propose to make modeling slightly more complex but to dramatically ease the extraction of results by not have the create Decision functions return LinearExpression.

Decision CE returning nested tuples

The DecisionBuilder is returning indexes of nested tuples. The desire is for the tuples to be "flattened".

SourceLink

For an open source project, I don't think SouceLink is the best way to improve the development experience.

The alternative is to include the source in the NuGet package. The main advantage here is that users do not need an internet connection when they want to see the inspect the source code corresponding to the NuGet package (because they already got it when they obtained the NuGet package).

The main advantage of SourceLink for an open source project is a slightly smaller NuGet package.

Embedding the source in the NuGet package is accomplished with these two lines.

I am willing to PR for this.

code review: potential bug when building solution object in the or-tools codepath

currently the Solution object is hardcoded to the first objective in the Model object, which seems wrong (model.Objectives.[0]):

https://github.com/matthewcrews/flips/blob/7951951714ae86f4a11397cf7af7eb3fa5fa7bd9/Flips/Solve.fs#L169-L173

If #106 gets merged, the objective value will be available to replace that expression and there won't be need to fix that hardcoded lookup.

Missing filtering for SMap4

This piece of code should work but there is a missing overload:

pairingDecision.[All, period, mentor, All]

Add support for Units of Measure for Decision

Enable the use of Units of Measure with the Decision type

It would be nice for the user to be able to "opt-in" to using UoM with the basic building blocks of modeling but still be able to work without them. This would be akin to how float and float<'Measure> behaves in F#.

It would be nice for the following types to support UoM:

• Scalar
• Decision
• LinearExpression

Here is how they should interact:

Note: Instead of writing out 'Measure for the UoM, I abbreviate using 'M, 'M1,'M2, etc.

Function signatures for the + operator

The addition operator should force the UoM to match on both sides of the operator for types where addition is allowed. All of the function signatures are commutative

// Note: The Scalar type is a single case DU to wrap a float to override equality
// Scalar, float addition
Scalar * float -> Scalar
Scalar<'M> * float<'M> -> Scalar<'M>
Scalar<'M> * float // Compiler error: UoM do not match
Scalar<'M1> * float<'M2> // Compiler error: UoM do not match

// Scalar, Scalar addition
Scalar * Scalar -> Scalar
Scalar<'M> * Scalar<'M> -> Scalar<'M>
Scalar<'M> * Scalar // Compiler error: UoM do not match
Scalar<'M1> * Scalar<'M2> // Compiler error: UoM do not match

// Scalar, Decision addition
Scalar * Decision -> LinearExpression
Scalar<'M> * Decision<'M> -> LinearExpression<'M> 
Scalar<'M> * Decision // Compiler error: UoM do not match
Scalar * Decision<'M> // Compiler error: UoM do not match
Scalar<'M1> * Decision<'M2> -> // Compiler error: UoM do not match

// Scalar, LinearExpression addition
Scalar * LinearExpression -> LinearExpression
Scalar<'M> * LinearExpression<'M> -> LinearExpression<'M>
Scalar<'M> * LinearExpression  // Compiler error: UoM do not match
Scalar * LinearExpression<'M> // Compiler error: UoM do not match
Scalar<'M1> * LinearExpression<'M2> // Compiler error: UoM do not match

// Decision, Decision addition
Decision * Decision -> LinearExpression
Decision<'M> * Decision<'M> -> LinearExpression<'M>
Decision<'M> * Decision // Compiler error: UoM do not match
Decision<'M1> * Decision<'M2> // Compiler error: UoM do not match

// Decision, LinearExpression addition
Decision * LinearExpression -> LinearExpression
Decision<'M> * LinearExpression<'M> -> LinearExpression<'M>
Decision<'M> * LinearExpression // Compiler error: UoM do not match
Decision * LinearExpression<'M> // Compiler error: UoM do not match

// LinearExpression, LinearExpression addition
LinearExpression * LinearExpression -> LinearExpression
LinearExpression<'M> * LinearExpression<'M> -> LinearExpression<'M>
LinearExpression<'M> * LinearExpression // Compiler error: UoM do not match
LinearExpression<'M1> * LinearExpression<'M2> // Compiler error: UoM do not match

Function signatures for the * operator

The * operator should have the same behaviors around UoM that the float type follows.

// Scalar, float multiplication
Scalar * float -> Scalar
Scalar<'M> * float -> Scalar<'M>
Scalar * float<'M> -> Scalar<'M>
Scalar<'M1> * float<'M2> -> Scalar<'M1 * 'M2>

// Scalar, Scalar multiplication
Scalar * Scalar -> Scalar
Scalar<'M> * Scalar -> Scalar<'M>

// Scalar, Decision multiplication
Scalar * Decision -> LinearExpression
Scalar<'M> * Decision -> LinearExpression<'M>
Scalar * Decision<'M> -> LinearExpression<'M>
Scalar<'M1> * Decision<'M2> -> LinearExpression<'M1 * 'M2>

// Scalar, LinearExpression multiplication
Scalar * LinearExpression -> LinearExpression
Scalar<'M> * LinearExpression -> LinearExpression<'M>
Scalar * LinearExpression<'M> -> LinearExpression<'M>
Scalar<'M1> * LinearExpression<'M2> -> LinearExpression<'M1 * 'M2>

The Comparison Operators

In Flips <==, >==, and == are binary infix operators and are used to create ConstraintExpression by comparing two differnet LinearExpression. The Comparison Operators should enforce UoM when they exist.

// All the comparison operators have the following signatures
LinearExpression * LinearExpression -> ConstraintExpression 
LinearExpression<'M> * LinearExpression<'M> -> ConstraintExpression 
LinearExpression<'M> * LinearExpression // Compiler error: UoM do not match
LinearExpression * LinearExpression<'M> // Compiler error: UoM do not match
LinearExpression<'M1> * LinearExpression<'M2> // Compiler error: UoM do not match

The challenge is that when we construct the ConstraintExpression we have to ensure UoM match. Once we have a ConstraintExpression, we no longer care about UoM. A ConstraintExpression is a element of a Constraint type and a Model contains a Constraint list. Since UoM is a kind of type information we need to drop it or ignore it at some point so that a Model can have a Constraint list where the LinearExpression inside may be of different UoM.