Mixed-integer quadratic programming (MIQP) is the problem of optimizing a quadratic function over points in a polyhedral set where some of the components are restricted to be integral. In this paper, we prove that the decision version of mixed-integer quadratic programming is in NP, thereby showing that it is NP-complete. This is established by showing that if the decision version of mixed-integer quadratic programming is feasible, then there exists a solution of polynomial size. This result generalizes and unifies classical results that quadratic programming is in NP and integer linear programming is in NP.

We describe a general adaptation of the well-known Multiplicative Weights Update algorithm for Mixed-Integer Nonlinear Programming. This algorithm is an iterative procedure which updates a distribution based on a gains/costs vector at the preceding iteration, samples decisions from the distribution, and updates the gains/costs vector based on the decisions. Our adaptation relies on the concept of ``pointwise reformulation'', which is expressed in function of some parameters $\theta$ and has the property that, for a certain value of $\theta$, the optimum of the reformulation is an optimum of the original problem. The Multiplicative Weights Update algorithm is used to find good values for $\theta$.

We follow on our 2012 talk in loving memory of Alberto to report on the (interesting, but not exhaustive) results on our investigation about decomposition methods for large-scale programs, with particular focus on (continuous, linear) Multicommodity Min-Cost Flow problems. These are based on separating the problem into small subproblems, and then "gluing back together" the generated information. This latter step is fundamental, and is typically achieved by a master problem. Although a couple of "by-the-book" versions of the master problem exist that are usually considered in the literature, there actually are many possible variants; we show that choosing the right one has a substantial impact on the overall performances, and therefore is a crucial step to obtain the most efficient approach. This choice is, however, far from being trivial.

(A computer implementation based on the presented work ranked first in most categories at the recent DIMACS 11 competition) The Steiner Tree Problem is a challenging NP-hard problem. Many hard instances of this problem are publicly available, that are still unsolved by state-of-the-art branch-and-cut codes. We conjecture that the extreme hardness of some classes of instances mainly comes from over-modeling, and that some instances can become quite easy to solve when a simpler model is considered. In other words, we aim at “thinning out” the usual models for the sake of getting a more agile framework. In particular, we focus on a model that only involves node variables, which is rather appealing for the “uniform” cases where all edges have the same cost. We show that this model allows one to quickly produce very good (sometimes proven optimal) solutions for notoriously hard instances from the literature. In particular, we report improved solutions for several STEINlib instances, including the (in)famous hypercube ones. Even though we do not claim our approach can work well in all cases, we report surprisingly good results for a number of unsolved instances. In some cases, our approach takes just few seconds to prove optimality for instances never solved (even after days of computation) by the standard methods. (joint work with Markus Leitner, Ivana Ljubic, Martin Luipersbeck, Michele Monaci, Max Resch, Domenico Salvagnin, and Markus Sinnl)

We present a specialized branch-and-bound (b&b) algorithm for the Euclidean Steiner tree problem (ESTP) in n-space and apply it to a convex mixed-integer nonlinear programming (MINLP) formulation of the problem. The algorithm contains procedures to avoid difficulties observed when applying a b&b algorithm for general MINLP problems to solve the ESTP. Our main emphasis is on isomorphism pruning, in order to prevent solving several equivalent subproblems corresponding to isomorphic Steiner trees. We also propose more general procedures, which may be extended to the solution of other MINLP problems.

Consider a graph with a vertex subset denoted as terminals. The Steiner tree problem in graphs asks for a cost-minimum tree connecting all terminals, while possibly also using some other vertices. It is quite simple and practically fast to approximate the Steiner tree problem on graphs within a ratio of $2$. The last decades have brought us several improvements along the lines of combinatorial algorithms (achieving ratios as low as $1.55$), and of LP-based rounding schemes (down to the currently best ratio of $1.38$). However, all these algorithms share the common trait that they depend on some parameter $k$; while their running time is exponentially dependent on $k$, the approximation ratio is only achieved for $k\to\infty$. We investigate the practical applicability of nearly all known approximation algorithms with ratio $<2$, and compare them to simple heuristics as well as exact algorithms.

