Maximum entropy reconstruction using derivative information part 2: computational results

Summary. Maximum entropy density estimation, a technique for reconstructing an unknown density function on the basis of certain measurements, has applications in various areas of applied physical sciences and engineering. Here we present numerical results for the maximum entropy inversion program based on a new class of information measures which are designed to control derivative values of the unknown densities. Received January 3, 1994 / Revised version received May 25, 1994     

Customer differentiated end-of-life inventory problem

This paper deals with the service parts end-of-life inventory problem in a circumstance that demands for service parts are differentiated. Customer differentiation might be due to criticality of the demand or based on various service contracts. In both cases, we model the problem as a finite horizon stochastic dynamic program and characterize the structure of the optimal inventory policy. We show that when customers are differentiated based on the demand criticality then the optimal structure consists of time and state dependent threshold levels for inventory rationing. In case of differentiation based on service contracts, we show that in addition to rationing thresholds we also need contract extension thresholds by which the system decides whether to offer an extension to an expiring contract or not. By numerical experiments in both cases, we identify the value of incorporating such decisions in service parts end-of-life inventory management with customer differentiation. Moreover, we show that these decisions not only result in cost efficiency but also decrease the risk of part obsolescence drastically.     

Alcohol consumption among college students: An agent‐based computational simulation

An agent‐based C++ program was developed to model student drinking. Student‐agents interact with each other and are randomly subjected to good or bad drinking experiences, to stories of other students' experiences, and to peer pressure. The program outputs drinking rates as functions of time based on various input parameters. The intent of this project is to simulate alcohol use, eventually adding other drugs, and possibly creating a simulation game for use as an educational tool. © 2008 Wiley Periodicals, Inc. Complexity, 2009     

Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion

We are given a set of parallel jobs that have to be executed on a set of speed-scalable processors varying their speeds dynamically. Running a job at a slower speed is more energy-efficient, however, it takes a longer time and affects the performance. Every job is characterized by the processing volume and the number or the set of the required processors. Our objective is to minimize the maximum completion time so that the energy consumption is not greater than a given energy budget. For various particular cases, we propose polynomial-time approximation algorithms, consisting of two stages. At the first stage, we give an auxiliary convex program. By solving this problem, we get processing times of jobs and a lower bound on the makespan. Then, at the second stage, we transform our problem into the corresponding scheduling problem with the constant speed of processors and construct a feasible schedule. We also obtain an “almost exact” solution for the preemptive settings based on a configuration linear program.

     

A GENERATOR AND A SIMPLEX SOLVER FOR NETWORK PIECEWISE LINEAR PROGRAMS

ＡＧＥＮＥＲＡＴＯＲＡＮＤＡＳＩＭＰＬＥＸＳＯＬＶＥＲＦＯＲＮＥＴＷＯＲＫＰＩＥＣＥＷＩＳＥＬＩＮＥＡＲＰＲＯＧＲＡＭＳＳＵＮＪＩＥ（孙捷）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉ...     

Lower Bounds for Measurable Chromatic Numbers

The Lovász theta function provides a lower bound for the chromatic number of finite graphs based on the solution of a semidefinite program. In this paper we generalize it so that it gives a lower bound for the measurable chromatic number of distance graphs on compact metric spaces. In particular we consider distance graphs on the unit sphere. There we transform the original infinite semidefinite program into an infinite linear program which then turns out to be an extremal question about Jacobi polynomials which we solve explicitly in the limit. As an application we derive new lower bounds for the measurable chromatic number of the Euclidean space in dimensions 10, . . . , 24 and we give a new proof that it grows exponentially with the dimension.     

Efficient Solution of a Class of Quantified Constraints with Quantifier Prefix Exists-Forall

In various applications the search for certificates for certain properties (e.g., stability of dynamical systems, program termination) can be formulated as a quantified constraint solving problem with quantifier prefix exists-forall. In this paper, we present an algorithm for solving a certain class of such problems based on interval techniques in combination with conservative linear programming approximation. In comparison with previous work, the method is more general—allowing general Boolean structure in the input constraint, and more efficient—using splitting heuristics that learn from the success of previous linear programming approximations.     

Complementarity Constraint Qualifications and Simplified B-Stationarity Conditions for Mathematical Programs with Equilibrium Constraints

With the aid of some novel complementarity constraint qualifications, we derive some simplified primal-dual characterizations of a B-stationary point for a mathematical program with complementarity constraints (MPEC). The approach is based on a locally equivalent piecewise formulation of such a program near a feasible point. The simplified results, which rely heavily on a careful dissection and improved understanding of the tangent cone of the feasible region of the program, bypass the combinatorial characterization that is intrinsic to B-stationarity.     

Some algorithms for semi-invariants of quivers

We present some theorems and algorithms for calculating perpendicular categories and locally semi-simple decompositions. We implemented a computer program TETIVA based on these algorithms and we offer this program for everybody's use.     

一类改进的灰色预测型线性规划

根据基于GM（1，1）模型的预测型线性规划思想方法，建立了中心逼近式GM（1，1）模型，从而给出对灰色预测型线性规划的改进。     

Two-phase flow modeling for low concentration spherical particle motion through a Newtonian fluid

