a branch and bound for MIP problems
Merge branch 'master' of git.sr.ht:~lucasemmoreira/branch-and-bound
fix: allow only feasible solution in pruning for quality


browse  log 



You can also use your local clone with git send-email.

#What is this?

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.

#How to use it?

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
	 (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
	 (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 
	 (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]])