We consider a generalization of the 0-1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The Interval Min-max Regret Knapsack Problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the complexity class Sigma^p_2 hence it is most probably not in NP. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an NP-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm, and evaluate their performance through extensive computational experiments.

We consider the classical 0-1 knapsack problem with an additional disjunctive relation on pairs of items represented by a conflict graph. This means that adjacent vertices in the graph correspond to items that may not be packed together in the knapsack. We present pseudopolynomial time algorithms for weakly chordal graphs and more generally for graph classes that do contain only polynomially many maximal cliques. Our algorithm is based on results by Fomin and Villanger [2010] and Lokshtanov et al. [2014] and can be extended to obtain FPTASs.

Joint work with Yann Disser, Max Klimm, and Nicole Megow. How to order the waiting list for an overbooked flight? This amounts to the problem of packing a knapsack without knowing its capacity. Whenever we attempt to pack an item that does not fit, the item is discarded; if the item fits, we have to include it in the packing. We show that there is always a policy that packs a value within factor 2 of the optimum packing, irrespective of the actual capacity. If all items have unit density, we achieve a factor equal to the golden ratio R = 1.618. Both factors are shown to be best possible. In fact, we obtain the above factors using packing policies that are universal in the sense that they fix a particular order of the items and try to pack the items in this order, independent of the observations made while packing. We give efficient algorithms computing these policies. On the other hand, we show that, for any R > 1, the problem of deciding whether a given universal policy achieves a factor of R is coNP-complete. If R is part of the input, the same problem is shown to be coNP-complete for items with unit densities. Finally, we show that it is coNP-hard to decide, for given R, whether a set of items admits a universal policy with factor R, even if all items have unit densities.

We present a new polynomially solvable case of the Quadratic Assignment Problem in Koopmans-Beckman form QAP(A,B), by showing that the identity permutation is optimal when A and B are respectively a Robinson similarity and dissimilarity matrix and one of A or B is a Toeplitz matrix. Robinsonian matrices arise in the classical seriation problem and play an important role in many applications where unsorted similarity (or dissimilarity) information must be reordered. Furthermore, we present a Lex-BFS based recognition algorithm based on a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs.

This lecture is dedicated to Manfred Padberg who passed away on May 12, 2014 after a long battle with cancer. Manfred is the person who introduced me to the techniques of combinatorial optimization and is my “spiritual” PhD thesis advisor. My lecture will consist of a combination of personal remembrances (encounters that led to a lifelong personal and scientific friendship) and sketches of Manfred’s fundamental contributions to optimization.

Within the next year, the Federal Communications Commission will be holding the first-ever "incentive auction" in which a government asks TV station to relinquish rights for payment and then — having obtained interference-free spectrum, sells the acquired spectrum to the wireless communications industry. The auction is expected to be the biggest spectrum auction ever with estimates that it will generate far more revenue than 38 billion dollars that the 2014 FCC Advanced Wireless Service (AWS) auction yielded. The proposed multi-round/multi-stage auction requires the solution of over a million satisfiability problem where each problem indicates whether or not it is possible to pack a given set of stations into a given bandwidth of spectrum. Besides these important problems, optimization has played an important role in informing policy on the impact of specific auction rules, on setting the amount of spectrum that will be auctioned, on determining the final channel assignments for the auction and on determining the sequencing of the relocation of TV stations to new channel assignments after the auction ends. The structure of each of these problem is a generalization of the weighted graph coloring problems. The problems have hundreds of thousands of variables and the constraint set can exceed 3 million rows. We will present the various approaches that were used to obtain optimal and near-optimal solutions to these difficult problems: both heuristics and decomposition methods. At the conclusion, we will provide information about accessing both the publicly-available data sets and the mathematical formulations for all problems.

