c

29 files changed, 558 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..ce56a81
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+_build/
+*jpg
+.ipynb_checkpoints
diff --git a/.ocamlformat b/.ocamlformat
new file mode 100644
index 0000000..aa5495a
--- /dev/null
+++ b/.ocamlformat
@@ -0,0 +1,2 @@
+profile = janestreet
+version = 0.26.1
\ No newline at end of file
diff --git a/algorithms/algorithms_lib.ml b/algorithms/algorithms_lib.ml
new file mode 100644
index 0000000..7eab223
--- /dev/null
+++ b/algorithms/algorithms_lib.ml
@@ -0,0 +1 @@
+module Simulated_annealing = Simulated_annealing
diff --git a/algorithms/dune b/algorithms/dune
new file mode 100644
index 0000000..c8d1ff3
--- /dev/null
+++ b/algorithms/dune
@@ -0,0 +1,6 @@
+(library
+ (inline_tests)
+ (name algorithms_lib)
+ (libraries core owl common_lib)
+ (preprocess
+  (pps ppx_inline_test ppx_jane)))
diff --git a/algorithms/pbil.ml b/algorithms/pbil.ml
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/algorithms/pbil.ml
diff --git a/algorithms/pbil.mli b/algorithms/pbil.mli
new file mode 100644
index 0000000..5260232
--- /dev/null
+++ b/algorithms/pbil.mli
@@ -0,0 +1,18 @@
+open! Core
+
+module Gene : sig
+  type t = float array
+end
+
+module Input : sig
+  type t =
+    { population_size : int64
+    ; evaluate_individual : Gene.t -> int64
+    ; termination_condition : Gene.t list -> iteration:int64 -> bool
+    }
+  [@@deriving sexp_of]
+end
+
+module Output : sig
+  type t = { distribution : float array }
+end
diff --git a/algorithms/simulated_annealing.ml b/algorithms/simulated_annealing.ml
new file mode 100644
index 0000000..8efb714
--- /dev/null
+++ b/algorithms/simulated_annealing.ml
@@ -0,0 +1,56 @@
+open! Core
+open Owl
+open Common_lib
+
+type 'a input =
+  { trials : int
+  ; radius : int
+  ; alpha : float
+  ; objective_function : 'a -> int64
+  ; initialize_sample : unit -> 'a
+  ; random_neighbour : 'a -> radius:int -> 'a
+  }
+[@@deriving sexp_of]
+
+type 'a result =
+  { costs : int64 array
+  ; time : Time_ns.Span.t
+  ; best_sample : 'a
+  }
+[@@deriving sexp_of]
+
+let anneal_function ~time ~trials ~cost ~new_cost ~alpha =
+  Maths.exp
+    Float.(-alpha * (of_int64 new_cost - of_int64 cost) * of_int time / of_int trials)
+;;
+
+let maybe_anneal ~time ~trials ~cost ~new_cost ~alpha =
+  let rand = Stats.uniform_rvs ~a:0. ~b:1. in
+  Float.(rand < anneal_function ~time ~trials ~cost ~new_cost ~alpha)
+;;
+
+let simulated_annealing
+  { trials; radius; alpha; objective_function; initialize_sample; random_neighbour }
+  =
+  Log.info_s
+    [%message "Simulated annealing" (trials : int) (radius : int) (alpha : float)];
+  let t0 = Time_ns.now () in
+  let sample = ref (initialize_sample ()) in
+  let cost = ref (objective_function !sample) in
+  let costs =
+    Array.init trials ~f:(fun time ->
+      let new_sample = random_neighbour !sample ~radius in
+      let new_cost = objective_function new_sample in
+      if Int64.(new_cost <= !cost)
+      then (
+        cost := new_cost;
+        sample := new_sample)
+      else if maybe_anneal ~time ~trials ~cost:!cost ~new_cost ~alpha
+      then (
+        cost := new_cost;
+        sample := new_sample);
+      !cost)
+  in
+  let t1 = Time_ns.now () in
+  { time = Time_ns.diff t1 t0; costs; best_sample = !sample }
+;;
diff --git a/algorithms/simulated_annealing.mli b/algorithms/simulated_annealing.mli
new file mode 100644
index 0000000..6cc709d
--- /dev/null
+++ b/algorithms/simulated_annealing.mli
@@ -0,0 +1,20 @@
+open! Core
+
+type 'a input =
+  { trials : int
+  ; radius : int
+  ; alpha : float
+  ; objective_function : 'a -> int64
+  ; initialize_sample : unit -> 'a
+  ; random_neighbour : 'a -> radius:int -> 'a
+  }
+[@@deriving sexp_of]
+
+type 'a result =
+  { costs : int64 array
+  ; time : Time_ns.Span.t
+  ; best_sample : 'a
+  }
+[@@deriving sexp_of]
+
+val simulated_annealing : 'a input -> 'a result
diff --git a/common/common_lib.ml b/common/common_lib.ml
new file mode 100644
index 0000000..ac026a5
--- /dev/null
+++ b/common/common_lib.ml
@@ -0,0 +1,4 @@
+module Permutation = Permutation
+module Curl_helper = Curl_helper
+module Plotting = Plotting
+module Log = Log
diff --git a/common/curl_helper.ml b/common/curl_helper.ml
new file mode 100644
index 0000000..730eaf8
--- /dev/null
+++ b/common/curl_helper.ml
@@ -0,0 +1,21 @@
+open! Core
+
+let fetch url f =
+  let c = Curl.init () in
+  Curl.set_url c url;
+  Curl.set_followlocation c true;
+  Curl.set_writefunction c f;
+  Curl.perform c;
+  Curl.cleanup c
+;;
+
+let get ~url =
+  Or_error.try_with (fun () ->
+    let buf = Buffer.create 16 in
+    fetch url (fun s ->
+      Buffer.add_string buf s;
+      String.length s);
+    Buffer.contents buf)
+;;
+
+let get_exn ~url = get ~url |> Or_error.ok_exn
diff --git a/common/curl_helper.mli b/common/curl_helper.mli
new file mode 100644
index 0000000..6ed67f1
--- /dev/null
+++ b/common/curl_helper.mli
@@ -0,0 +1,6 @@
+open! Core
+
+(** Sends a HTTP request and returns the result payload as string. *)
+val get : url:string -> string Or_error.t
+
+val get_exn : url:string -> string
diff --git a/common/dune b/common/dune
new file mode 100644
index 0000000..e7273d4
--- /dev/null
+++ b/common/dune
@@ -0,0 +1,6 @@
+(library
+ (inline_tests)
+ (name common_lib)
+ (libraries core owl owl-plplot curl)
+ (preprocess
+  (pps ppx_inline_test ppx_jane)))
diff --git a/common/gene.ml b/common/gene.ml
new file mode 100644
index 0000000..3ad2609
--- /dev/null
+++ b/common/gene.ml
@@ -0,0 +1 @@
+open! Core
diff --git a/common/gene.mli b/common/gene.mli
new file mode 100644
index 0000000..7f14c08
--- /dev/null
+++ b/common/gene.mli
@@ -0,0 +1,3 @@
+open! Core
+
+type t = float array [@@deriving sexp]
diff --git a/common/log.ml b/common/log.ml
new file mode 100644
index 0000000..2992378
--- /dev/null
+++ b/common/log.ml
@@ -0,0 +1,51 @@
+open! Core
+
+module Level = struct
+  type t =
+    | Debug
+    | Info
+    | Error
+  [@@deriving sexp]
+
+  let of_string str = Sexp.of_string str |> t_of_sexp
+  let to_string t = sexp_of_t t |> Sexp.to_string
+end
+
+type t = { mutable level : Level.t }
+
+let log = { level = Info }
+let set_level level = log.level <- level
+
+let set_level_via_param_helper ~f =
+  let open Command.Param in
+  map
+    (flag
+       "log-level"
+       (optional (Arg_type.create Level.of_string))
+       ~doc:"LEVEL The log level")
+    ~f:(Option.iter ~f)
+;;
+
+let set_level_via_param () = set_level_via_param_helper ~f:set_level
+
+let has_level level =
+  match level, log.level with
+  | Level.Debug, _ -> true
+  | _, Level.Debug -> false
+  | Info, _ -> true
+  | _, Info -> false
+  | Error, _ -> true
+;;
+
+let log_s level sexp =
+  if has_level level
+  then (
+    let ts = Time_ns.now () in
+    print_endline
+      [%string
+        "[%{Time_ns.to_string_utc ts} %{level#Level}] -- %{Sexp.to_string_hum sexp}"])
+;;
+
+let debug_s = log_s Debug
+let info_s = log_s Info
+let error_s = log_s Error
diff --git a/common/log.mli b/common/log.mli
new file mode 100644
index 0000000..50230bf
--- /dev/null
+++ b/common/log.mli
@@ -0,0 +1,14 @@
+open! Core
+
+module Level : sig
+  type t =
+    | Debug
+    | Info
+    | Error
+end
+
+val set_level : Level.t -> unit
+val set_level_via_param : unit -> unit Command.Param.t
+val debug_s : Sexp.t -> unit
+val info_s : Sexp.t -> unit
+val error_s : Sexp.t -> unit
diff --git a/common/permutation.ml b/common/permutation.ml
new file mode 100644
index 0000000..d74ae33
--- /dev/null
+++ b/common/permutation.ml
@@ -0,0 +1,26 @@
+open! Core
+open Owl
+
+type t = int array [@@deriving sexp_of]
+
+let create lst =
+  let sorted = List.sort lst ~compare:Int.compare in
+  if List.for_alli sorted ~f:(fun i elt -> i = elt)
+  then Ok (Array.of_list lst)
+  else Or_error.error_s [%message "Cannot create a permutation" (lst : int list)]
+;;
+
+let length = Array.length
+let get_unsafe = Array.unsafe_get
+let id n = create (List.init n ~f:Fn.id) |> Or_error.ok_exn
+let shuffle t = Stats.shuffle t
+
+let random_neighbour t ~radius =
+  let l = length t in
+  let random_idx () = Stats.uniform_int_rvs ~a:0 ~b:(l - 1) in
+  let transitions = List.init radius ~f:(fun _ -> random_idx (), random_idx ()) in
+  let new_t = Array.copy t in
+  List.fold transitions ~init:new_t ~f:(fun t (i, j) ->
+    Array.swap t i j;
+    t)
+;;
diff --git a/common/permutation.mli b/common/permutation.mli
new file mode 100644
index 0000000..b076d9f
--- /dev/null
+++ b/common/permutation.mli
@@ -0,0 +1,13 @@
+open! Core
+
+(** Permutation of numbers 0...n-1 *)
+type t [@@deriving sexp_of]
+
+val create : int list -> t Or_error.t
+val length : t -> int
+val get_unsafe : t -> int -> int
+val id : int -> t
+val shuffle : t -> t
+
+(** Performs [radius] random transpositions on t. *)
+val random_neighbour : t -> radius:int -> t
diff --git a/common/plotting.ml b/common/plotting.ml
new file mode 100644
index 0000000..d4a8af3
--- /dev/null
+++ b/common/plotting.ml
@@ -0,0 +1,72 @@
+open! Core
+open Owl_plplot
+
+let initialize_plot
+  ?(xlabel = "values")
+  ?(ylabel = "")
+  ?(font_size = 8.)
+  ?(pen_size = 1.)
+  ~name
+  ()
+  =
+  let h = Plot.create [%string "%{name}.jpg"] in
+  Plot.set_xlabel h xlabel;
+  Plot.set_ylabel h ylabel;
+  Plot.set_font_size h font_size;
+  Plot.set_pen_size h pen_size;
+  h
+;;
+
+let simple_plot_floats
+  ?xlabel
+  ?ylabel
+  ?font_size
+  ?pen_size
+  ?(spec = [ Plot.RGB (255, 0, 50) ])
+  ~name
+  values
+  =
+  Log.info_s [%message "Plotting" name];
+  let h = initialize_plot ?xlabel ?ylabel ?font_size ?pen_size ~name () in
+  let length = Array.length values in
+  let indices = Array.init length ~f:Float.of_int in
+  Plot.plot
+    ~h
+    ~spec
+    (Owl_dense_matrix.D.of_array indices 1 length)
+    (Owl_dense_matrix.D.of_array values 1 length);
+  Plot.output h
+;;
+
+let simple_plot_int64 ?xlabel ?ylabel ?font_size ?pen_size ?spec ~name values =
+  simple_plot_floats
+    ?xlabel
+    ?ylabel
+    ?font_size
+    ?pen_size
+    ?spec
+    ~name
+    (Array.map values ~f:Float.of_int64)
+;;
+
+let histogram_int64
+  ?xlabel
+  ?ylabel
+  ?font_size
+  ?pen_size
+  ?(bin = 100)
+  ?(spec = [ Plot.RGB (255, 0, 50) ])
+  ~name
+  values
+  =
+  let h = initialize_plot ?xlabel ?ylabel ?font_size ?pen_size ~name () in
+  Plot.histogram
+    ~h
+    ~bin
+    ~spec
+    (Owl_dense_matrix.D.of_array
+       (Array.map ~f:Int64.to_float values)
+       1
+       (Array.length values));
+  Plot.output h
+;;
diff --git a/common/plotting.mli b/common/plotting.mli
new file mode 100644
index 0000000..8af5afa
--- /dev/null
+++ b/common/plotting.mli
@@ -0,0 +1,33 @@
+open! Core
+open Owl_plplot
+
+val simple_plot_floats
+  :  ?xlabel:string
+  -> ?ylabel:string
+  -> ?font_size:float
+  -> ?pen_size:float
+  -> ?spec:Plot.spec list
+  -> name:string
+  -> float array
+  -> unit
+
+val simple_plot_int64
+  :  ?xlabel:string
+  -> ?ylabel:string
+  -> ?font_size:float
+  -> ?pen_size:float
+  -> ?spec:Plot.spec list
+  -> name:string
+  -> int64 array
+  -> unit
+
+val histogram_int64
+  :  ?xlabel:string
+  -> ?ylabel:string
+  -> ?font_size:float
+  -> ?pen_size:float
+  -> ?bin:int
+  -> ?spec:Plot.spec list
+  -> name:string
+  -> int64 array
+  -> unit
diff --git a/dune-project b/dune-project
new file mode 100644
index 0000000..5bfde7a
--- /dev/null
+++ b/dune-project
@@ -0,0 +1,21 @@
+(lang dune 3.10)
+
+(name evo_algs)
+
+(generate_opam_files false)
+
+(source
+ (github korbiniak/evo_algs))
+
+(authors "Franciszek Malinka")
+
+(license MIT)
+
+(package
+ (name evo_algs)
+ (synopsis "Code for evolutionary algorithms course")
+ (description "Code for evolutionary algorithms course")
+ (depends ocaml dune)
+ (tags (evolutionary)))
+
+; See the complete stanza docs at https://dune.readthedocs.io/en/stable/dune-files.html#dune-project
diff --git a/qap/bin/dune b/qap/bin/dune
new file mode 100644
index 0000000..0710a9e
--- /dev/null
+++ b/qap/bin/dune
@@ -0,0 +1,6 @@
+(executable
+ (public_name qap)
+ (name qap)
+ (libraries core core_unix.command_unix qap_lib)
+ (preprocess
+  (pps ppx_jane)))
diff --git a/qap/bin/qap.ml b/qap/bin/qap.ml
new file mode 100644
index 0000000..1e0dfde
--- /dev/null
+++ b/qap/bin/qap.ml
@@ -0,0 +1,3 @@
+open! Core
+
+let () = Command_unix.run Qap_lib.Main.command
diff --git a/qap/src/dune b/qap/src/dune
new file mode 100644
index 0000000..a7bfdff
--- /dev/null
+++ b/qap/src/dune
@@ -0,0 +1,6 @@
+(library
+ (inline_tests)
+ (name qap_lib)
+ (libraries async core owl owl-plplot curl common_lib algorithms_lib)
+ (preprocess
+  (pps ppx_inline_test ppx_jane)))
diff --git a/qap/src/main.ml b/qap/src/main.ml
new file mode 100644
index 0000000..b7e2939
--- /dev/null
+++ b/qap/src/main.ml
@@ -0,0 +1,31 @@
+open! Core
+
+let simulated_annealing_command =
+  Command.basic_or_error
+    ~summary:"simulated annealing"
+    (let%map_open.Command () = Common_lib.Log.set_level_via_param ()
+     and n = flag "n" (required int) ~doc:"INT Qap instance size"
+     and trials = flag "trials" (required int) ~doc:"INT number of trials"
+     and radius = flag "radius" (required int) ~doc:"INT radius"
+     and alpha = flag "alpha" (required float) ~doc:"FLOAT alpha" in
+     fun () -> Qap.simulated_annealing ~n ~trials ~radius ~alpha |> Or_error.return)
+;;
+
+let random_sampling_command =
+  Command.basic_or_error
+    ~summary:"random sampling"
+    (let%map_open.Command () = Common_lib.Log.set_level_via_param ()
+     and n = flag "n" (required int) ~doc:"INT Qap instance size"
+     and trials = flag "trials" (required int) ~doc:"INT number of trials" in
+     fun () ->
+       Qap.random_sampling ~n ~trials |> ignore;
+       Ok ())
+;;
+
+let command =
+  Command.group
+    ~summary:"QAP solutions"
+    [ "simulated-annealing", simulated_annealing_command
+    ; "random-sampling", random_sampling_command
+    ]
+;;
diff --git a/qap/src/main.mli b/qap/src/main.mli
new file mode 100644
index 0000000..780124b
--- /dev/null
+++ b/qap/src/main.mli
@@ -0,0 +1,3 @@
+open! Core
+
+val command : Command.t
diff --git a/qap/src/qap.ml b/qap/src/qap.ml
new file mode 100644
index 0000000..719f8d9
--- /dev/null
+++ b/qap/src/qap.ml
@@ -0,0 +1,117 @@
+open! Core
+open Common_lib
+module Matrix = Owl_dense_matrix.Generic
+
+(* # Popularne instancje QAP wraz z dokładnym minimum funkcji celu *)
+(*    Nug12   12    578 (OPT)    (12,7,9,3,4,8,11,1,5,6,10,2)                  *)
+(*    Nug14   14   1014 (OPT)    (9,8,13,2,1,11,7,14,3,4,12,5,6,10)             *)
+(*    Nug15   15   1150 (OPT)    (1,2,13,8,9,4,3,14,7,11,10,15,6,5,12)           *)
+(*    Nug16a  16   1610 (OPT)    (9,14,2,15,16,3,10,12,8,11,6,5,7,1,4,13)       *)
+(*    Nug16b  16   1240 (OPT)    (16,12,13,8,4,2,9,11,15,10,7,3,14,6,1,5)        *)
+(*    Nug17   17   1732 (OPT)    (16,15,2,14,9,11,8,12,10,3,4,1,7,6,13,17,5)        *)
+(*    Nug18   18   1930 (OPT)    (10,3,14,2,18,6,7,12,15,4,5,1,11,8,17,13,9,16)      *)
+(*    Nug20   20   2570 (OPT)    (18,14,10,3,9,4,2,12,11,16,19,15,20,8,13,17,5,7,1,6) *)
+(*    Nug21   21   2438 (OPT)    (4,21,3,9,13,2,5,14,18,11,16,10,6,15,20,19,8,7,1,12,17) *)
+(*    Nug22   22   3596 (OPT)    (2,21,9,10,7,3,1,19,8,20,17,5,13,6,12,16,11,22,18,14,15) *)
+(*    Nug24   24   3488 (OPT)    (17,8,11,23,4,20,15,19,22,18,3,14,1,10,7,9,16,21,24,12,6,13,5,2) *)
+(*    Nug25   25   3744 (OPT)    (5,11,20,15,22,2,25,8,9,1,18,16,3,6,19,24,21,14,7,10,17,12,4,23,13) *)
+(* *  Nug27   27   5234 (OPT)    (23,18,3,1,27,17,5,12,7,15,4,26,8,19,20,2,24,21,14,10,9,13,22,25,6,16,11) *)
+(* *  Nug28   28   5166 (OPT)    (18,21,9,1,28,20,11,3,13,12,10,19,14,22,15,2,25,16,4,23,7,17,24,26,5,27,8,6) *)
+(* *  Nug30   30   6124 (OPT)    (5 12 6 13 2 21 26 24 10 9 29 28 17 1 8 7 19 25 23 22 11 16 30 4 15 18 27 3 14 20) *)
+
+let nug_x_instance_url x = [%string "https://qaplib.mgi.polymtl.ca/data.d/nug%{x}.dat"]
+let one_dim_matrix kind array = Matrix.of_array kind array 1 (Array.length array)
+
+type t =
+  { size : int
+  ; dists : (int64, Bigarray.int64_elt) Matrix.t
+  ; flows : (int64, Bigarray.int64_elt) Matrix.t
+  }
+
+let create ~url =
+  Log.info_s [%message "Downloading QAP instance" url];
+  let%map.Or_error data = Common_lib.Curl_helper.get ~url in
+  Log.info_s [%message "Downloaded QAP instance"];
+  let lines = String.split_lines data in
+  let size = List.hd_exn lines |> Int.of_string in
+  let lines = List.tl_exn lines |> List.tl_exn in
+  let values =
+    List.concat_map lines ~f:(fun row ->
+      row
+      |> String.split ~on:' '
+      |> List.filter_map ~f:(function
+        | "" -> None
+        | value -> Some (Int64.of_string value)))
+  in
+  let flows, distances = List.split_n values (size * size) in
+  { size
+  ; flows = Matrix.of_array Bigarray.Int64 (Array.of_list flows) size size
+  ; dists = Matrix.of_array Bigarray.Int64 (Array.of_list distances) size size
+  }
+;;
+
+let create_exn ~url = create ~url |> Or_error.ok_exn
+
+let objective_function_exn { size; dists; flows } perm =
+  assert (Permutation.length perm = size);
+  let compute_row i row =
+    let pi = Permutation.get_unsafe perm i in
+    Matrix.mapi
+      (fun j flow ->
+        let pj = Permutation.get_unsafe perm j in
+        Int64.(flow * Matrix.get dists pi pj))
+      row
+    |> Matrix.sum'
+  in
+  let row_values = Matrix.mapi_rows compute_row flows in
+  Matrix.sum' (one_dim_matrix Bigarray.Int64 row_values)
+;;
+
+let print t =
+  print_endline [%string "Size: %{t.size#Int}"];
+  Matrix.print t.flows;
+  Matrix.print t.dists
+;;
+
+let random_sampling ~n ~trials =
+  let qap_n = create_exn ~url:(nug_x_instance_url (Int.to_string n)) in
+  print qap_n;
+  let t0 = Time_ns.now () in
+  let perm = Permutation.id n in
+  let costs = Array.create ~len:trials Int64.zero in
+  let perm = Permutation.shuffle perm in
+  for i = 0 to trials - 1 do
+    let perm = Permutation.shuffle perm in
+    costs.(i) <- objective_function_exn qap_n perm
+  done;
+  let t1 = Time_ns.now () in
+  print_endline [%string "Elapsed time: %{Time_ns.diff t1 t0#Time_ns.Span}"];
+  Plotting.histogram_int64
+    ~pen_size:3.
+    ~bin:100
+    ~name:[%string "qap_random_sampling_%{n#Int}_trials_%{trials#Int}"]
+    costs;
+  costs
+;;
+
+let simulated_annealing ~n ~trials ~radius ~alpha =
+  let qap_n = create_exn ~url:(nug_x_instance_url (Int.to_string n)) in
+  let objective_function = objective_function_exn qap_n
+  and initialize_sample () = Permutation.id n |> Permutation.shuffle
+  and random_neighbour = Permutation.random_neighbour in
+  let result =
+    Algorithms_lib.Simulated_annealing.simulated_annealing
+      { trials; radius; alpha; objective_function; initialize_sample; random_neighbour }
+  in
+  Plotting.simple_plot_int64
+    ~name:
+      [%string
+        "qap_simulated_annealing_%{n#Int}_trials_%{trials#Int}_alpha_%{alpha#Float}_radius_%{radius#Int}"]
+    result.costs;
+  Log.info_s
+    [%message
+      (Array.min_elt result.costs ~compare:Int64.compare : Int64.t option)
+        (Matrix.mean' (one_dim_matrix Bigarray.Int64 result.costs) : Int64.t)];
+  Log.info_s [%message "Elapsed time" (result.time : Time_ns.Span.t)];
+  Log.info_s [%message "Result" (result.best_sample : Permutation.t)]
+;;
diff --git a/qap/src/qap.mli b/qap/src/qap.mli
new file mode 100644
index 0000000..48f26a5
--- /dev/null
+++ b/qap/src/qap.mli
@@ -0,0 +1,14 @@
+open! Core
+open Common_lib
+
+type t
+
+val create_exn : url:string -> t
+val create : url:string -> t Or_error.t
+
+(** Throws if [perm] length is not consistent with [t]. *)
+val objective_function_exn : t -> Permutation.t -> int64
+
+val print : t -> unit
+val random_sampling : n:int -> trials:int -> int64 array
+val simulated_annealing : n:int -> trials:int -> radius:int -> alpha:float -> unit
diff --git a/qap/src/qap_lib.ml b/qap/src/qap_lib.ml
new file mode 100644
index 0000000..a5a59ad
--- /dev/null
+++ b/qap/src/qap_lib.ml
@@ -0,0 +1 @@
+module Main = Main