By Wolfgang Keller
Originally written 2019-03-20
Last modified 2019-03-20
The focus of my mathematical activity in the last years lies in the areas of polyhedral combinatorics, combinatorial optimization and (mixed-)integer linear optimization (here in particular theory of cutting plane algorithms). For these subject areas also the umbrella term “discrete optimization” is common. Regarding cutting plane algorithms, the following remark: hybrid algorithms which combine a branch-and-bound framework with cutting plane algorithms (branch-and-cut algorithms) are currently the most powerful class of algorithms for solving (mixed-)integer linear programs ((M)ILPs).
In the areas of polyhedral combinatorics and combinatorial optimization, I developed two new extended formulations of the spanning tree polytope in my diploma thesis which are still “record holders” for the smallest known asymptotic extension complexity (i.e. number of inequalities) of a symmetric or asymmetric extended formulation of the spanning tree polytope.
My doctoral thesis is guided by the following question: one can naturally assign a cutting plane operator to a class of cutting planes that is used in cutting plane algorithms for solving mixed-integer linear programs ((M)ILPs). Unluckily, there exist a huge number of cutting planes and even if one restricts oneself to cutting plane operators, the number is still very large.
To keep track of this conglomeration, I defined two hierarchies of cutting plane operators based on lineality spaces. These two hierarchies are interleaved like jigsaw pieces and can thus be united into a common hierarchy. For this “double hierarchy”, I showed that many cutting plane operators that are considered in literature lie in this hierarchy (e.g. Chvátal-Gomory closure, split closure, crooked cross closure) or can be bounded by operators in it (e.g. t-branch split closure).
I hold the belief that it is worthless to talk/write of “x years of experience in programming language y” since this reveals nothing about the kind of tasks, the speed of traversing the learning curve etc. I also believe that understanding a programming language really encompassingly (including its complete ecosystem, subtle details of its community etc.) is effectively a life task. The central reason that this attracts little attention lies in my opinion therein that in practice only a superficial selection of the features that modern programming languages and their ecosystems provide is utilized.
Of course, I am also familiar with technologies that one finds in the programming environment, such as version control systems (for my own projects, I use git; but I also worked with Subversion and Mercurial in the past).
My interest in programming topics shall also be testified by the fact that possibly one year ago, I started privately (in the evenings after my “real job” at the university) with writing texts for an alternative curriculum for computer science (all of this is however still in an early state). Among other things, I work here on a new assembly language in particular for x86 processors with the goal to trace back this instruction set that is (in my eyes unjustly) ill-reputed to be inelegant and muddled to elegant basic patterns.