For an integer linear program, Gomory's corner relaxation is obtained by ignoring the nonnegativity of the basic variables in a tableau formulation. In joint work with Sercan Yildiz, we do not relax these nonnegativity constraints. We generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry and periodicity. Our result is based on a new concept, the notion of generalized symmetry condition. We also generalize the 2-slope theorem of Gomory and Johnson for extreme cut-generating functions.

In this talk we present some properties of two-branch split cuts, which generalize the split cuts of Cook, Kannan and Schrijver, and were studied by Li and Richard (2008). In particular, we show that the closure of a polyhedral set with respect to two-branch split cuts is a polyhedron. Furthermore, we use this result to show that the quadrilateral closure of the two-row continuous group relaxation (the set of points satisfying all cutting planes obtained from maximal lattice-free quadrilaterals) is a polyhedron, answering an open question in Basu, Bonami, Cornuejols and Margot (2011). This is joint work with Oktay Gunluk and Diego Moran.

When reformulating a given mixed integer program by the use of classical Dantzig-Wolfe decomposition, a subset of the constraints is partially convexified, which corresponds to implicitly adding all valid inequalities for the associated integer hull. This yields an extended formulation with a potentially stronger LP relaxation than the original formulation. Thus, a solution of the original linear programming (LP) relaxation obtained by transferring an optimal basic solution of the reformulated LP relaxation is in general not basic and furthermore, a basic solution in the original LP relaxation having the same objective value may not even exist. Hence, cutting planes that are separated using a basis like Gomory mixed integer cuts or strong Chvatal-Gomory cuts are usually not directly applicable when separating such a solution in the original problem. Nevertheless, we can use a heuristic to obtain a basic solution and separate this auxiliary solution by applying all separators including those using a basis. The generated cutting planes might not only cut off the auxiliary solution, but also the solution we originally wanted to separate. So far, this problem was only considered extensively by Range, who proposed the previously described approach including a particular heuristic. We present alternative heuristics to obtain a basic solution and extend this procedure by considering additional valid inequalities strengthening the original LP relaxation. Furthermore, we provide the first full implementation of a separation procedure like this and tested it on instances of several problem classes.

The talk discusses several integer programming models for a real-world (compiler) scheduling problem. One of them is a newly developed model based on the linear ordering problem. It is presented in some more detail and experimental results are given to show that a branch-and-cut implementation based on this model can compete with the currently best methods from constraint programming. The talk also addresses the weaknesses and potential further improvements of the approach.

Joint work with: Volker Kaibel, Jon Lee, Matthias Walter We show that every independence polytope of a regular matroid has an extended formulation of size quadratic in the number of its ground elements. This generalizes the same statement for (co-)graphic matroids, which is a simple consequence of Martin's extended formulation for the spanning tree polytope. In our argumentation, we make use of Seymour's decomposition theorem for regular matroids.

We present a polynomial time algorithm to find a 3-coloring of a graph without an induced path on seven vertices. Joint work with Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Maya Stein, and Mingxian Zhong.

We consider the fundamental resource minimization problem in which we ask for the minimum number of machines that is necessary for feasibly scheduling jobs with release dates and hard deadlines. We study the online variant of this problem in which every job becomes known to an algorithm only at its release date. We develop several algorithms for preemptive and non-preemptive problem variants, and evaluate their performance by the competitive ratio, a widely-used measure that compares the solution value of an online algorithm with an optimal offline value. As the most general special case we consider jobs with agreeable deadlines, i.e., the time intervals for scheduling jobs form a proper interval graph. We give the first constant-competitive non-preemptive algorithm for this problem, which is of particular interest given the strong lower bound of n for the general problem. We also prove that for the preemptive scheduling problem, one of the most natural algorithms, Least Laxity First (LLF), achieves a constant ratio for agreeable jobs, while in general its performance guarantee is lower bounded by Omega(n^{1/3}). Our most general result is a O(log n)-competitive algorithm for the general preemptive scheduling problem.

