Locally unique solutions of quadratic programs,linear and nonlinear complementarity problems

It is shown that McCormick's second order sufficient optimality conditions are also necessary for a solution to a quadratic program to be locally unique and hence these conditions completely characterize a locally unique solution of any quadratic program. This result is then used to give characterizations of a locally unique solution to the linear complementarity problem. Sufficient conditions are also given for local uniqueness of solutions of the nonlinear complementarity problem.Research supported by National Science Foundation Grant MCS74-20584 A02.     

On the symmetric travelling salesman problem II: Lifting theorems and facets

Four lifting theorems are derived for the symmetric travelling salesman polytope. They provide constructions and state conditions under which a linear inequality which defines a facet of then-city travelling salesman polytope retains its facetial property for the (n + m)-city travelling salesman polytope, wherem 1 is an arbitrary integer. In particular, they permit a proof that all subtour-elimination as well as comb inequalities define facets of the convex hull of tours of then-city travelling salesman problem, wheren is an arbitrary integer.     

Home Care optimization: impact of pattern generation policies on scheduling and routing decisions

In Home Care optimization, operators have to be assigned to patients by taking into account compatibility skill constraints, and patient visits have to be scheduled in a given planning horizon. Moreover, operator tours have to be determined. Integer Linear Programming models have been proposed which use the concept of patterns, i.e. a priori scheduling profiles, to combine the diverse decision levels. Computational results on real instances show that pattern generation policies are crucial to address scheduling and routing in large Home Care instances.     

Random Hermite differential equations: Mean square power series solutions and statistical properties

This paper deals with the construction of random power series solution of second order linear differential equations of Hermite containing uncertainty through its coefficients and initial conditions. Under appropriate hypotheses on the data, we establish that the constructed random power series solution is mean square convergent. We provide conditions in order to obtain random polynomial solutions and, as a consequence, random Hermite polynomial are introduced. Also, the main statistical functions of the approximate stochastic process solution generated by truncation of the exact power series solution are given. Finally, we apply the proposed technique to several illustrative examples comparing the numerical results with respect to those provided by other available approaches including Monte Carlo simulation.     

Random walks,totally unimodular matrices,and a randomised dual simplex algorithm

We discuss the application of random walks to generating a random basis of a totally unimodular matrix and to solving a linear program with such a constraint matrix. We also derive polynomial upper bounds on the combinatorial diameter of an associated polyhedron.Supported by NATO grant RG0088/89.Corresponding author. Supported by NSF grants CCR-8900112, CCR-9024935 and NATO grant RG0088/89.     

Random fractal strings: Their zeta functions, complex dimensions and spectral asymptotics

In this paper a string is a sequence of positive non-increasing real numbers which sums to one. For our purposes a fractal string is a string formed from the lengths of removed sub-intervals created by a recursive decomposition of the unit interval. By using the so-called complex dimensions of the string, the poles of an associated zeta function, it is possible to obtain detailed information about the behaviour of the asymptotic properties of the string. We consider random versions of fractal strings. We show that by using a random recursive self-similar construction, it is possible to obtain similar results to those for deterministic self-similar strings. In the case of strings generated by the excursions of stable subordinators, we show that the complex dimensions can only lie on the real line. The results allow us to discuss the geometric and spectral asymptotics of one-dimensional domains with random fractal boundary.

     

A stochastic aggregate production planning model in a green supply chain: Considering flexible lead times,nonlinear purchase and shortage cost functions

In this paper we develop a stochastic programming approach to solve a multi-period multi-product multi-site aggregate production planning problem in a green supply chain for a medium-term planning horizon under the assumption of demand uncertainty. The proposed model has the following features: (i) the majority of supply chain cost parameters are considered; (ii) quantity discounts to encourage the producer to order more from the suppliers in one period, instead of splitting the order into periodical small quantities, are considered; (iii) the interrelationship between lead time and transportation cost is considered, as well as that between lead time and greenhouse gas emission level; (iv) demand uncertainty is assumed to follow a pre-specified distribution function; (v) shortages are penalized by a general multiple breakpoint function, to persuade producers to reduce backorders as much as possible; (vi) some indicators of a green supply chain, such as greenhouse gas emissions and waste management are also incorporated into the model. The proposed model is first a nonlinear mixed integer programming which is converted into a linear one by applying some theoretical and numerical techniques. Due to the convexity of the model, the local solution obtained from linear programming solvers is also the global solution. Finally, a numerical example is presented to demonstrate the validity of the proposed model.     

Random point fields associated with certain Fredholm determinants I: fermion, Poisson and boson point processes

We introduce certain classes of random point fields, including fermion and boson point processes, which are associated with Fredholm determinants of certain integral operators and study some of their basic properties: limit theorems, correlation functions, Palm measures etc. Also we propose a conjecture on an α-analogue of the determinant and permanent.     

Objective function and logarithmic barrier function properties in convex programming: level sets,solution attainment and strict convexity *

We give several results, some new and some old, but apparently overlooked, that provide useful characterizations of barrier functions and their relationship to problem function properties. In particular, we show that level sets of a barrier function are bounded if and only if feasible level sets of the objective function are bounded and we obtain conditions that imply solution existence, strict convexity or a positive definite Hessian of a barrier function. Attention is focused on convex programs and the logarithmic barrier function. Such results suggest that it would seem possible to extend many recent complexity results by relaxing feasible set compactness to the feasible objective function level set boundedness assumption.