\(\) We consider the theoretical computational complexity of finding locally optimal solutions to bilevel linear optimization problems (BLPs), from the leader’s perspective. We show that, for any constant \(c > 0\), the problem of finding a leader’s solution that is within Euclidean distance \(c^n\) of any locally optimal leader’s solution, where \(n\) is the total … Read more
We present column elimination as a general framework for solving (large-scale) integer programming problems. In this framework, solutions are represented compactly as paths in a directed acyclic graph. Column elimination starts with a relaxed representation, that may contain infeasible paths, and solves a constrained network flow over the graph to find a solution. It then … Read more
Log-det semidefinite programming (SDP) problems are optimization problems that often arise from Gaussian graphic models. A log-det SDP problem with an l1-norm term has been examined in many methods, and the dual spectral projected gradient (DSPG) method by Nakagaki et al.~in 2020 is designed to efficiently solve the dual problem of the log-det SDP by … 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 report on results concerning the polyhedral structure of the quadratic linear ordering problem and its associated integer linear programming formulations. Specifically, we provide a deeper analysis of the characteristic equation system that partly describes the corresponding polytope, i.e., the convex hull of the feasible solutions to the quadratic linear ordering problem, and determine an … Read more
In the Vehicle Routing Problem (VRP) with Lockers, the vertices in a graph are divided into two key subsets: a customer set and a locker set, with lockers serving as alternative delivery points for the customer’s parcel. This paper presents a generic VRP with lockers, where a customer’s parcel can be delivered either to its … Read more
This tutorial provides an introduction to the use of decision diagrams for solving discrete optimization problems. A decision diagram is a graphical representation of the solution space, representing decisions sequentially as paths from a root node to a target node. By merging isomorphic subgraphs (or equivalent subproblems), decision diagrams can compactly represent an exponential solution … Read more
The most successful approaches for the TSP use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder: What is the … Read more
The maximum-entropy sampling problem (MESP) aims to select the most informative principal submatrix of a prespecified size from a given covariance matrix. This paper proposes an augmented factorization bound for MESP based on concave relaxation. By leveraging majorization and Schur-concavity theory, we demonstrate that this new bound dominates the classic factorization bound of Nikolov (2015) and a recent … 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