Linear programming based meta-heuristics for the weighted maximal planar graph

The weighted maximal planar graph (WMPG) is practically important in the laying out of facilities in modern manufacturing environments. Given a weighted complete graph, the WMPG seeks to find a sub-graph such that it is planar—it can be embedded on the plane without any arcs intersecting, and it is maximal—no additional arc can be added to the sub-graph without destroying its planarity, and it also has the maximal sum of arc weights. In this paper, an integer linear programming (ILP) model is newly introduced for the problem. Two meta-heuristics are then derived from the ILP relaxation. The first meta-heuristic considers all variables with fractional values greater than half in the ILP relaxation to build an initial sub-graph from which a planar sub-graph is extracted using greedy random adaptive search procedure (GRASP) and augmented by triangulation of faces. The second meta-heuristic considers only arcs with integer values in the ILP relaxation. The remaining arcs are then sorted in descending order of their weights, for selection and insertion with a planarity testing procedure, to obtain a feasible solution using GRASP. Computational results are reported on a set of 100 test instances of size varying from 20 to 100 facilities. The computational results demonstrate the tightness of the new upper bound when compared to the classical one as well as the good performance of the proposed metaheuristics when compared to the best-known procedures in the literature in terms of solution quality and computational requirement. Finally, the paper presents a successful integration of GRASP with classical optimisation approaches and should be attempted for other optimisation problems.     

Semi-definite programming techniques for structured quadratic inverse eigenvalue problems

In the past decade or so, semi-definite programming (SDP) has emerged as a powerful tool capable of handling a remarkably wide range of problems. This article describes an innovative application of SDP techniques to quadratic inverse eigenvalue problems (QIEPs). The notion of QIEPs is of fundamental importance because its ultimate goal of constructing or updating a vibration system from some observed or desirable dynamical behaviors while respecting some inherent feasibility constraints well suits many engineering applications. Thus far, however, QIEPs have remained challenging both theoretically and computationally due to the great variations of structural constraints that must be addressed. Of notable interest and significance are the uniformity and the simplicity in the SDP formulation that solves effectively many otherwise very difficult QIEPs.     

Linear complementarity problems and multiple objective programming

An equivalence is demonstrated between solving a linear complementarity problem with general data and finding a certain subset of the efficient points of a multiple objective programming problem. A new multiple objective programming based approach to solving linear complementarity problems is presented. Results on existence, uniqueness and computational complexity are included.     

Approximate dynamic programming for stochastic linear control problems on compact state spaces

This paper addresses Markov Decision Processes over compact state and action spaces. We investigate the special case of linear dynamics and piecewise-linear and convex immediate costs for the average cost criterion. This model is very general and covers many interesting examples, for instance in inventory management. Due to the curse of dimensionality, the problem is intractable and optimal policies usually cannot be computed, not even for instances of moderate size.     

Nonlinear programming using minimax techniques

A minimax approach to nonlinear programming is presented. The original nonlinear programming problem is formulated as an unconstrained minimax problem. Under reasonable restrictions, it is shown that a point satisfying the necessary conditions for a minimax optimum also satisfies the Kuhn-Tucker necessary conditions for the original problem. A leastpth type of objective function for minimization with extremely large values ofp is proposed to solve the problem. Several numerical examples compare the present approach with the well-known SUMT method of Fiacco and McCormick. In both cases, a recent minimization algorithm by Fletcher is used.This paper is based on work presented at the 5th Hawaii International Conference on System Sciences, Honolulu, Hawaii, 1972. The authors are greatly indebted to V. K. Jha for his programming assistance and J. H. K. Chen who obtained some of the numerical results. This work was supported in part by the National Research Council of Canada under Grant No. A7239, by a Frederick Gardner Cottrell Grant from the Research Corporation, and through facilities and support from the Communications Research Laboratory of McMaster University.     

Enhanced mixed integer programming techniques and routing problems

This is a summary of the author’s PhD thesis supervised by Andrea Lodi and Paolo Toth and defended on 16 April 2009 at the Università di Bologna. The thesis is written in English and is available from the author upon request. This work is focused on Mixed Integer Programming (MIP). In particular, the first part of the thesis deals with general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. The second part is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications.     

A large deviation theorem for weighted sums

Asymptotic representations are derived for large deviation probabilities of weighted sums of independent, identically distributed random variables. The main theorem generalizes a 1952 theorem of Chernoff which asserts that n ^–1 log P(S _n>cn)–log , where S _n is the partial sum of a sequence of independent, identically distributed random variables X ₁, X ₂, ... and is a constant depending on X ₁. The main result is similar in form to, but different in focus from, a particular case of Feller's (1969) theorem on large deviations for triangular arrays.This paper is based on work done for the author's doctoral dissertation written under Prof. Donald R. Truax of the University of Oregon, Eugene.     

Sensitivity method for basis inverse representation in multistage stochastic linear programming problems

