fidzu : LISP

Here are the raw download stats for the top 100 projects in Quicklisp for June:

 9081  alexandria
 7797  closer-mop
 7437  split-sequence
 6863  cl-ppcre
 6790  babel
 6498  trivial-features
 6303  iterate
 6222  bordeaux-threads
 6173  anaphora
 6099  trivial-gray-streams
 5522  trivial-garbage
 5367  cffi
 5056  flexi-streams
 4911  nibbles
 4729  let-plus
 4702  usocket
 4592  puri
 4582  cl-base64
 4286  trivial-backtrace
 4181  chipz
 4145  cl+ssl
 4021  cl-fad
 3959  chunga
 3381  drakma
 3292  named-readtables
 3281  ironclad
 3221  more-conditions
 3153  esrap
 3144  local-time
 2928  utilities.print-items
 2587  parse-number
 2439  cl-yacc
 2149  metabang-bind
 2142  cl-unicode
 2131  cl-interpol
 2101  trivial-utf-8
 2084  md5
 2083  fiveam
 2056  asdf-flv
 1930  optima
 1918  lparallel
 1897  log4cl
 1879  slime
 1869  lift
 1854  trivial-indent
 1822  closure-common
 1808  cxml
 1795  array-utils
 1746  plump
 1743  uuid
 1612  bt-semaphore
 1561  trivial-types
 1541  simple-date-time
 1513  cl-clon
 1472  cl-json
 1429  cl-utilities
 1392  architecture.hooks
 1390  quri
 1342  cl-containers
 1340  metatilities-base
 1330  cl-annot
 1319  cl-syntax
 1317  asdf-system-connections
 1291  ieee-floats
 1253  plexippus-xpath
 1113  salza2
 1079  trivial-mimes
 1070  postmodern
 1067  arnesi
 1052  cl-slice
 1050  fare-utils
 1047  fast-io
 1040  static-vectors
 1027  fare-quasiquote
 1015  symbol-munger
 1009  djula
 1007  collectors
 1003  access
  996  gettext
  982  cl-parser-combinators
  980  cl-locale
  925  hunchentoot
  904  cl-sqlite
  896  inferior-shell
  894  fare-mop
  887  prove
  885  rfc2388
  868  cl-log
  865  command-line-arguments
  859  trivia
  858  lisp-namespace
  851  cl-colors
  824  py-configparser
  821  cl-markdown
  821  cl-ansi-text
  821  asdf-finalizers
  820  dynamic-classes
  819  cl-mssql
  818  garbage-pools
  805  cl-abnf

25 Jul 2017 7:13pm GMT

New projects:

• 3bgl-shader - CL-hosted CL-like DSL for generating GLSL - MIT
• cl-forms - A web forms handling library - MIT
• cl-ksuid - K-sortable unique identifiers - GPLv3
• cl-pixman - Low-level pixel manipulation. - LLGPL
• cl-yesql - Common Lisp library for using SQL. - MIT
• easy-routes - Yet another routes handling utility on top of Hunchentoot - MIT
• laap - A Common Lisp multi-threaded event loop. - MIT
• matplotlib-cl - A 2D Plotting library for Common Lisp using Matplotlib. - MIT
• oook - Some magic on the shoulders of CLSQL - MIT
• overlord - Experimental build/module system. - MIT
• semantic-spinneret - A set of Semantic UI components for use with Spinneret - MIT
• with-setf - Macros for setting a place for the duration of a scope - Unlicense
• xlsx - Basic reader for Excel files. - MIT

Updated projects: 3d-vectors, assoc-utils, cepl, cl+ssl, cl-ana, cl-autowrap, cl-dbi, cl-emoji, cl-fluent-logger, cl-fond, cl-hash-util, cl-kanren, cl-mixed, cl-opengl, cl-pdf, cl-rail, cl-random-forest, cl-ssdb, cl-str, cl-typesetting, cl-webdav, clavier, closer-mop, clsql-fluid, coleslaw, croatoan, deeds, dexador, doubly-linked-list, femlisp, flac-parser, fs-utils, gamebox-dgen, gamebox-ecs, gamebox-frame-manager, gamebox-grids, gamebox-math, genie, glkit, harmony, hu.dwim.web-server, hu.dwim.zlib, hunchentoot, infix-math, inquisitor, jsonrpc, kenzo, lack, lake, lichat-protocol, lichat-serverlib, lichat-tcp-server, lichat-ws-server, local-time, maiden, mcclim, mito, mito-auth, ningle, parseq, pgloader, physical-quantities, plump, py-configparser, qlot, ratify, roan, rtg-math, rutils, sanitized-params, serapeum, simple-logger, sketch, spinneret, staple, stumpwm, trivia, websocket-driver, woo.