Several well-known discrete optimization problems can be formulated as continuous quadratic minimization problems in which the objective function is concave along the edges of the feasible set, a property known as edge-concavity. Examples include the edge and vertex separator problems on a graph. In this talk, we show that these formulations possess the interesting property that local optimality can be checked in polynomial time (for a general quadratic program determining local optimality of a feasible point is NP-hard). Along the way, we also derive new first and second order optimality conditions for general nonlinear programs. These conditions are stated in terms of the first and second derivatives of the objective function along the directions parallel to edges of the feasible set.

Midterm hydro scheduling problem is about optimizing the performance of a hydro network over a period of few months. This decision problem is affected by uncertainty on energy prices, demands and rainfall, and we model it as a nonlinear chance-constrained mathematical program. This is a Multi-stage problem where at each stage we must decide how much water to release from the reservoirs, i.e. determines how much energy we can produce. The production function is nonlinear, at a first approximation concave, but in fact nonconvex. Moreover, the inflows and the demands are random, thus the profit over the entire time horizon is therefore nondeterministic. We present a Branch-and-Cut algorithm based on the approach recently proposed by Jim Luedtke, which uses Benders-type cuts. However, in our case the feasible region induced by each scenario is a general convex set instead of a polyhedron. Further more, we introduce a separation algorithm for the corresponding scenario subproblems that exploits projection and KKT conditions, and has some clear advantages over generalized Benders decomposition. Joint work with Andrea Lodi, Giacomo Nannicini, Dimitri Thomopulos

We consider extended formulations that give the same feasible region when projected down to the original space. We show that applying split cuts to such extended formulations can be more effective than applying split cuts to the original formulation. We show that for every 0-1 mixed-integer set with n+k variables, there is an extended formulation with 2n+k variables whose split closure is integral. The proof is constructive. We then extend this idea to general mixed integer sets (the result however does not hold anymore). We also look at split cuts for the Lovasz/Schrijver extended formulation and show that it is significantly stronger than the original procedure. We also have some computational results showing the strength of our approach for 2-row relaxations and the stable set problem.

We present a preliminary version of a software tool which, given a system of linear inequalities and a subset of integer variables, investigates the associated mixed-integer hull. In particular, it detects all equations and some facets valid for the hull with exact arithmetic. The generation of facets can be controlled by specifying an interesting objective function. This is in contrast to usual convex-hull algorithms which produce the entire description of the hull, but run out of resources for small dimensions already. Based on the performance of the MIP solver used this software can handle much larger dimensions. The approach is related to work on target cuts by Buchheim, Liers and Oswald in 2008.

A graph is balanced if its clique-matrix is balanced. No characterization of minimally non-balanced graphs is known, and even no conjecture on the structure of such graphs has been posed. In this talk, we provide such a characterization for the class of diamond-free graphs.

The stable allocation problem is one of the broadest extensions of the well-known stable marriage problem. In an allocation problem, edges of a bipartite graph have capacities and vertices have quotas to fill. Here we investigate the case of uncoordinated processes in stable allocation instances. In this setting, a feasible allocation is given and the aim is to reach a stable allocation by raising the value of the allocation along blocking edges and reducing it on worse edges if needed. Do such myopic changes lead to a stable solution? In our present work, we analyze both better and best response dynamics from an algorithmic point of view. With the help of two deterministic algorithms we show that random procedures reach a stable solution with probability one for all rational input data in both cases. Surprisingly, while there is a polynomial path to stability when better response strategies are played (even for irrational input data), the more intuitive best response steps may require exponential time. We also study the special case of correlated markets. There, random best response strategies lead to a stable allocation in expected polynomial time.

There is a wide assortment of structures which come in pairs. Even though each given instance is easy to recognise, it seems to be generally hard, given an instance, to find its partner. It would be nice to be able to reduce this searching, for one kind of structure, to another. Two such kinds of structure are Hamiltonian paths in graphs with certain properties. Another such kind of structure is simple Euler-Complex abstractions of the Lemke-Howsen method for finding bimatrix equilibria.

