Two approaches to piecewise affine approximation

The problem of approximation by piecewise affine functions has been studied for several decades (least squares and uniform approximation). If the location of switches from one affine piece to another (knots for univariate approximation) is known the problem is convex and there are several approaches to solve this problem. If the location of such switches … Read more

Rounding in Mixed-Integer Model Predictive Control

This paper interfaces combinatorial integral approximation strategies with the inherent robustness properties of conventional model predictive control with stabilizing terminal conditions. We deduce practical stability results for finite-control set and mixed-integer model predictive control and investigate the evolution of the closed-loop system in the presence of control rounding to draw conclusions about deviation from optimality. … Read more

Descent Scheme for a Class of Bilevel Programming Problems

In this paper, a class of bilevel programming problems is studied, in which the lower level is a quadratic programming problem, and the upper level problem consists of a nonlinear objective function with coupling constraints. An iterative process is developed to generate a sequence of points, which converges to the solution of this problem. In … Read more

Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization

Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-sample strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, we derive a semidefinite relaxation and a randomized rounding scheme, which obtains provably near-optimal solutions, mimicking the blueprint from Goemans and Williamson for the Max-Cut problem. We … Read more

Integrated Optimization of Timetabling and Electric Vehicle Scheduling: A Case Study of Aachen, Germany

We tackle the integrated planning problem of periodic timetabling and electric vehicle scheduling, crucial for cities transitioning to electric bus fleets. Given existing timetables, we allow only minor modifications and propose an iterative solution approach that addresses the Electric Vehicle Scheduling Problem (EVSP) in each iteration. Due to the NP-hard nature of EVSP, we employ … Read more

Robust combinatorial optimization problems with knapsack constraints under interdiction uncertainty

We present an algorithm for finding near-optimal solutions to robust combinatorial optimization problems with knapsack constraints under interdiction uncertainty. We incorporate a heuristic for generating feasible solutions in a standard row generation approach. Experimental results are presented for set covering, simple plant location, and min-knapsack problems under a discrete-budgeted interdiction uncertainty set introduced in this … Read more

Local Convergence Analysis for Nonisolated Solutions to Derivative-Free Methods of Optimization

This paper provides a local convergence analysis for newly developed derivative-free methods in problems of smooth nonconvex optimization. We focus here on local convergence to local minimizers, which might be nonisolated and hence more challenging for convergence analysis. The main results provide efficient conditions for local convergence to arbitrary local minimizers under the fulfillment of … Read more

Computational Methods for the Household Assignment Problem

We consider the household assignment problem as it occurs in the geo-referencing step of spatial microsimulation models. The resulting model is a maximum weight matching problem with additional side constraints. For real-world instances such as the one for the city of Trier in Germany, the number of binary variables exceeds 10^9, and the resulting instances … Read more

A General Framework for Sequential Batch-Testing

We consider sequential testing problems that involve a system of \(n\) stochastic components, each of which is either working or faulty with independent probability. The overall state of the system is a function of the state of its individual components, and the goal is to determine the system state by testing its components at the … Read more

Globally Convergent Derivative-Free Methods in Nonconvex Optimization with and without Noise

This paper addresses the study of nonconvex derivative-free optimization problems, where only information of either smooth objective functions or their noisy approximations is available. General derivative-free methods are proposed for minimizing differentiable (not necessarily convex) functions with globally Lipschitz continuous gradients, where the accuracy of approximate gradients is interacting with stepsizes and exact gradient values. … Read more