We consider two variants of the toll-setting problem in which a traffic authority uses tolls either to maximize revenue or to alleviate bottlenecks in the traffic network. The users of the network are assumed to act according to Wardrop’s user equilibrium so that the overall toll-setting problems are modeled as mathematical problems with equilibrium constraints. … Read more
In binary polynomial optimization, the goal is to find a binary point maximizing a given polynomial function. In this paper, we propose a novel way of formulating this general optimization problem, which we call factorized binary polynomial optimization. In this formulation, we assume that the variables are partitioned into a fixed number of sets, and … Read more
The Standard Quadratic optimization Problem (StQP), arguably the simplest among all classes of NP-hard optimization problems, consists of extremizing a quadratic form (the simplest nonlinear polynomial) over the standard simplex (the simplest polytope/compact feasible set). As a problem class, StQPs may be nonconvex with an exponential number of inefficient local solutions. StQPs arise in a … Read more
We consider approaches for optimally organizing competitive sports leagues in light of competitive and logistical considerations. A common objective is to assign teams to divisions so that intradivisional travel is minimized. We present a bilinear programming formulation based on k-way equipartitioning, and show how this formulation can be extended to account for additional constraints and … Read more
A key factor towards a low-carbon society is energy efficient heating of private houses. The choice of heating technology as well as the decision for certain energy-efficient house renovations are made mainly by individual homeowners. In contrast, municipal energy network planning heavily depends on and strongly affects these decisions. Further, there are different conflicting objectives … Read more
Symmetries in mixed-integer (nonlinear) programs (MINLP), if not handled appropriately, are known to negatively impact the performance of (spatial) branch-and-bound algorithms. Usually one thus tries to remove symmetries from the problem formulation or is relying on a solver that automatically detects and handles symmetries. While modelers of a problem can handle various kinds of symmetries, … Read more
Robust optimization is an approach for handling uncertainty in optimization problems, in which the uncertainty set determines the conservativeness of the solutions. In this paper, we propose a data-driven uncertainty set using a type of volume-based clustering, which we call Minimum-Volume Norm-Based Clustering (MVNBC). MVNBC extends the concept of minimum-volume ellipsoid clustering by allowing clusters … Read more
This paper investigates convex quadratic optimization problems involving $n$ indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix $Q$ defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this … Read more
For continuous decision spaces, nonlinear programs (NLPs) can be efficiently solved via sequential quadratic programming (SQP) and, more generally, sequential convex programming (SCP). These algorithms linearize only the nonlinear equality constraints and keep the outer convex structure of the problem intact, such as (conic) inequality constraints or convex objective terms. The aim of the presented … Read more
In this paper, we consider convex quadratic optimization problems with indicators on the continuous variables. In particular, we assume that the Hessian of the quadratic term is a Stieltjes matrix, which naturally appears in sparse graphical inference problems and others. We describe an explicit convex formulation for the problem by studying the Stieltjes polyhedron arising … Read more