The dual bounds obtained by column generation algorithms can be remarkably improved by also including cuts defined over the variables of the Master problem. However, those cuts are non-robust, in the sense that each added cut makes the pricing subproblem harder, quickly making it intractable. Pecin et al.(2014) introduced a "limited memory" technique that allowed an effective use of the Subset Row Cuts (Jepsen et al. (2008)) for the set partitioning formulation of vehicle routing problems. This work generalizes the technique for arbitrary rank-1 cuts. Moreover, a polyhedral investigation helped to determine which sets of multipliers can be useful. The improved branch-cut-and-price algorithm can solve some classical CVRP instances with up to 420 customers.

Railway systems are often affected by delays, disturbances or cancellations. These undesired events can be alleviated by suitably re-routing and re-scheduling trains, in real-time. Such task (train dispatching) is central in managing railway systems as it allows recovering from undesirable deviations from the timetable and better exploiting railway resources. With few exceptions, dispatching is still almost entirely in the hands of human operators, despite the problem amounts to solving a complex and large optimization problem. Dispatchers naturally decompose this problem into two separate sub-problems, by first deciding how trains should travel and meet along the line (macro problem), and then establishing the exact sequencing and platforms assignment in each station. Most heuristic approaches to the problem are based on the same macro/micro decomposition, with the micro problem solved only once the macro is fixed. This decomposition can be made exact by means of a classical tool from mixed integer linear programming, namely Benders' reformulation. In this talk, we describe how integer programming can be exploited to find optimal solutions to large dispatching problems within the stringent time limit required by this application. In particular, we show how to decompose the problem into smaller sub-problems, associated with different parts of the network. This decomposition is the basis for a master-slave solution algorithm, in which the master problem is associated with the line and the slave problem is associated with the stations. The two sub-problems are modeled as mixed integer linear programs, with specific sets of variables and constraints. Similarly to the classical Benders' decomposition approach, slave and master communicate through suitable feasibility cuts in the variables of the master. Interestingly, the slave problem further decompose into smaller sub-problems, each associated to a specific station. We show how the station sub-problem, under some assumptions which are often fulfilled in practice, can be solved in polynomial time. A decision support system based on this exact approach was put in operation in Norway in February 2014, representing one of the first operative applications of mathematical optimization to train dispatching.

Congestion games are widely used to model and analyse the behaviour of selfish acting uncontrolled individuals competing over a commonly used set of resources. A typical example of congestion games can be observed every day at rush hour in a congested city: each individual car driver chooses a route through a street network. The travel time of each of the streets in use highly depends on the congestion caused by the route choices of the other car drivers. A stable state ("equilibrium") is reached if none of the individuals can improve its outcome by unilateral switching to an alternative strategy. The famous Braess paradox describes the interesting phenomenon that improving the network infrastructure, for example by building new streets, may in fact lead to higher travel times under an equilibrium. We show that Braess paradox cannot occur as long as each player's strategy space forms the base set of a matroid. Moreover, we show that for every non-matroid set system, we can construct a two-player game that does admit the Braess paradox. (Joint work with Tobias Harks, Michel Goemans, Satoru Fujishige and Rico Zenklusen).

The Laplacian energy of a graph is defined as the sum of the absolute values of the differences of average degree and eigenvalues of the Laplacian matrix of the graph. This spectral graph parameter is upper bounded by the energy obtained when replacing the eigenvalues with the conjugate degree sequence of the graph, in which the $i$-th number counts the nodes having degree at least $i$. Because the sequences of eigenvalues and conjugate degrees coincide for the class of threshold graphs, these are considered likely candidates for maximizing the Laplacian energy over all graphs with given number of nodes. We do not answer this open problem, but within the class of threshold graphs we give an explicit and constructive description of threshold graphs maximizing this spectral graph parameter for a given number of nodes, for given numbers of nodes and edges, and for given numbers of nodes, edges and trace of the conjugate degree sequence in the general as well as in the connected case. In particular this positively answers the conjecture that the pineapple maximizes the Laplacian energy over all connected threshold graphs with given number of nodes.

