We examine an extension of the Traveling Salesperson Problem (TSP), the so called TSP with Forbidden Neighborhoods (TSPFN). The TSPFN is asking for a shortest Hamiltonian cycle of a given graph, where vertices traversed successively have a distance larger than a given radius. This problem is motivated by an application in mechanical engineering, more precisely … Read more
In this paper we investigate the Locomotive Scheduling Problem, i.e., the optimization of locomotive utilization with prior known transports that must be performed. Since railway timetables are typically planned a year in advance, the aim is to assign locomotives to trains such that the locomotive utilization is maximized while maintenance constraints are taken into account. … Read more
This paper shows that the self-concordance parameter of the universal barrier on any n-dimensional proper convex domain is upper bounded by n. This bound is tight and improves the previous O(n) bound by Nesterov and Nemirovski. The key to our main result is a pair of new, sharp moment inequalities for s-concave distributions, which could … Read more
This paper is concerned with a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite constraint is relaxed, and the resultant mixed-integer linear optimization problem is repeatedly solved with valid inequalities for the relaxed constraint. We prove convergence properties of the algorithm. Moreover, to speed up the computation, we … Read more
We consider a lot-sizing problem in a single-item single-stage production system facing non-stationary stochastic demand in a nite planning horizon. Motivated by practice, the set-up times need to be deter- mined and frozen once and for all at the beginning of the horizon while decisions on the exact lot sizes can be deferred until the … Read more
The Douglas-Rachford algorithm is a classical and a successful method for solving the feasibility problems. Here, we provide a region for global convergence of the algorithm for the feasibility problem involving a disc and a circle in the Euclidean space of dimension two. Citation1. Borwein, J.M., Sims, B.: The Douglas-Rachford algorithm in the absence of … Read more
We propose a novel theoretical framework to investigate deep neural networks using the formalism of proximal fixed point methods for solving variational inequalities. We first show that almost all activation functions used in neural networks are actually proximity operators. This leads to an algorithmic model alternating firmly nonexpansive and linear operators. We derive new results … Read more
In the last two decades, many descent methods for multiobjective optimization problems were proposed. In particular, the steepest descent and the Newton methods were studied for the unconstrained case. In both methods, the search directions are computed by solving convex subproblems, and the stepsizes are obtained by an Armijo-type line search. As a consequence, the … Read more
We study cyclic binary strings with bounds on the lengths of the intervals of consecutive ones and zeros. This is motivated by scheduling problems where such binary strings can be used to represent the state (on/off) of a machine. In this context the bounds correspond to minimum and maximum lengths of on- or off-intervals, and … Read more
We establish a general computational framework for Chvátal’s conjecture based on exact rational integer programming. As a result we prove Chvátal’s conjecture holds for all downsets whose union of sets contains seven elements or less. The computational proof relies on an exact branch-and-bound certificate that allows for elementary verification and is independent of the integer … Read more