Congestion in large cities and populated areas is one of the major challenges in urban logistics, and should be addressed at different planning and operational levels. The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the well known Traveling Salesman Problem (TSP) where the travel times are not assumed to be constant along the … Read more
We study derivative-free constrained optimization problems and propose a trust-region method that builds linear or quadratic models around the best feasible and and around the best infeasible solutions found so far. These models are optimized within a trust region, and the progressive barrier methodology handles the constraints by progressively pushing the infeasible solutions toward the … Read more
In this paper, we study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: Given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined … Read more
In this paper, constraint and integer programming formulations are applied to solve Bandwidth Coloring Problem (BCP) and Bandwidth Multicoloring Problem (BMCP). The problems are modeled using distance geometry (DG) approaches, which are then used to construct the constraint programming formulation. The integer programming formulation is based on a previous formulation for the related Minimum Span … Read more
We consider a primal-dual potential reduction algorithm for nonlinear convex optimization problems over symmetric cones. The same complexity estimates as in the case of linear objective function are obtained provided a certain nonlinear system of equations can be solved with a given accuracy. This generalizes the result of K. Kortanek, F. Potra and Y.Ye. We … Read more
Quadratic programs (QP) with an indefinite Hessian matrix arise naturally in some direct optimal control methods, e.g. as subproblems in a sequential quadratic programming (SQP) scheme. Typically, the Hessian is approximated with a positive definite matrix to ensure having a unique solution; such a procedure is called \emph{regularization}. We present a novel regularization method tailored … Read more
This paper has the goal to propose a gradient and function sampling method that under special circumstances moves superlinearly to a minimizer of a general class of nonsmooth and nonconvex functions. We present global and local convergence theory with illustrative examples that corroborate and elucidate the theoretical results obtained along the manuscript. ArticleDownload View PDF
We provide a framework for computing the exact worst-case performance of any algorithm belonging to a broad class of oracle-based first-order methods for composite convex optimization, including those performing explicit, projected, proximal, conditional and inexact (sub)gradient steps. We simultaneously obtain tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this … Read more
In this work we present a branch-and-bound (B&B) framework for the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS) and the node-weighted Steiner tree problem (NWSTP). The main component of … Read more
In general, multistage stochastic optimization problems are formulated on the basis of continuous distributions describing the uncertainty. Such ”infinite” problems are practically impossible to solve as they are formulated and finite tree approximations of the underlying stochastic processes are used as proxies. In this paper, we demonstrate how one can find guaranteed bounds, i.e. finite … Read more