We study polyhedra in the context of network flow problems, where the flow value on each arc lies in one of several predefined intervals. This is motivated by nonlinear problems on transportation networks, where nonlinearities are handled by piecewise linear approximation or relaxation - a common and established approach in many applications. Several methods for modeling piecewise linear functions are known which provide a complete description for a single network arc. However, in general this property is lost when considering multiple arcs. We show how to strengthen the formulation for specific substructures consisting of multiple arcs by linear inequalities. For the case of paths of degree-two-nodes we give a complete description of the polyhedron projected to the integer variables. Our model is based on - but not limited to - the multiple choice method; we also show how to transfer our results to a formulation based on the incremental method. Computational results show that a state-of-the-art MIP-solver greatly benefits from using our cutting planes for random and realistic network topologies.

In communication networks, the routing decision process remains decoupled from the network design process, i.e., resource installation and allocation planning process (centralized and offline). To keep both processes together, we propose a distributed optimization technique aware of distributed nature of the routing process by decomposing the optimization problem along same dimensions as (distributed) routing decision process. For this purpose, we generalize the capacitated multi-commodity capacitated fixed charge network design (MCND) class of problems by including different types of fixed costs (installation and maintenance costs) and variable costs (routing costs) but also variable traffic demands over multiple periods. However, conventional integer programming methods can typically solve only small to medium size instances. As an alternative, we propose a Lagrangian approach for computing a lower bound by relaxing the flow conservation constraints such that the Lagrangian subproblem itself decomposes by node. Though this approach yields one subproblem per network node, solving the Lagrangian dual by means of the bundle method remains a complex computational tasks. However, the approach is more robust than any LP solvers and it always returns some solutions. Instead, we proved that CPLEX, which solves the LP relaxation, is not able to provide a solution for large instances.

Congestion games on networks have extensively been studied till recently. An interesting special class of congestion games on networks is the class of congestion games on extension-parallel networks considered by Holzman and Law-yone (2003). It is shown by Fotakis (2010) that for every congestion game on an extension-parallel network any best-response sequence terminates in $n$ steps and gives a pure Nash equilibrium of the game, where $n$ is the number of players. We show that the fast termination of best-response sequences results from M-convexity of the potential function associated with the game. It is revealed that the best-response dynamic process corresponds to a greedy procedure for minimizing M-convex functions. We also give a characterization of M-convex functions in terms of greedy procedures. (Joit work with Michel Goemans, Tobias Harks, Britta Peis, and Rico Zenklusen)

Network routing problems with elastic traffic demands (i.e., specified by origin-destination pairs without prescribed flow values) and fair allocation of flows have been attracting a growing attention in the networking literature. Motivated by best-effort services in IP networks (e.g., simultaneous data download between different hosts with no guaranteed rate) and adopting the point of view of the network operators, we investigate a bilevel network flow problem introduced in [1] and defined as follows. Given a directed graph with a capacity for each arc and a set of elastic traffic demands specified by the corresponding origin-destination pairs, the network operator has to select a single path for each pair so as to maximize the total throughput while assuming that the flows are allocated over the chosen paths according to a fairness principle. We consider max-min fair flow allocation as well as maximum bottleneck flow allocation. After presenting some structural and complexity results, we discuss MILP formulations, describe a Branch-and-Price algorithm and report some computational results. This is joint work with Stefano Coniglio and Leonardo Taccari. References [1] E. Amaldi, A. Capone, S. Coniglio, L. G. Gianoli: Network Optimization Problems Subject to Max-Min Fair Flow Allocation. IEEE Communications Letters 17(7): 1463-1466 (2013).

During the last century, conic optimisation was established as a useful tool with a wide range of applications. In this talk, we will look at a special type of conic optimisation called copositive optimisation. This provides numerous applications, and we shall look at a new proof for how the NP-hard problem of finding the stability number of a graph can be reformulated as a copositive optimisation problem. From this we see that copositive optimisation is NP-hard.

