The “sequential ordering problem” (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernández & Salazar introduced a “multi-commodity flow” (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables … Read more
We develop a new constraint-reduced infeasible predictor-corrector interior point method for semidefinite programming, and we prove that it has polynomial global convergence and superlinear local convergence. While the new algorithm uses HKM direction in predictor step, it adopts AHO direction in corrector step to obtain faster approach to the central path. In contrast to the … Read more
We consider the linear or quadratic 0/1 program \[P:\quad f^*=\min\{ c^Tx+x^TFx : \:A\,x =\b;\:x\in\{0,1\}^n\},\] for some vectors $c\in R^n$, $b\in Z^m$, some matrix $A\in Z^{m\times n}$ and some real symmetric matrix $F\in R^{n\times n}$. We show that $P$ can be formulated as a MAX-CUT problem whose quadratic form criterion is explicit from the data of … Read more
We present global convergence rates for a line-search method which is based on random first-order models and directions whose quality is ensured only with certain probability. We show that in terms of the order of the accuracy, the evaluation complexity of such a method is the same as its counterparts that use deterministic accurate models; … Read more
We present a new algorithm for optimizing a linear function over the set of efficient solutions of a multiobjective integer program MOIP. The algorithm’s success relies on the efficiency of a new algorithm for enumerating the nondominated points of a MOIP, which is the result of employing a novel criterion space decomposition scheme which (1) … Read more
Constraint reduction is an essential method because the computational cost of the interior point methods can be effectively saved. Park and O’Leary proposed a constraint-reduced predictor-corrector algorithm for semidefinite programming with polynomial global convergence, but they did not show its superlinear convergence. We first develop a constraint-reduced algorithm for semidefinite programming having both polynomial global … Read more
A key step in solving minimax distributionally robust optimization (DRO) problems is to reformulate the inner maximization w.r.t. probability measure as a semiinfinite programming problem through Lagrange dual. Slater type conditions have been widely used for zero dual gap when the ambiguity set is defined through moments. In this paper, we investigate effective ways for … Read more
Non-convex quadratic programming with box constraints is a fundamental problem in the global optimization literature, being one of the simplest NP-hard nonlinear programs. We present a new heuristic for this problem, which enables one to obtain solutions of excellent quality in reasonable computing times. The heuristic consists of four phases: binarisation, convexification, branch-and-bound, and local … Read more
In a Hilbert space setting, we study the stability properties of the regularized continuous Newton method with two potentials, which aims at solving inclusions governed by structured monotone operators. The Levenberg-Marquardt regularization term acts in an open loop way. As a byproduct of our study, we can take the regularization coefficient of bounded variation. These … Read more
This paper gives a straightforward implementation of simulated annealing for solving maximum cut problems and compares its performance to that of some existing heuristic solvers. The formulation used is classical, dating to a 1989 paper of Johnson, Aragon, McGeoch, and Schevon. This implementation uses no structure peculiar to the maximum cut problem, but its low … Read more