Models that are used for the simulation of two-phase flows in coastal dynamics make extensive use of empirical data. The main focus of this investigation is to develop models for specific aspects of two-phase flows that are based on physical principles in order to reduce the use of such data. In this study several existing empirically based drag force models are discussed. The motion of spherical or near-spherical solid particles through a Newtonian fluid is investigated and a new method for closure of the drag force, using a Representative Unit Cell is discussed and compared to the existing models as well as to experimental data. The various drag models were also evaluated by numerical simulations, using an in-house developed program based on an adaptation of the SIMPLE procedure.     

Mathematical Programming with System of Equilibrium Constraints

In this paper, we study the mathematical program with system of equilibrium constraints. This problem contains bilevel program with system of equilibrium constraints, semi-infinite program with system of equilibrium constraints, mathematical program with Nash equilibrium constraints, mathematical program with system of mixed variational like inequalities constraints. We establish the existence theorems of mathematical program with system of equilibrium constraints under various assumptions.     

Global optimization of nonconvex factorable programming problems

In this paper, we consider a special class of nonconvex programming problems for which the objective function and constraints are defined in terms of general nonconvex factorable functions. We propose a branch-and-bound approach based on linear programming relaxations generated through various approximation schemes that utilize, for example, the Mean-Value Theorem and Chebyshev interpolation polynomials coordinated with a Reformulation-Linearization Technique (RLT). A suitable partitioning process is proposed that induces convergence to a global optimum. The algorithm has been implemented in C++ and some preliminary computational results are reported on a set of fifteen engineering process control and design test problems from various sources in the literature. The results indicate that the proposed procedure generates tight relaxations, even via the initial node linear program itself. Furthermore, for nine of these fifteen problems, the application of a local search method that is initialized at the LP relaxation solution produced the actual global optimum at the initial node of the enumeration tree. Moreover, for two test cases, the global optimum found improves upon the solutions previously reported in the source literature. Received: January 14, 1998 / Accepted: June 7, 1999?Published online December 15, 2000     

Automated code generation by local search

There are many successful evolutionary computation techniques for automatic program generation, with the best known, perhaps, being genetic programming. Genetic programming has obtained human competitive results, even infringing on patented inventions. The majority of the scientific literature on automatic program generation employs such population-based search approaches, to allow a computer system to search a space of programs. In this paper, we present an alternative approach based on local search. There are many local search methodologies that allow successful search of a solution space, based on maintaining a single incumbent solution and searching its neighbourhood. However, use of these methodologies in searching a space of programs has not yet been systematically investigated. The contribution of this paper is to show that a local search of programs can be more successful at automatic program generation than current nature inspired evolutionary computation methodologies.     

A finite algorithm for the least two-norm solution of a linear program 1

By perturbing properly a linear program to a separable quadratic program it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overtaxation techniques). In this way large sparse linear programs can be handled.

In this paper we give a new computational criterion to check whether the solution of the perturbed quadratic program provides the least 2-norm solution of the original linear program. This criterion improves on the criterion proposed in an earlier paper.

We also describe an algorithm for solving linear programs which is based on the SOR methods. The main property of this algorithm is that, under mild assumptions, it finds the least 2-norm solution of a linear program in a finite number of iteration.s     

Bounds for the cup-length of Poincaré spaces and their applications

Our main result offers a new (quite systematic) way of deriving bounds for the cup-length of Poincaré spaces over fields; we outline a general research program based on this result. For the oriented Grassmann manifolds, already a limited realization of the program leads, in many cases, to the exact values of the cup-length and to interesting information on the Lyusternik-Shnirel'man category.     

A statistical analysis of an algorithm's complexity

In doing the statistical analysis of bubble sort program, we compute its execution times with various parameters. The statistical analysis endorses the specific quadratic pattern of the execution time on the number of items to be sorted. Next, a cursor along the future direction is indicated.     

Problem-based optimal scenario generation and reduction in stochastic programming

Scenarios are indispensable ingredients for the numerical solution of stochastic programs. Earlier approaches to optimal scenario generation and reduction are based on stability arguments involving distances of probability measures. In this paper we review those ideas and suggest to make use of stability estimates based only on problem specific data. For linear two-stage stochastic programs we show that the problem-based approach to optimal scenario generation can be reformulated as best approximation problem for the expected recourse function which in turn can be rewritten as a generalized semi-infinite program. We show that the latter is convex if either right-hand sides or costs are random and can be transformed into a semi-infinite program in a number of cases. We also consider problem-based optimal scenario reduction for two-stage models and optimal scenario generation for chance constrained programs. Finally, we discuss problem-based scenario generation for the classical newsvendor problem.

     

Privacy-preserving vertically partitioned linear program with nonnegativity constraints

We propose a simple privacy-preserving reformulation of a linear program with inequality constraints and nonnegativity constraints. By employing two random matrix transformation we construct a secure linear program based on the privately held data without revealing that data. The secure linear program has the same minimum value as the original linear program. Component groups of the solution of the transformed problem can be decoded and made public only by the original group that owns the corresponding columns of the constraint matrix and can be combined to give an exact solution vector of the original linear program.     

Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem

Necessary and sufficient conditions are established for the convergence of various iterative methods for solving the linear complementarity problem. The fundamental tool used is the classical notion of matrix splitting in numerical analysis. The results derived are similar to some well-known theorems on the convergence of iterative methods for square systems of linear equations. An application of the results to a strictly convex quadratic program is also given.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571.The author gratefully acknowledges several comments by K. Truemper on the topics of this paper.