Removed projects: gtfl, s-dot.

gtfl and s-dot are related projects. The website hosting them has disappeared, and the author has not responded to email queries. So they are not in Quicklisp any more.

To get this update, use (ql:update-dist "quicklisp").

Enjoy!

25 Jul 2017 4:26pm GMT

(please note that I'm assuming a Linux/64 bit platform or VirtualBox image)

Preamble: about a month ago, I was completely void of any android experience.
This is to say: using both QML (which is easy to learn) and Common Lisp (which I assume you already know) to develop android apps is not a difficult task at all, as you'll see.

So, if you are like me just a month ago, there are no excuses not to write your own, first android app using this new "EQL5-Android" project!

We will build a small game (Sokoban), which uses Lisp for the program logic, and QML for the UI, and build an APK for the android platform.

---

Being the author of that very first attempt of integrating Lisp and Qt4 (see lisp-cffi-qt4), what I would like to accomplish is providing you with a ca. 3 MB download, which can be tried out instantly.

10 years ago, the lisp-cffi-qt4.zip (a runnable win32 binary version), was a 3 MB download, including both ECL and Qt4 (UPX compressed, but still).
10 years later, this time on android, what download size is to be expected?
We will see...

---

Since all the documentation needed for preparing the development environment is already covered in the "EQL5-Android" project itself, I will give only the link here:

README-PREPARE.txt

So, I'm assuming that you already have everything installed and set up (Qt 5.7.1, Android NDK 10e, Android SDK, Java JDK, and obviously the EQL5-Android sources from gitlab), in order to build android packages (APK files).

(EQL5 itself, the desktop version, is not strictly needed to follow this example; but for developing your own apps, you will obviously need it; even here it's very helpful for testing and debugging, if something doesn't work as expected.)

If you already know the process of building EQL5 apps for the desktop, you will find that building (cross-compiling) to android is very similar, with only a few more steps involved.

Since we use an example of EQL5-Android itself, everything has already been set up. But I want to remember the steps that are not obvious, if you are not familiar with Qt and EQL:

• you need to add all your external resources, like QML files, PNG files etc. to a Qt resource file (ending .qrc); this will integrate them (compressed) directly into the executable
• you need to add all your Lisp files, in exact order of loading, to make.lisp (in a future version of EQL5, I will try to integrate this step with ASDF)

And that's it, basically (except the app name, which needs to be adapted to the *.qrc file name, to your *.pro file name and contents (see TARGET and RESOURCES), and to the contents of the third script 3-build-apk.sh (see *.json file name).

Everything else will stay the same for every project.

Now I want to call your attention on the huge advantage of using Qt for your android apps: you can first build a desktop exe, with the exact same sources, and try/debug it. If the desktop version works, the android app will generally work too (the only things that may need adaption are e.g. font sizes and similar).

So, let's get practical! In the EQL5-Android sources, switch to 'examples/sokoban/'.

Building a desktop exe would be this 3 liner:

  $ eql5 make-desktop.lisp
  $ qmake sokoban_desktop.pro
  $ make
      

(To test if all resources have really been included in the sokoban_desktop executable, you need to move it to a different directory, and launch it from there.)

Here's a screenshot of our app running on the desktop:

But now let's do the cross-compile dance!

First let's copy the needed shared libraries to the 'android-build/' directory.
Just run script number 1:

  $ ./1-copy-libs.sh
      

This step needs only be done once for every new project. It will copy the cross-compiled ECL and EQL5 libs into our android build directory.

The next steps are very similar to a desktop build:

  $ ecl-android -shell make.lisp
  $ qmake-android sokoban.pro
  $ make
      

---

Since cross-compiling requires a special "host ECL", which needs to match the target platform (that is, 32 bit, no double floats), we would be in trouble with cross-compiling EQL5 code: we certainly don't want a seperate EQL5 32 bit version, only for cross-compiling...

But there is a solution to this (see 'utils/EQL5-symbols.lisp' in sources): for cross-compiling -- which is the job of our "host ECL" -- we pretend to be the eql5 executable, by defining all packages and symbols, defining all EQL5 macros (otherwise we can't compile), and simply defining dummy-functions for all EQL5 functions, so the compiler will not complain.

So, loading 'utils/EQL5-symbols.lisp' in our host ECL will be sufficient for cross-compiling EQL5 code.

If you are interested in how the cross-compile environment is set up, please see:

utils/cross-compile.lisp

(thanks to Sylvain Ageneau, who wrote the original version; this is a simplified version not depending on ASDF; the latter will be integrated in a future version)

---

So, the above 3 liner will build the shared library of our app, ready to be included in the android build. To copy it where the android build expects it, use script number 2:

  $ ./2-install-lib.sh
      

The last step, which will build our APK file, is a verbose one (for eventual debugging), and a little time consuming: it will create the whole package structure, and compile the whole thing into an APK file, ready to be installed on an android device.

There is this great tool (courtesy Qt) called androiddeployqt, which automates the whole and complex process of creating an APK file, with all the needed options already set in our 3rd script:

  $ ./3-build-apk.sh
      

Here the contents of the above script, where you can see all the selected options:

  $ ~/Qt5.7.1/5.7/android_armv7/bin/androiddeployqt \
        --input android-libsokoban.so-deployment-settings.json \
        --output android-build \
        --deployment ministro \
        --gradle \
        --verbose
      

If it will tell you BUILD SUCCESSFUL, then you'll find the APK file (ready for deployment) in 'android-build/build/outputs/apk/'.

The last step is copying over the APK file to your android device, and install / run it. Normally you're not allowed to do this, because it requires special developer settings (please search the web for instructions how to enable them, as they are different for every android version).

After connecting via USB and copying the APK file over to your device, just tap it from there. This will ask for installing, and then for opening the app.

Here's a screenshot of the sokoban app running on a tablet:

Above you see the splash screen, because startup will take a few seconds.

Below the game:

After seeing the result, I'd like to consider a few QML and Lisp snippets.

QML is easy to learn. You just need to declare what you want (and it will do the how behind the scenes).
Let's see this snippet for defining and placing our arrow buttons:

  // container for arrow buttons
  Item {
      id: arrows
      width: up.width * 3
      height: up.height * 3
      anchors.margins: 10
      anchors.right: parent.right
      anchors.verticalCenter: parent.verticalCenter

      Ext.Button {
          id: up
          objectName: "up"
          source: "img/up.png"
          anchors.horizontalCenter: parent.horizontalCenter
      }

      Ext.Button {
          objectName: "left"
          source: "img/left.png"
          anchors.verticalCenter: parent.verticalCenter
      }

      Ext.Button {
          objectName: "right"
          source: "img/right.png"
          anchors.verticalCenter: parent.verticalCenter
          anchors.right: parent.right
      }

      Ext.Button {
          objectName: "down"
          source: "img/down.png"
          anchors.horizontalCenter: parent.horizontalCenter
          anchors.bottom: parent.bottom
      }
  }
      

So, we define an Item as container for the buttons, giving it the width (up.width * 3) and height (up.height * 3), according to the button sizes: this may be any calculation or function call, and may refer to any item of the file, referred to by its id.

For placing the container itself, and the single arrow buttons, we just need to define anchors, which can be relative to other items (here: the parent item).

The Ext.Button is a user defined item class, which can be found in 'qml/ext/Button.qml. That is, the whole directory 'ext/' is imported as Ext:

  import "ext/" as Ext
      

This means that every file in 'ext/' is now a new QML class, which can be referred to via Ext (like a namespace).

The definition of our image button class (see 'qml/ext/Button.qml') is:

  import QtQuick 2.0

  Image {
      signal pressed()

      MouseArea {
          anchors.fill: parent
          onPressed: { parent.pressed() }
      }
  }
      

So, we don't need a real button, but only a clickable image: adding a mouse area will allow us to capture mouse events; this event is then passed to the parent (that is, the Image class), where a Qt signal will be emitted: this will allow us to connect to it from Lisp:

  (defun connect ()
    (macrolet ((pressed (item function)
                 `(qconnect (find-quick-item ,item) "pressed()"
                            (lambda () ,function))))
      (pressed "up"       (sokoban:move :north *maze*))
      (pressed "down"     (sokoban:move :south *maze*))
      (pressed "left"     (sokoban:move :west *maze*))
      (pressed "right"    (sokoban:move :east *maze*))
      (pressed "previous" (change-level :previous))
      (pressed "next"     (change-level :next))
      (pressed "undo"     (undo))
      (pressed "restart"  (reset-maze))
      (pressed "solve"    (solve))))
      

If you already played the game finishing a level, you will have noticed that there are 2 animations (rotation of the player, wiggling of all boxes) which run queued.
This is a little tricky to do, but with the help of a Lisp macro, we only need these lines in Lisp (being queued a macro):

  (defun final-animation ()
    (queued (qml-set "rotate_player" "running" t)
            (qml-set-all "wiggle_box" "running" t)))
      

Please see the sources for all the details. And this would not be possible without a Lisp function called from QML for notifying us whenever an animation state changes, see 'qml/ext/RotationAnimation.qml':

  import QtQuick 2.0
  import EQL5 1.0

  RotationAnimation {
      onRunningChanged: Lisp.call("qsoko:animation-change", running)
  }
      

---

What I left out to explain is the dynamic (at run time) creation of QML items (see 'qml/items/*' and 'lisp/sokoban.lisp'); let's just say that this is left as an exercise to the reader, as all sources will patiently stay there to be read...

---

Well. But I still didn't answer the initial question: how big of a download is to be expected, 10 years later?

Since our APK file uses the ministro service for automatically installing the needed Qt libraries at the first launch of the app, it will only need to include both the ECL and EQL5 libraries (you can therefore use different ECL and EQL5 versions for every app you deploy).

So, to finally answer the question: our download will be ca. 3.5 MB (instead of 3 MB, 10 years ago, although we obviously compare apples and oranges here).

Seems acceptable.

And since I promised you to test it instantly (if you own a device with ARM processor), here you are:

sokoban.apk

Enjoy!

15 Jul 2017 1:00am GMT

New projects:

• cepl.spaces - Adds abstractions over vector spaces to CEPL - BSD 2 Clause
• cl-cpus - Get number of CPUs - ISC
• cl-diskspace - List disks, get disk total/free/usable space information. - ISC
• cl-fixtures - A simple library to create and use parameterized fixtures - MIT
• cl-fluent-logger - A structured logger for Fluentd - BSD 3-Clause
• cl-mixed - Bindings to libmixed, a sound mixing and processing library. - Artistic
• cl-rail - Unspecified - Unspecified
• cl-random-forest - Random Forest and Global Refinement for Common Lisp - MIT Licence
• cl-soloud - Bindings to SoLoud, a multi-platform, multi-backend, minimal dependencies sound mixing and output library - Artistic
• cl-ssdb - SSDB client for Common Lisp. - MIT
• cl-threadpool - Implementation of a thread pool - MIT
• deploy - Tools to aid in the deployment of a fully standalone application. - Artistic
• doplus - DO+ (doplus) is a high-level, extensible iteration construct for Common Lisp with a reasonably simple implementation, which in particular does not use a code walker. - GPLv3
• flow - A flowchart and generalised graph library. - Artistic
• gtk-tagged-streams - Text I/O using streams for GTK text buffers, including tags for styling. - BSD Simplified (2-clause)
• harmony - A common lisp sound server and sound processing library. - Artistic
• hu.dwim.zlib - Common Lisp FFI wrapper for zlib, aka http://zlib.net/ - BSD or Bugroff
• modest-config - A modest config file loader library - MIT
• nineveh - A library of common gpu functions - BSD 2 Clause
• papyrus - A Literate Programming Tool - MIT
• parseq - A parser for sequences such as strings, lists, vectors as well as trees. - GPLv2
• physical-quantities - Use lisp numbers for physical quantities with unit and error. - GPLv2
• roan - A library to support change ringing applications, including methods library support - MIT
• sanitized-params - Sanitizer for parameters - BSD 2-Clause
• sdl2-game-controller-db - Lets you easily load the lovely sdl2 gamecontroller db into cl-sdl2 - BSD 3 Clause
• trivial-battery - Getting the battery information - BSD 2-Clause
• trivial-swank - swank server communications - BSD simplified
• trivial-wish - Create 'wishes' which are requests to compute something later - BSD 2-clause

Updated projects: 3d-matrices, 3d-vectors, architecture.builder-protocol, architecture.service-provider, ayah-captcha, caveman, caveman2-widgets-bootstrap, cepl, cepl.camera, cepl.devil, cepl.sdl2, cepl.sdl2-image, cepl.sdl2-ttf, cepl.skitter, cffi, cl+ssl, cl-ana, cl-ansi-term, cl-bloom, cl-dbi, cl-emoji, cl-fond, cl-gamepad, cl-gists, cl-glfw3, cl-graph, cl-haml, cl-hash-util, cl-jpeg, cl-monitors, cl-mssql, cl-ntp-client, cl-ohm, cl-opengl, cl-out123, cl-plplot, cl-readline, cl-scsu, cl-soil, cl-str, cl-twitter, clack, clim-widgets, closer-mop, clsql-fluid, clss, clx, croatoan, curry-compose-reader-macros, deeds, dendrite, dirt, documentation-utils, doubly-linked-list, drakma, easing, erudite, esrap, f2cl, fare-scripts, fast-http, fast-io, femlisp, fs-utils, fxml, gamebox-dgen, gamebox-ecs, gamebox-frame-manager, gamebox-grids, gamebox-math, gettext, glaw, glkit, glop, glsl-spec, glsl-toolkit, horner, http-get-cache, hu.dwim.asdf, hu.dwim.util, hu.dwim.web-server, inquisitor, iolib, jsonrpc, jwacs, l-system, lichat-protocol, livesupport, log4cl, macrodynamics, maiden, mcclim, media-types, metatilities, mito, mk-string-metrics, opticl, parachute, png-read, prbs, qlot, qmynd, qtools, rtg-math, rutils, scalpl, scriptl, sdl2kit, serapeum, simple-logger, sketch, skitter, smackjack, spinneret, staple, structy-defclass, stumpwm, the-cost-of-nothing, tm, translate-client, trivial-main-thread, trivial-mmap, trivial-shell, trivial-update, uffi, umlisp, unix-opts, varjo, weblocks, websocket-driver, whofields, with-cached-reader-conditionals, woo, yaclml.

To get this update, use (ql:update-dist "quicklisp"). Enjoy!

01 Jul 2017 6:54pm GMT

I've long felt that compilers (and symbolic processing in general) would benefit from embedding integer programming solvers. However, I was never comfortable with actually doing so for a production system that others would have to run: industrial strength integer linear programming solvers are large systems with complex runtime behaviour, and that's not the kind of black box you want to impose on people who just want to build their project. (That's also true of SAT solvers, though, so maybe embedding complicated black boxes is the new normal?)

However, if we had something simple enough to implement natively in the compiler, we could hope for the maintainers to understand what the ILP solver is doing. This seems realistic to me mostly because the generic complexity tends to lie in the continuous optimisation part. Branching, bound propagation, etc. is basic, sometimes domain specific, combinatorial logic; cut generation is probably the most prominent exception, and even that tends to be fairly combinatorial. (Maybe that's why we seem to be growing comfortable with SAT solvers: no scary analysis.) So, for the past couple years, I've been looking for simple enough specialised solvers I could use in branch-and-bound for large 0/1 ILP.

Some stuff with augmented lagrangians and specialised methods for box-constrained QP almost panned out, but nested optimisation sucks when the inner solver is approximate: you never know if you should be more precise in the lower level or if you should aim for more outer iterations.

A subroutine in Chubanov's polynomial-time linear programming algorithm [PDF] (related journal version) seems promising, especially since it doesn't suffer from the numerical issues inherent to log barriers.

Chubanov's subroutine in branch-and-bound

Chubanov's "Basic Subroutine" accepts a problem of the form \(Ax = 0\), \(x > 0\), and either:

1. returns a solution;
2. returns a non-empty subset of variables that must be 0 in any feasible solution;
3. returns a non-empty subset of variables \(x\sb{i}\) that always satisfy \(x\sb{i} \leq u\) in feasible solutions with \(x\sp{\star} \in [0, 1]\), for some constant \(u < 1\) (Chubanov sets \(u = \frac{1}{2}\)).

The class of homogeneous problems seems useless (never mind the nondeterministic return value), but we can convert "regular" 0/1 problems to that form with a bit of algebra.

Let's start with \(Ax = b\), \(0 \leq x \leq 1\), we can reformulate that in the homogeneous form:

\[Ax - by = 0,\] \[x + s - \mathbf{1}y = 0,\] \[x, s, y \geq 0.\]

Any solution to the original problem in \([0, 1]\) may be translated to the homogeneous form (let \(y = 1\) and \(s = 1 - x\)). Crucially, any 0/1 (binary) solution to the original problem is still 0/1 in the homogeneous form. In the other direction, any solution with \(y > 0\) may be converted to the box-constrained problem by dividing everything by \(y\).

If we try to solve the homogenous form with Chubanov's subroutine, we may get:

1. a strictly positive (for all elements) solution. In that case, \(y > 0\) and we can recover a solution to the box-constrained problem.
2. a subset of variables that must be 0 in any feasible solution. If that subset includes \(y\), the box-constrained problem is infeasible. Otherwise, we can take out the variables and try again.
3. a subset of variables that are always strictly less than 1 in feasible solutions. We exploit the fact that we only really care about 0/1 solutions (to the original problem or to the homogenous reformulation) to also fix these variables to 0; if the subset includes \(y\), the 0/1 problem is infeasible.

As soon as we invoke the third case to recursively solve a smaller problem, we end up solving an interesting ill-specified relaxation of the initial 0/1 linear program: it's still a valid relaxation of the binary problem, but is stricter than the usual box linear relaxation.

That's more than enough to drive a branch-and-bound process. In practice, branch-and-bound is much more about proving the (near-) optimality of an existing solution than coming up with strong feasible solutions. That's why the fact that the subroutine "only" solves feasibility isn't a blocker. We only need to prove the absence of 0/1 solutions (much) better than the incumbent solution, and that's a constraint on the objective value. If we get such a proof, we can prune away that whole search subtree; if we don't, the subroutine might have fixed some variables 0 or 1 (always useful), and we definitely have a fractional solution. That solution to the relaxation could be useful for primal heuristics, and will definitely be used for branching (solving the natural LP relaxation of constraint satisfaction problems ends up performing basic propagation for us, so we get some domain propagation for free by only branching on variables with fractional values).

At the root, if we don't have any primal solution yet, we should probably run some binary search on the objective value at the root node and feed the resulting fractional solutions to rounding heuristics. However, we can't use the variables fixed by the subroutine: until we have a feasible binary solution with objective value \(Z\sp{\star}\), we can't assume that we're only interested in binary solutions with object value \(Z < Z\sp{\star}\), so the subroutine might fix some variables simply because there is no 0/1 solution that satisfy \(Z < k\) (case 3 is vacuously valid if there is no 0/1 solution to the homogeneous problem).

That suffices to convince me of correctness. I still have to understand Chubanov's "Basic Subroutine."

Understanding the basic subroutine

This note by Cornelis/Kees Roos helped me understand what makes the subroutine tick.

The basic procedure updates a dual vector \(y\) (not the same \(y\) as the one I had in the reformulation... sorry) such that \(y \geq 0\) and \(|y|_1 = 1\), and constantly derives from the dual vector a tentative solution \(z = P\sb{A}y\), where \(P\sb{A}\) projects (orthogonally) in the null space of the homogeneous constraint matrix \(A\) (the tentative solution is \(x\) in Chubanov's paper).

At any time, if \(z > 0\), we have a solution to the homogenous system.

If \(z = P\sb{A}y = 0\), we can exploit the fact that, for any feasible solution \(x\), \(x = P\sb{A}x\): any feasible solution is alrady in the null space of \(A\). We have

\[x\sp{\top}y = x\sp{\top}P\sb{A}y = x\sp{\top}\mathbf{0} = 0\]

(the projection matrix is symmetric). The solution \(x\) is strictly positive and \(y\) is non-negative, so this must mean that, for every component of \(y\sb{k} > 0\), \(x\sb{k} = 0\). There is at least one such component since \(|y|_1 = 1\).

The last condition is how we bound the number of iterations. For any feasible solution \(x\) and any component \(j\),

\[y\sb{j}x\sb{j} \leq y\sp{\top}x = y\sp{\top}P\sb{A}x \leq |x| |P\sb{A}y| \leq \sqrt{n} |z|.\]

Let's say the max element of \(y\), \(y\sb{j} \geq 2 \sqrt{n}|z|\). In that case, we have \[x\sb{j} \leq \frac{\sqrt{n}|z|}{y\sb{j}} \leq \frac{1}{2}.\]

Chubanov uses this criterion, along with a potential argument on \(|z|\), to bound the number of iterations. However, we can apply the result at any iteration where we find that \(x\sp{\top}z < y\sb{j}\): any such \(x\sb{j} = 0\) in binary solutions. In general, we may upper bound the left-hand side with \(x\sp{\top}z \leq |x||z| \leq \sqrt{n}|z|\), but we can always exploit the structure of the problem to have a tighter bound (e.g., by encoding clique constraints \(x\sb{1} + x\sb{2} + … = 1\) directly in the homogeneous reformulation).

The rest is mostly applying lines 9-12 of the basic procedure in Kees's note. Find the set \(K\) of all indices such that \(\forall k\in K,\ z\sb{k} \leq 0\) (Kees's criterion is more relaxed, but that's what he uses in experiments), project the vector \(\frac{1}{|K|} \sum\sb{k\in K}e\sb{k}\) in the null space of \(A\) to obtain \(p\sb{K}\), and update \(y\) and \(z\).

The potential argument here is that after updating \(z\), \(\frac{1}{|z|\sp{2}}\) has increased by at least \(|K| > 1\). We also know that \(\max y \geq \frac{1}{n}\), so we can fix a variable to 0 as soon as \(\sqrt{n} |z| < \frac{1}{n}\), or, equivalently, \(\frac{1}{|z|} > n\sp{3/2}\). We need to increment \(\frac{1}{|z|\sp{2}}\) to at most \(n\sp{3}\), so we will go through at most \(1 + n\sp{3})\) iterations of the basic procedure before it terminates; if the set \(K\) includes more than one coordinate, we should need fewer iterations to reach the same limit.

Chubanov shows how to embed the basic procedure in a basic iterative method to solve binary LPs. The interesting bit is that we reuse the dual vector \(y\) as much as we can in order to bound the total number of iterations in the basic procedure. We fix at least one variable to \(0\) after a call to the basic procedure that does not yield a fractional solution; there are thus at most \(n\) such calls.

Next step

In contrast to regular numerical algorithms, the number of iterations and calls so far have all had exact (non asymptotic) bounds. The asymptotics hide in the projection step, where we average elementary unit vectors and project them in the null space of \(A\). We know there will be few (at most \(n\)) calls to the basic procedure, so we can expend a lot of time on matrix factorisation. In fact, Chubanov outright computes the projection matrix in \(\mathcal{O}(n\sp{3})\) time to get his complexity bound of \(\mathcal{O}(n\sp{4})\). In practice, this approach is likely to fill a lot of zeros in, and thus run out of RAM.

I'd start with the sparse projection code in SuiteSparse. The direct sparse solver spends less time on precomputation than fully building the projection matrix (good if we don't expect to always hit the worst case iteration bound), and should preserve sparsity (good for memory usage). In return, computing projections is slower, which brings the worst-case complexity to something like \(\mathcal{O}(n\sp{5})\), but that can be parallelised, should be more proportional to the number of non-zeros in the constraint matrix (\(\mathcal{O}(n)\) in practice), and may even exploit sparsity in the right-hand side. Moreover, we can hope that the \(n\sp{3}\) iteration bound is pessimistic; that certainly seems to be the case for most experiments with random matrices.

The worst-case complexity, between \(\mathcal{O}(n\sp{4})\) and \(\mathcal{O}(n\sp{5})\), doesn't compare that well to interior point methods (\(\mathcal{O}(\sqrt{n})\) sparse linear solutions). However, that's all worst-case (even for IPMs). We also have different goals when embedding linear programming solvers in branch-and-bound methods. Warm starts and the ability to find solution close to their bounds are key to efficient branch-and-bound; that's why we still use simplex methods in such methods. Chubanov's projection routine seems like it might come close to the simplex's good fit in branch-and-bound, while improving efficiency and parallelisability on large LPs.

17 Jun 2017 7:24pm GMT

Dear Community,

During this iteration we had many valuable contributions. It's a joy to see how McCLIM gains more mindshare and people are willing to put their time and wallet in fixing issues and writing applications in McCLIM.

Some highlights for this iteration:

• many Listener fixes,
• major tab layout extension refactor,
• new extension for Bezier curves (based on older internal implementation),
• interactor improvements,
• layout improvements,
• fixes for redisplay and transformations,
• documentation cleanups,
• cleanup of the issues (closed the obsolete and fixed ones).

All McCLIM bounties (both active and already solved) may be found here.

Bounties solved this iteration:

• [$200] Interactor CLI prompt print problem

Fixed by Gabriel Laddel. Waiting for a pull request and a bounty claim.

• [$200] Problem with coordinate swizzling (probably).

Fixed by Alessandro Serra and merged. Waiting for a bounty claim.

• [$100] menu for input-prompt in lisp-listener does not disappear after use.

Fixed by Alessandro Serra and merged. Waiting for a bounty claim.

Active bounties:

• [$150] When flowing text in a FORMATTING-TABLE, the pane size is used instead of the column size.

• [$150] clx: input: english layout. (someone already works on it).

• [$100] Caps lock affects non-alphabetic keys. (new)

• [$100] Add PDF file generation (PDF backend). (new)

• [$100] Keystroke accelerators may shadow keys even if inactive. (new)

Our current financial status is $1,429 for bounties and $267 recurring monthly contributions from the supporters (thanks!).

Suggestions as to which other issues should have a bounty on them are appreciated and welcome. Please note that Bountysource has a functionality "Suggest an Issue" which may be found on the bounties page. If you feel that you may solve some problem, but there is no bounty on it, feel free to suggest it too.

If you have any questions, doubts or suggestions - please contact me either by email (daniel@turtleware.eu) or on IRC (my nick is jackdaniel).

Sincerely yours,
Daniel Kochmański

12 Jun 2017 1:00am GMT

11 Jun 2017 10:41am GMT

Next Saturday, the 17th of June, there is going to be a live "study session" about Shirakumo's game engine Trial. The intention of this event is to get people acquainted with the internal structure and features of Trial, so that they may work on it by themselves, and thus help improve it in the future.

The study session is going to be held on my regular stream from 10:00-16:00 UTC. That's 12:00-18:00 CEST, 6:00-12:00 EST, 19:00-3:00 JST. We might stop earlier if people run out of steam or there isn't as much to cover as I anticipated.

Participants that want to actively ask questions and follow along are encouraged to download and set up Mumble for voice communication, and to download the source code of Trial and its dependencies ahead of time, so that they may follow along on their own screens, rather than being subject to the stream delay.

You are expected to have a decent understanding of Common Lisp, as I won't have time to teach you that. While an understanding of modern OpenGL is advantageous, it won't be required. I'll try to explain OpenGL as much as possible or necessary as we go along. Likely there will be another stream at a later point, where modern OpenGL is explained from the ground up.

Hope to see you there!

10 Jun 2017 9:10am GMT

(See also: https://jobs.dou.ua/companies/surftown/vacancies/42175/)

Keepit.com is expanding and we are looking for candidates to join our strong cloud software development team.

We use Lisp systems to implement business logic operations such as resource accounting, data mining, billing, automated operations (AI), full system test suites and more. We wish to extend our team with another skilled colleague, to work with us in this area.

We expect a strong technical mind coupled with a visionary outlook and ability to work closely together with the entire team, from architecture through development, QA and ultimately production.

Keepit can offer a passionate working environment with bright minded colleagues bringing out the next generations of data consolidation, data security and data sharing solutions coupled with the ability to bring-out real value of the data of our customers.

Required skills:

Good understanding of Common Lisp;

Good algorithmic knowledge

Will be a plus:

Good understanding of HTTP, REST and XML;

Shell scripting and ability to read/write Makefiles;

Experience with Emacs, slime/swank and SBCL;

Some knowledge of C++

Desired communication skills:

Team player, but with high degree of ability to work independently;

Upper-intermediary level of English for daily written and video calls communication;

Person who is gladly willing to share knowledge within the team;

Willingness to take initiative and suggest alternative ways of solving problems;

Quick learner, self starter.

Contact information:

e-mail: mhn@keepit.com, Skype: maryna.hnatyk

09 Jun 2017 1:24pm GMT

07 Jun 2017 12:11pm GMT