Efficient operation of underground railway systems is critical not only for maintaining punctual service but also for minimizing energy consumption, a key factor in reducing operational costs and environmental impact. To evaluate the energy consumption of the timetables, this paper delves into the development of mathematical models to accurately represent energy dynamics within the underground … Read more
We report on results concerning the polyhedral structure of, and integer linear programming formulations for, the quadratic linear ordering problem. Specifically, we provide a deeper analysis of the characteristic equation system that takes part in the minimal description of the convex hull of its feasible solutions, and we determine an accessible description of a restricted … Read more
We introduce a new class of valid inequalities for any 0/1 knapsack polytope, called Solitary item inequality, which are facet-defining. We prove that any facet-defining inequality of a 0/1 knapsack polytope with nonnegative integral coefficients and right hand side 1 belongs to this class, and hence, the set of facet-defining inequalities corresponding to strong covers … 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
University students benefit academically, personally and professionally from an expansion of their in-class social network. To facilitate this, we present a novel and broadly applicable optimization approach that exposes individuals to as many as possible peers that they do not know. This novel class of ‘social seating assignment problems’ is parameterized by the social network, … Read more
In this paper, a sequential adaptive regularization algorithm using cubics (ARC) is presented to solve nonlinear equality constrained optimization. It is motivated by the idea of handling constraints in sequential quadratic programming methods. In each iteration, we decompose the new step into the sum of the normal step and the tangential step by using composite … Read more
The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in Nesterov and Polyak (2006) and Cartis, Gould and Toint (2011) to require, under standard assumptions, at most O(\epsilon^{3/(3-q)}) evaluations of the objective function and its derivatives of degrees one and two to produce an \epsilon-approximate critical point of order q in {1,2}. This bound … Read more
The b-matching problem is a well-known generalization of the classical matching problem with various applications in operations research and computer science. Given an undirected graph, each vertex v has a capacity b(v), indicating the maximum number of times it can be matched, while edges can also be used multiple times. The problem is solvable in … 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