chiark / gitweb /
wip lp notes before condense
authorIan Jackson <ijackson@chiark.greenend.org.uk>
Fri, 7 Mar 2014 13:44:10 +0000 (13:44 +0000)
committerIan Jackson <ijackson@chiark.greenend.org.uk>
Fri, 7 Mar 2014 13:44:10 +0000 (13:44 +0000)
main.c

diff --git a/main.c b/main.c
index fa5c7db..6465f9b 100644 (file)
--- a/main.c
+++ b/main.c
@@ -38,6 +38,25 @@ static void optimise(void) {
     }
   }
 
+  /*
+   * We formulate our problem as an LP problem as follows.
+   * In this file "n" and "m" are the matchstick numbers.
+   *
+   * Each set bit in the adjacency matrix corresponds to taking a
+   * fragment from old match i and making it part of new match j.
+   *
+   * The structural variables (columns) are:
+   *   x_fragsz_i_j    the size of that fragment
+   *   x_minimum       minimum size of any fragment
+   *
+   * The auxiliary variables (rows, constraints) are:
+   *   x_total_i       total length for each input match (fixed variable)
+   *   x_total_j       total length for each output match (fixed variable)
+   *   x_fragmin_i_j   amount by which fragment is > minimum (lower bound 0)
+   *
+   * The objective function is simply to maximise x_minimum
+   */
+
   printf("nyi\n");
 }