In the research domain complex problem solving in psychology, where the aim is to analyze complex human decision making and problem solving, computer-based test-scenarios play a major role. The approach is to evaluate the performance of participants within microworlds and correlate it to certain attributes, e.g. the participant's capacity to regulate emotions. In the past, however, these test-scenarios have usually been defined on a trial-and-error basis, until certain characteristica became apparent. The more complex models become, the more likely it is that unforeseen and unwanted characteristics emerge in studies. To overcome this important problem, we propose to use mathematical optimization methodology on three levels: first, in the design stage of the complex problem scenario, second, as an analysis tool, and third, to provide feedback in real time for learning purposes. We present the general setting of this novel application area for optimization technology as well as the most important results from a study on the impact of optimization results on training. These show that knowledge about optimal solutions significantly enhances future performance compared to a control group.

I will present results of joint work with Jan Kr\"umpelmann and Stefan Weltge. Weismantel and Del Pia showed that the sequence of closures with respect to the family of all integral lattice-free polyhedra converges to the mixed-integer hull in finitely many steps. Since one can discard polyhedra which are not maximal with respect to inclusion, the smaller family of all inclusion-maximal integral lattice-free polyhedra already has the mentioned finite-convergence property. Averkov, Wagner and Weismantel showed that, for each dimension d, there are only finitely many inclusion-maximal integral lattice-free polyhedra if one identifies polyhedra coinciding up to unimodular affine transformations. This result leads to the problem of classification of such polyhedra in fixed dimensions d=1,2,3 etc. For dimensions d=1,2 the classification problem is trivial and for each d \ge 3 very challenging. I will discuss the case d=3. Averkov, Wagner and Weismantel classified all three-dimensional inclusion-maximal lattice-free polyhedra whose every facet contains an integral point in the relative interior (there are 12 bounded and 3 unbounded such polyhedra). Surprisingly, the additional condition on facets is indeed a restriction for each dimension d \ge 4, as was shown by Ziegler and Nill. It has been an open question whether the three-dimensional polyhedra found by Averkov, Wagner and Weismantel are all three-dimensional inclusion-maximal lattice-free polyhedra. We answer the latter question in positive. Our proof employs results from the geometry of numbers and a computer-assisted search.

Given a huge set of shipments as well as a predefined freight train schedule that can be slightly varied during the solution process, our goal is to produce optimal transportation plans. Thereby, the main objective is to minimize the energy consumption under consideration of a set of business rules like demand satisfaction and delivery dates that have to be complied. Precisely speaking, the developed methods should provide decision support to railway companies determining which commodities should be transported by which train on which route at what time. The requirements result in a highly complex large scale problem based on tremendous time expanded networks. We develop a compact MIP formulation that fits in a tailor made rolling horizon method and enables us to present first results for real world instances provided by our industrial partner DB Mobility Logistics. This is joint work with Prof. Dr. Zimmermann and funded by the German Federal Ministry of Education and Research (BMBF).

It is well-known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. Many authors have studied the problem of determining an optimal set of transmission lines to switch off to minimize the cost of meeting a given power demand under the direct current (DC) model of power flow. This problem is known in the literature as the Direct-Current Optimal Transmission Switching Problem (DC-OTS). Most research on DC-OTS has focused on heuristic algorithms for generating quality solutions or on the application of DC-OTS to crucial operational and strategic problems. The mathematical theory of the DC-OTS problem is less well-developed. In this work, we formally establish that DC-OTS is NP-Hard, even if the power network is a series-parallel graph with at most one load/demand pair. Inspired by Kirchoff's Voltage Law, we give a cycle-based formulation for DC-OTS, and we use the new formulation to build a cycle-induced relaxation. We characterize the convex hull of the cycle-induced relaxation, and the characterization provides strong valid inequalities that can be used in a cutting-plane approach to solve the DC-OTS. We give details of a practical implementation, and we show promising computational results on standard benchmark instances. This is joint work with: Burak Kocuk, Santanu Dey, Andy Sun (Georgia Tech), Hyemin Jeon, and Jim Luedtke (Wisconsin)