A version of the simplex method for solving stochastic linear control problems is presented. The method uses a compact basis inverse representation that extensively exploits the original problem data and takes advantage of the supersparse structure of the problem. Computational experience indicates that the method is capable of solving large problems.This research was supported by Programs CPBP02.15 and RPI.02.     

Linear regression estimators for multinormal distributions in optimization of stochastic programming problems

Several linear regression estimators are presented, which approximate the distribution function of the m-dimensional normal distribution, or the distribution function along a line. These regression estimators are quadratic functions, or simple functions of quadratic functions and can be applied in numerical problems, arising during optimization of stochastic programming problems. A root finding procedure is developed, that can be used to find the intersection of a line and the border of the feasible set. Directional derivatives and gradient of the normal distribution can be computed. Some numerical results are also presented.     

Constructing an artificial basis in the symmetric linear programming problems

The constraint region of a symmetric LP problem is extended to a region with a known corner point constructed on the gradient of a linear form. The solution of the problem by the simplex method starts with the supporting program that corresponds to this corner point. The algorithm is proved, a bound on an approximate solution is obtained, and cases with an exact solution are identified.Khmel'nitskii Technological Institute of Consumer Services. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 67, pp. 106–113, 1989.     

Linear programming with multiple choice constraints for single chain undiscounted Markov decision problems

This paper develops an efficient LP algorithm for solving single chain undiscounted Markov decision problems. The algorithm imposes, in the framework of the simplex method, the multiple choice constraints that exactly one basic variable be chosen from each Markov state. It is proved that the algorithm converges to an optimal solution in a finite number of steps.     

Linear boundary value problems for systems of ordinary differential equations on non compact intervals

Sunto In guesta nota si esaminano la completa continuità e il rango dell'operatore integrale associate al sistema x – A(t)x=f(t, x Tx=r al variare del tipo di stabilità della parte lineare.     

Large deviation principles for sequences of logarithmically weighted means

In this paper we consider several examples of sequences of partial sums of triangular arrays of random variables {Xn:n?1}; in each case Xn converges weakly to an infinitely divisible distribution (a Poisson distribution or a centered Normal distribution). For each sequence we prove large deviation results for the logarithmically weighted means with speed function . We also prove a sample path large deviation principle for {Xn:n?1} defined by , where σ²∈(0,∞) and {Un:n?1} is a sequence of independent standard Brownian motions.     

Solving nonlinear principal-agent problems using bilevel programming

While significant progress has been made, analytic research on principal-agent problems that seek closed-form solutions faces limitations due to tractability issues that arise because of the mathematical complexity of the problem. The principal must maximize expected utility subject to the agent’s participation and incentive compatibility constraints. Linearity of performance measures is often assumed and the Linear, Exponential, Normal (LEN) model is often used to deal with this complexity. These assumptions may be too restrictive for researchers to explore the variety of relationships between compensation contracts offered by the principal and the effort of the agent. In this paper we show how to numerically solve principal-agent problems with nonlinear contracts. In our procedure, we deal directly with the agent’s incentive compatibility constraint. We illustrate our solution procedure with numerical examples and use optimization methods to make the problem tractable without using the simplifying assumptions of a LEN model. We also show that using linear contracts to approximate nonlinear contracts leads to solutions that are far from the optimal solutions obtained using nonlinear contracts. A principal-agent problem is a special instance of a bilevel nonlinear programming problem. We show how to solve principal-agent problems by solving bilevel programming problems using the ellipsoid algorithm. The approach we present can give researchers new insights into the relationships between nonlinear compensation schemes and employee effort.     

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider $N$ -fold $4$ -block decomposable integer programs, which simultaneously generalize $N$ -fold integer programs and two-stage stochastic integer programs with $N$ scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable  $N$ , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843–862,1990), which allows us to use convex continuous optimization as a subroutine.     

Gambling and curve-fitting problems using dynamic programming

In this paper, a racehorse problem and related problems are solved using dynamic programming. A special curve-fitting problem is discussed, and a method for solution is given. The treatment throughout is elementary and gives a fundamental discussion of dynamic programming with respect to a certain class of functional equations.     

Mixed-integer programming techniques for decomposing IMRT fluence maps using rectangular apertures

We consider a matrix decomposition problem arising in Intensity Modulated Radiation Therapy (IMRT). The problem input is a matrix of intensity values that are to be delivered to a patient via IMRT from some given angle, under the condition that the IMRT device can only deliver radiation in rectangular shapes. This paper studies the problem of minimizing the number of rectangles (and their associated intensities) necessary to decompose such a matrix. We propose an integer programming-based methodology for providing lower and upper bounds on the optimal solution, and demonstrate the efficacy of our approach on clinical data.     

Linear programming method for rational approximation

Development of a new algorithm, based on linear programming, for the computation of the best rational approximation of a continuous function.