We present a lagrangean heuristic based on the time-indexed formulation of the Single Machine Scheduling Problem with Release Dates. We observe that lagrangian relaxation of job constraints leads to a Weighted Stable Set problem on an Interval Graph. The problem is polynomially solvable by a dynamic programming algorithm. Computational experience is reported on instances up … Read more
Non-smoothness and non-convexity in optimization problems often arise because a combinatorial structure is imposed on smooth or convex data. The combinatorial aspect can be explicit, e.g. through the use of ”max”, ”min”, or ”if” statements in a model, or implicit as in the case of bilevel optimization where the combinatorial structure arises from the possible … Read more
In one of fundamental work in combinatorial optimization Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets its line graph. Also the neighborhood of any vertex in a line graph partitions into two cliques: graphs with this latter property are called quasi-line graphs. Quasi-line graphs … Read more
This paper presents a small example for which the Penalty Interior Point Method converges to a non-stationary point. The reasons for this adverse behaviour are discussed. CitationNumerical Analysis Report NA/208, Department of Mathematics, University of Dundee, February 2002.ArticleDownload View PDF
Recently, it has been shown that Nonlinear Programming solvers can successfully solve a range of Mathematical Programs with Equilibrium Constraints (MPECs). In particular, Sequential Quadratic Programming (SQP) methods have been very successful. This paper examines the local convergence properties of SQP methods applied to MPECs. It is shown that SQP converges superlinearly under reasonable assumptions … Read more
We describe developments associated with Version 4 of the NEOS Server and note that these developments have led to an exponential growth in the number of job submissions. We also provide an overview of some of the research and educational uses for the NEOS Server and discuss future research challenges. CitationPreprint ANL/MCS-P947-0202, Argonne National Laboratory … Read more
$T$-algebras are non-associative algebras defined by Vinberg in the early 1960’s for the purpose of studying homogeneous cones. Vinberg defined a cone $K(\mathcal A)$ for each $T$-algebra $\mathcal A$ and proved that every homogeneous cone is isomorphic to one such $K(\mathcal A)$. We relate each $T$-algebra $\mathcal A$ with a space of linear operators in … Read more
We build upon the work of Fukuda et al.\ \cite{FuKoMuNa01} and Nakata et al.\ \cite{NaFuFuKoMu01}, in which the theory of partial positive semidefinite matrices has been applied to the semidefinite programming (SDP) problem as a technique for exploiting sparsity in the data. In contrast to their work, which improves an existing algorithm that is based … Read more
We introduce a computer program PENNON for the solution of problems of convex Nonlinear and Semidefinite Programming (NLP-SDP). The algorithm used in PENNON is a generalized version of the Augmented Lagrangian method, originally introduced by Ben-Tal and Zibulevsky for convex NLP problems. We present generalization of this algorithm to convex NLP-SDP problems, as implemented in … Read more
We address the feasibility of the pair of alternative conic systems of constraints Ax = 0, x \in C, and -A^T y \in C^*, defined by an m by n matrix A and a cone C in the n-dimensional Euclidean space. We reformulate this pair of conic systems as a primal-dual pair of conic programs. … Read more