Merge branch 'master' of git.sr.ht:~lucasemmoreira/branch-and-bound
add: colored readme
fix: allow only feasible solution in pruning for quality
Well, this is my attempt to create a branch and bound for integer programming. Since I will be improving this as necessary, it is what one may call an eternal work in progress.
It kind of baffled me that, by the time of this writing, there is no solid optimization package for mixed integer programming in clojure. I needed a simple branch and bound to solve small problem, then a after a few days bnb-clj was born.
Well, this is an issue. You see, there are probably a ton of good ways to create a model interface for MIP, however it was not my focus at the moment. So to use it, looks more like coding than math modelling.
I will drop here my first test with it. The model was:
max 1a0,0 + 2a0,1 + 3a1,0 + 4a1,1
s.t. a0,0 + a0,1 <= 1
a1,0 + a1,1 <= 1
a0,0 + a1,0 = 1
a0,1 + a1,1 = 1
a0,0, a0,1, a1,0, a1,1 binaries
In the test/branch_and_bound/core_test.clj all this code is written and ready to go =].
First importing.
(require '[prolin.protocols :as pp]
'[branch-and-bound.core :refer :all])
An auxiliary fn to create the names for the model
(defn var-name
[name row col]
(keyword (str name row "_" col)))
Some constraints. After each constraint I put a call to see how it would be done.
(defn binary-vars
[constraints name [rows cols]]
(apply clojure.set/union
constraints
(for [row rows]
(apply clojure.set/union (map #(binary-constraint (var-name name row %)) cols)))))
(binary-vars #{} "x" [(range 2) (range 2)])
(defn once-in-line
[constraints name [rows cols]]
(apply clojure.set/union
constraints
(for [row rows]
#{(pp/constraint '<= (pp/linear-polynomial -1 (zipmap (map #(var-name name row %) cols) (repeat 1))))})))
(once-in-line #{} "x" [(range 2) (range 2)])
(defn once-in-col
[constraints name [rows cols] capacity]
(apply clojure.set/union
constraints
(for [col cols]
#{(pp/constraint '<= (pp/linear-polynomial (* -1 (nth capacity col)) (zipmap (map #(var-name name % col) rows) (repeat 1))))})))
(once-in-col #{} "x" [(range 2) (range 2)] [2 3])
The objective function. Again, at the end an example on how to call it.
(defn objective-fn
[name [rows cols] coefficients]
(apply merge
(for [row rows]
(apply merge (map #(hash-map (var-name name row %) (nth (nth coefficients row) %)) cols)))))
(objective-fn "x" [(range 2) (range 2)] '((1 2) (3 4)))
A simple estructure to contain the constraints and the objective function.
(defn full-model [var-name dim capacity coeff]
{:constraints (-> #{}
(binary-vars var-name dim)
(once-in-line var-name dim)
(once-in-col var-name dim capacity))
:obj-fn (objective-fn var-name dim coeff)})
(full-model "x" [(range 2) (range 2)] [2 3] [[1 2] [3 4]])
Finally, how to solve the model.
(defn find-solution [capacity margin-matrix]
(let [dim [(range (count margin-matrix)) (range (count (first margin-matrix)))]
{:keys [constraints obj-fn]} (full-model "x" dim capacity margin-matrix)]
(solve-model! (model! constraints obj-fn (keys obj-fn)))))
(find-solution [1 2] [[2 1] [3 4]])