quandary.quandary — io.github.mlimotte/quandary 0.9.0

A wrapper for Google's OR-Tools for linear programming and satisfaction solver. OR-Tools has several solvers, we use the CP-SAT Solver: https://developers.google.com/optimization/cp/cp_solver

A demonstration of a minimal Linear Programming example to showcase calling the solver.

Some reference links:

• Help on Integer logic with Or Tools (sample): https://git.xkool.org/hw/or-tools/-/blob/e59073c45f054867ef4c80c99db94d985c9b5679/ortools/sat/doc/integer_arithmetic.md
• https://or-tools.github.io/docs/javadoc/index.html Look for com.google.ortools.sat.CpModel

Set up local (Mac): (1) JDK and export JDK_HOME (or let "jenv" do it) export JAVA_HOME=/Library/Java/JavaVirtualMachines/openjdk.jdk

(2) OR Tools binaries TODO: Confirm if this is necessary; or will maven do this for us? https://developers.google.com/optimization/install/java

(3) Maven

brew install maven

mvn -v

(4) Versions installed:

https://search.maven.org/artifact/com.google.ortools/ortools-java/

! clj

(! s)

Given a string variable, return the negated equivalent

add-multiplication-factors! clj

(add-multiplication-factors! model domain-map string-factors)

Adds all the factors using .addMultiplicationEquality and creating tmp vars as needed.

apply-modifier clj multimethod

Applies a constraint modifier to an OR-Tools constraint object. Dispatches on the modifier keyword (e.g. :only-if).

as-2d-int-array clj

(as-2d-int-array tuples)

Converts a seq of seqs into a Java Object[] of int[], for use with OR-Tools tuple constraints.

divide-seq-by clj

(divide-seq-by pred sequence)

Split a sequence into multiple sequences, starting a new one each time (pred item) is truthy. The item is included in the new seq.

domain clj

(domain & [v0 :as values])

Creates an OR-Tools Domain from a seq of integer values. Accepts either a flat sequence of integers or a single collection.

domain-vs-equations-inbalance? clj

(domain-vs-equations-inbalance? collation)

(domain-vs-equations-inbalance? domain equations assumptions)

Returns a map of {:unused-domain … :missing-domain …} if there are variables present in the domain but absent from equations, or vice versa. Returns nil when balanced. Unconstrained variables slow the solver significantly.

eop-< clj

(eop-< model linarg lin-long-arg x y & [z])

Adds a strictly-less-than constraint to model. With two polynomial args (x, y): x < y. With three args (x, y, z): x < y < z (strict range constraint).

eop-<= clj

(eop-<= model linarg lin-long-arg x y & [z])

Adds a less-than-or-equal constraint to model. With two polynomial args (x, y): x <= y. With three args (x, y, z): x <= y <= z (range constraint).

eq-grammar clj

eval-in-domain clj

(eval-in-domain domain-map key)

Looks up key in domain-map, returning its OR-Tools IntVar/BoolVar. Numbers are returned as longs. Throws with variable name suggestions if a string key is not found.

int-var-arg clj

(int-var-arg domain-map polynomial)

Extracts a single OR-Tools variable from a single-element polynomial. Use for operators that require a bare IntVar rather than a LinearArgument.

load-native clj

long-arg clj

(long-arg polynomial)

Extracts a single long value from a single-element polynomial.

lvar? clj

(lvar? x)

Returns true if x is an OR-Tools integer variable (IntVar or BoolVar).

math-ceil clj

mk-domain-map clj

(mk-domain-map model m)

Given a model and a domain spec, create the domain variables in the model and return a same-shaped map of Vars. A domain spec looks like this, for example: {"x" [:range 0 20] "y" [:boolean] "z" [9 10 11 12 13]} In the :range case, the second value is inclusive.

mk-solutions-callback clj

(mk-solutions-callback state-ref
                       int-vars
                       {:keys [name-value] :or {name-value true} :as options})

Creates an OR-Tools CpSolverSolutionCallback that records each solution into state-ref. int-vars is the domain-map of solver variables. Each solution's :values entry mirrors the structure of int-vars with each variable replaced by [name value] when the :name-value option is true (default), or by a raw long value otherwise.

named? clj

(named? x)

Returns true if x is a String or implements clojure.lang.Named (keyword or symbol).

negative-term clj

(negative-term t1)

(negative-term t1 t2)

(negative-term n1 t1 t2)

Negates a polynomial term by multiplying its leading numeric coefficient by -1. Handles 1-, 2-, and 3-element term vectors.

nil-or-blank? clj

(nil-or-blank? s)

Returns true if s is nil or a blank string. Unlike string/blank?, returns false (rather than throwing) for non-string values.

parse-equations clj

(parse-equations & args)

Parses one or more equation strings (e.g. "r + p = 20") into the internal polynomial equation format. Multiple strings are joined with newlines before parsing.

solve! clj

(solve! solver-wrapper model)

Runs the CP-SAT solver against model, collecting solutions via the callback in solver-wrapper. Ensure @load-native has been realized before calling this directly.

solve-equations clj

(solve-equations domain
                 equations
                 &
                 [{[objective-instruction objective-varname] :objective
                   :keys [model-fn retain-temp? limit assumptions
                          check-inbalance? load-native? export-pb-to-file]
                   :or {check-inbalance? true load-native? true}
                   :as options}])

Solve the set of equations and return all/some solutions. domain is a Map of variables names to domains. E.g. {"x" [:range 0 20] "y" [:range 0 20] "z" [9 10 11 12 13]

;; Tuple constraint: key is a vector of variable names, value is [:tuples <allowed-assignments>] ;; where <allowed-assignments> is a seq of integer vectors, each the same length as the key. ;; Constrains the named variables to only take on the listed combinations of values ;; (uses OR-Tools addAllowedAssignments). E.g.: ;; {["a" "b"] [:tuples [[1 2] [3 4] [5 6]]]} ;; means (a=1,b=2) or (a=3,b=4) or (a=5,b=6) are the only allowed assignments. } equations are of the form: eq = [operator left right] operator = (= | < | > | != | <= | etc) left = polynomial right = polynomial polynomial = [term+] term = varname | integer | [integer varname] | [integer varname varname]

options In addition to the options defined in this fn signature, options is also passed to solver-with-callback.

solver-with-callback clj

(solver-with-callback vars
                      {:keys [timeout relative-gap-limit num-workers
                              enumerate-all]
                       :or {timeout 20.0 num-workers 0}
                       :as options})

Creates and configures a CP-SAT solver and solution callback. Returns a SolverWrapper. Options:

• :timeout — max seconds to run (default 20.0)
• :num-workers — number of parallel workers; omit or pass 0 to use OR-Tools default (all cores)
• :relative-gap-limit — stop within this fraction of optimal
• :enumerate-all — collect all solutions (not supported with multiple workers)

strip-temp-vars clj

(strip-temp-vars x)

Remove map entries where the key starts with "TEMP.". Works on a map or a seq of maps.

submit-equations clj

(submit-equations model domain-map equations)

Processes equations data structure. For example: (["=" ([2 "x"] [4 "y"]) ([124])] ; 2x + 4y = 124 ["<" ([1 "y"]) ([4])] ["<" ([1 "x"] [1 "y"]) ([40])] )

I.e. multiplication and addition/subtraction are implicit with "="/.

the-parser clj

validate-rest-strings! clj

(validate-rest-strings! term)

Throws if any element after the first in term is not a String. Used to validate multi-factor multiplication terms like [3 "x" "y"].

var-name-from clj