Search code examples
f#clrdsllinear-programmingclp

LP DSL for F# with Clp as solver

Since the Microsoft Solver Foundation has been deprecated, I am trying to find an alternative or a reasonable way to create my own DSL.

What I am looking for is essential a DSL to describe a LP in F#, solve it with Clp and evaluate the results.

Before I reinvent the wheel: does someone know a good library that already provides a DSL for LPs?

Otherwise, how would you build such a DSL in F#? Essentially, I would like to be able to write something like

let xs = createVars 100 in 0..1
let ys = [| 1 .. 100 |]
let f i x = i*x
let lp = 
    minimize sumprod(xs, ys) subjectTo [
      xs.[0] + xs.[1] = 1
      sum(xs) <= 1
      sum({for i in 1..100 -> f i xs.[i]}) <= 100
      // ...
    ]
let solver = Clp()
let result = solver.solve lp
Solution

  • Before I reinvent the wheel: does someone know a good library that already provides a DSL for LPs?

    No, I don't know any except ODSL from Microsoft SolverFoundation itself.

    Otherwise, how would you build such a DSL in F#?

    1. Decide the syntax of the language. Although you want to build an internal DSL, you have to decide what are allowed and what are inexpressible in your language.

    2. Use F# quotations to obtain an AST. Why do you need reflection? First, you create a bunch of variables and combine them with float constants to form linear constraints. Later, you will fill up these variables with appropriate values. Reflection allows you to create placeholders and calculate results later.

    3. Transform ASTs to linear programs in CLP and solve. It seems CLP doesn't have .NET API; you could communicate with the solver via command lines, but it isn't very convenient and robust. It is good idea to start building a low-level API before creating DSLs.

    4. (Optional) In F# 3.0, you can create a query syntax for your DSL. You can have a look at a convincing example, the built-in query expression.

    Since the Microsoft Solver Foundation has been deprecated, I am trying to find an alternative or a reasonable way to create my own DSL.

    Anyway, MSF will provide valuable examples for your work. You can browse through ODSL source code in this codebase. Indeed, from the codebase you can see that ODSL has completed three first steps. I'm building an optimization query language on top of ODSL (step 4) and have only finished the surface syntax. For example, this original example

    <@
        let sa = var<Barrel/Day>()
        let vz = var<Barrel/Day>()

        minimise (20.0<Dollar/Barrel> * sa + 15.0<Dollar/Barrel> * vz)

        where
            [
                0.3 * sa + 0.4 * vz >= 2000.<Barrel/Day>;
                0.4 * sa + 0.2 * vz >= 1500.<Barrel/Day>;
                0.2 * sa + 0.3 * vz >= 500.<Barrel/Day>;
                sa <= 9000.<Barrel/Day>;
                vz <= 6000.<Barrel/Day>;
                sa >= 0.<Barrel/Day>;
                vz >= 0.<Barrel/Day>  
            ]
    @>

    would be transformed to

    opt { let! sa = var<Barrel/Day>()
      let! vz = var<_>()
      assume (0.3 * sa + 0.4 * vz >= 2000.<_>)
      assume (0.4 * sa + 0.2 * vz >= 1500.<_>)
      assume (0.2 * sa + 0.3 * vz >= 500.<_>)
      assume (sa <= 9000.<_> && sa >= 0.<_>)
      assume (vz <= 6000.<_> && vz >= 0.<_>)   
      minimise (20.0<Dollar/Barrel> * sa + 15.0<_> * vz)
    }

    I have also translated a number of DSL examples here in case you're interested.