Efficiently handling last-mile deliveries becomes more and more important nowadays. Using drones to support classical vehicles allows improving delivery schedules as long as efficient solution methods to plan last-mile deliveries with drones are available. We study exact solution approaches for some variants of the traveling salesman problem with drone (TSP-D) in which a truck and … Read more
Techniques based on sharing data and computation among queries have been an active research topic in database systems. While work in this area developed algorithms and systems that are shown to be effective, there is a lack of rigorous modeling and theoretical study for query processing and optimization. Query batching in database systems has strong … Read more
The combinatorial integral approximation (CIA) decomposition suggests to solve mixed-integer optimal control problems (MIOCPs) by solving one continuous nonlinear control problem and one mixed-integer linear program (MILP). Unrealistic frequent switching can be avoided by adding a constraint on the total variation to the MILP. Within this work, we present a fast heuristic way to solve … Read more
We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an r-dimensional linear space. The resulting MIP formulation is ideal, and uses exactly r integer variables and 2 x (# of spanning hyperplanes) general inequality constraints. We use … Read more
A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this paper, we first revisit basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we … Read more
Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous … Read more
The minimum connectivity inference (MCI) problem represents an NP-hard generalization of the well-known minimum spanning tree problem. Given a set of vertices and a finite collection of subsets (of this vertex set), the MCI problem requires to find an edge set of minimal cardinality so that the vertices of each subset are connected. Although the … Read more
Tailored mixed-integer optimal control policies for real-world applications usually have to avoid very short successive changes of the active integer control. Minimum dwell time constraints express this requirement and can be included into the combinatorial integral approximation decomposition, which solves mixed-integer optimal control problems by solving one continuous nonlinear program and one mixed-integer linear program. … Read more
For sparse graphs, the odd cycle polytope can be used to compute useful bounds for the maximum stable set problem quickly. Yannakakis introduced an extended formulation for the odd cycle inequalities of the stable set polytope in 1991, which provides a direct way to optimize over the odd cycle polytope in polynomial time, although there … Read more
We consider a problem involving a set of agents who need to coordinate their actions to optimize the sum of their objectives while satisfying a common resource constraint. The objective functions of the agents are unknown to them a priori and are revealed in an online manner. The resulting problem is an online optimization problem … Read more