A variety of formulations for the Travelling Salesman Problem as Mixed Integer Program have been proposed. They contain either non-binary variables or the number of constraints and variables is large. We want to give a new formulation that consists solely of binary variables; the number of variables and the number of constraints are of order … Read more
We present pure-integer Gomory cuts in a way so that they are derived with respect to a “dual form” pure-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. The input integer problem is not in standard form, and so the cuts are derived a bit differently. In … Read more
This paper is concerned with completely positive and semidefinite relaxations of quadratic programs with linear constraints and binary variables as presented by Burer. It observes that all constraints of the relaxation associated with linear constraints of the original problem can be accumulated in a single linear constraint without changing the feasible set of either the … Read more
This paper studies $K$-sublinear inequalities, a class of inequalities with strong relations to K-minimal inequalities for disjunctive conic sets. We establish a stronger result on the sufficiency of $K$-sublinear inequalities. That is, we show that when $K$ is the nonnegative orthant or the second-order cone, $K$-sublinear inequalities together with the original conic constraint are always … Read more
In recent years the expansion of energy supplies from volatile renewable sources has triggered an increased interest in stochastic optimization models for hydro-thermal unit commitment. Several studies have modelled this as a two-stage or multi-stage stochastic mixed-integer optimization problem. Solving such problems directly is computationally intractable for large instances, and alternative approaches are required. In … Read more
A direct-search derivative-free Matlab optimizer for bound-constrained problems is described, whose remarkable features are its ability to handle a mix of continuous and discrete variables, a versatile interface as well as a novel self-training option. Its performance compares favourably with that of NOMAD, a state-of-the art package. It is also applicable to multilevel equilibrium- or … Read more
The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this paper we … Read more
The pollution routing problem (PRP) aims to determine a set of routes and speed over each leg of the routes simultaneously to minimize the total operational and environmental costs. A common approach to solve the PRP exactly is through speed discretization, i.e., assuming that speed over each arc is chosen from a prescribed set of … Read more
We consider a combinatorial optimization problem for spatial information cloaking. The problem requires to compute one or several disjoint arborescences on a graph from a predetermined root or subset of candidate roots, so that the number of vertices in the arborescences is minimized but a given threshold on the overall weight associated with the vertices … Read more
Expansion of natural gas networks is a critical process involving substantial capital expenditures with complex decision-support requirements. Given the non-convex nature of gas transmission constraints, global optimality and infeasibility guarantees can only be offered by global optimisation approaches. Unfortunately, state-of-the-art global optimisation solvers are unable to scale up to real-world size instances. In this study, … Read more