We study constant-factor approximation algorithms for the Bin Packing Problem with Setups (BPPS). First, we show that adaptations of classical BPP heuristics can have arbitrarily poor worst-case performance on BPPS instances. Then, we propose a two-phase heuristic for the BPPS that applies an α-approximation algorithm for the BPP to the items of each class and … Read more
We consider the problem of maximizing a monotone increasing, normalized, and submodular function defined on a set of weighted items under a knapsack constraint. A well-known greedy algorithm, analyzed by Wolsey (1982), achieves an approximation factor of \(0.357\) for this problem. This greedy algorithm starts with an empty solution set and iteratively generates a feasible … Read more
We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classical problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution’s cardinality. If any deleted elements were part … Read more
A new method for finding closed-loop optimal controllers of fractional tracking quadratic optimal control problems is introduced. The optimality conditions for the fractional optimal control problem are obtained. Illustrative examples are presented to show the applicability and capabilities of the method. ArticleDownload View PDF
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
This paper interfaces combinatorial integral approximation strategies with the inherent robustness properties of conventional model predictive control with stabilizing terminal conditions to establish practical asymptotic stability results for finite-control set and mixed-integer model predictive control. We examine the impact of sequential control rounding on the closed-loop performance in terms of stability and optimality. Sum-up rounding … Read more
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
Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-round strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, we derive a semidefinite relaxation and a randomized rounding scheme that obtains provably near-optimal solutions, building on the blueprint from Goemans and Williamson for the Max-Cut problem. … Read more
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
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