a branch and bound for MIP problems

Merge branch 'master' of git.sr.ht:~lucasemmoreira/branch-and-bound

add: colored readme

fix: allow only feasible solution in pruning for quality

- read-only
- https://git.sr.ht/~lucasemmoreira/branch-and-bound
- read/write
- git@git.sr.ht:~lucasemmoreira/branch-and-bound

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 1a_{0,0} + 2a_{0,1} + 3a_{1,0} + 4a_{1,1}

s.t. a_{0,0} + a_{0,1} <= 1

a_{1,0} + a_{1,1} <= 1

a_{0,0} + a_{1,0} = 1

a_{0,1} + a_{1,1} = 1

a_{0,0}, a_{0,1}, a_{1,0}, a_{1,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]])
```