Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

Past Projects

Theoretical Complexity of Container Stowage

I investigated the theoretical complexity of container stowage problems with Rune Møller Jensen and Dario Pacino. Specifically, we proved that the k-Shift problem is solvable in polynomial time when the number of stacks and tiers available to stow containers in is fixed. We further proved that the hatch overstow problem, which involves avoiding container overstowage in the presence of hatch covers on container vessels, is NP-complete. Our article, "On the complexity of container stowage planning problems", was published in Discrete Applied Mathematics in 2014.

ISAC

ISAC clusters for SAT instances Combining GGA and Stochastic Offline Programming (Malitsky and Sellmann 2009), Instance Specific Algorithm Configuration (ISAC) takes advantage of similarities between instances of a problem to train a custom solver that adjusts its parameters based on the instance it is required to solve.

Using the "g-means" clustering algorithm (Learning the k in k-means, Hamerly and Elkan 2003), ISAC forms groups of instances from features provided by the user. GGA is then employed to find high quality parameters for a solver on those instances. Finally, when given an instance to solve, ISAC measures the distance between the instance and its learned cluster centers in order to use the solver parameters that will best solve the instance.

A paper describing the ISAC system with empirical test results was accepted to ECAI 2010.

GGA

Using a novel "gender-based" genetic algorithm, GGA is a state-of-the-art parameter tuner for the automatic configuration of solvers. GGA can handle discrete, continuous and real parameters and has been used to tune solvers for a variety of problems, such as satisfiability (SAT), set covering and mixed integer programs (MIPs). GGA represents the parameters of a target solver as a "parameter tree", a type of and-or tree that expresses the relations of parameters, and exploits the tree structure during optimization.

Source code is not currently available, but binary copies of GGA can potentially be distributed. Please contact me for more information. Alternatively, you can write your own parameter tuning using the algorithm given in our 2009 CP paper.

The University for the Information Society