The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. … Read more

Polynomial interior point cutting plane methods

Polynomial cutting plane methods based on the logarithmic barrier function and on the volumetric center are surveyed. These algorithms construct a linear programming relaxation of the feasible region, find an appropriate approximate center of the region, and call a separation oracle at this approximate center to determine whether additional constraints should be added to the … Read more

Facets of The Cardinality Constrained Circuit Polytope

The Cardinality Constrained Circuit Problem (CCCP) is the problem of finding a minimum cost circuit in a graph where the circuit is constrained to have at most $k$ edges. The CCCP is NP-Hard. We present classes of facet-inducing inequalities for the convex hull of feasible circuits. Article Download View Facets of The Cardinality Constrained Circuit … Read more

A comparison of the Sherali-Adams, Lov\’asz-Schrijver and Lasserre relaxations for sh-1$ programming

Sherali and Adams \cite{SA90}, Lov\’asz and Schrijver \cite{LS91} and, recently, Lasserre \cite{Las01b} have proposed lift and project methods for constructing hierarchies of successive linear or semidefinite relaxations of a $0-1$ polytope $P\subseteq \oR^n$ converging to $P$ in $n$ steps. Lasserre’s approach uses results about representations of positive polynomials as sums of squares and the dual … Read more

Augmented self-concordant barriers and nonlinear optimization problems with finite complexity.

In this paper we study special barrier functions for the convex cones, which are the sum of a self-concordant barrier for the cone and a positive-semidefinite quadratic form. We show that the central path of these augmented barrier functions can be traced with linear speed. We also study the complexity of finding the analytic center … Read more

Solving large MINLPs on computational grids

We consider the solution of Mixed Integer Nonlinear Programming (MINLP) problems by a parallel implementation of nonlinear branch-and-bound on a computational grid or meta-computer. Computational experience on a set of large MINLPs is reported which indicates that this approach is efficient for the solution of large MINLPs. Citation Numerical Analysis Report NA/200, Department of Mathematics, … Read more

The Integration of an Interior-Point Cutting-Plane Method within a Branch-and-Price Algorithm

This paper presents a novel integration of interior point cutting plane methods within branch-and-price algorithms. Unlike the classical method, columns are generated at a “central” dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce improvements to ACCPM. We propose a new procedure … Read more

Pattern search algorithms for mixed variable programming

Many engineering optimization problems involve a special kind of discrete variable that {\em can} be represented by a number, but this representation has no significance. Such variables arise when a decision involves some situation like a choice from an unordered list of categories. This has two implications: The standard approach of solving problems with continuous … Read more

Mixed variable optimization of the number and composition of heat intercepts in a thermal insulation system

In the literature, thermal insulation systems with a fixed number of heat intercepts have been optimized with respect to intercept locations and temperatures. The number of intercepts and the types of insulators that surround them were chosen by parametric studies. This was because the optimization methods used could not treat such categorical variables. Discrete optimization … Read more