A flexible framework for Group Decision Support: WINGDSS version 3.0

A flexible framework for Group Decision Support on PCs in Microsoft Windows environment is presented. WINGDSS does not replace human judgment but highly supports the entire process of decision making, from problem structuring to post-decision analysis. The latest version of WINGDSS is a modular, open system with a dynamical connection to relational databases, an interpreter for defining problem specific evaluation procedures, a lot of interactive features from setting up the tree of criteria until the sensitivity analysis on individual/group ranking. By providing tools for recursively redefining the decision problem, WINGDSS helps the decision makers in achieving a result satisfactory to the whole group.Research supported in part by the Hungarian Foundation for Scientific Research, Grant No. 2568 and by the Hungarian National Committee for Technical Research and Development, Grant No. 93-97-67-0553.     

Necessary Conditions for Impulsive Nonlinear Optimal Control Problems without a priori Normality Assumptions

First-order and second-order necessary conditions of optimality for an impulsive control problem that remain informative for abnormal control processes are presented and derived. One of the main features of these conditions is that no a priori normality assumptions are required. This feature follows from the fact that these conditions rely on an extremal principle which is proved for an abstract minimization problem with equality constraints, inequality constraints, and constraints given by an inclusion in a convex cone. Two simple examples illustrate the power of the main result.The first author was partially supported by the Russian Foundation for Basic Research Grant 02-01-00334. The second author was partially supported by the Russian Foundation for Basic Research Grant 00-01-00869. The third author was partially supported by Fundacao para a Ciencia e Tecnologia and by INVOTAN Grant.     

On the solution of large,structured linear complementarity problems: The block partitioned case

This paper delineates the underlying theory of an efficient method for solving a class of specially-structured linear complementarity problems of potentially very large size. We propose a block-iterative method in which the subproblems are linear complementarity problems. Problems of the type considered here arise in the process of making discrete approximations to differential equations in the presence of special side conditions. This problem source is exemplified by the free boundary problem for finite-length journal bearings. Some of the authors' computational experience with the method is presented.Research partially supported by the Office of Naval Research under contract N-00014-67-A-0112-0011; U.S. Atomic Energy Commission Contract AT (04-3)-326 PA No. 18.Research partially supported by U.S. Atomic Energy Commission Contract AT(04-3)-326 PA No. 30; and National Science Foundation Grant GJ 35135X.     

The adjacency relation on the traveling salesman polytope is NP-Complete

We consider the problem of determining whether two traveling salesman tours correspond to non-adjacent vertices of the convex polytope associated with the traveling salesman problem. This problem is shown to be NP-Complete for both the symmetric and nonsymmetric traveling salesman problem. Several implications are discussed.This Research was supported by NSF Grant GK-420488, the U.S. Army Research Office-Durham under Grant DAHC04-75-G0192, and an IBM Fellowship.     

Combining Trust-Region Techniques and Rosenbrock Methods to Compute Stationary Points

Rosenbrock methods are popular for solving a stiff initial-value problem of ordinary differential equations. One advantage is that there is no need to solve a nonlinear equation at every iteration, as compared with other implicit methods such as backward difference formulas or implicit Runge–Kutta methods. In this article, we introduce a trust-region technique to select the time steps of a second-order Rosenbrock method for a special initial-value problem, namely, a gradient system obtained from an unconstrained optimization problem. The technique is different from the local error approach. Both local and global convergence properties of the new method for solving an equilibrium point of the gradient system are addressed. Finally, some promising numerical results are also presented. This research was supported in part by Grant 2007CB310604 from National Basic Research Program of China, and #DMS-0404537 from the United States National Science Foundation, and Grant #W911NF-05-1-0171 from the United States Army Research Office, and the Research Grant Council of Hong Kong.     

Optimal stopping,exponential utility,and linear programming

This paper uses linear programming to compute an optimal policy for a stopping problem whose utility function is exponential. This is done by transforming the problem into an equivalent one having additive utility and nonnegative (not necessarily substochastic) transition matrices.Research was supported by NSF Grant ENG 76-15599.     

An accelerated covering relaxation algorithm for solving 0–1 positive polynomial programs

The purpose of this note is to present an accelerated algorithm for solving 0–1 positive polynomial (PP) problems. Like our covering relaxation algorithm (Management Science 1979), the accelerated algorithm is a cutting plane method, which uses the linear set covering problem as a relaxation for PP. However, a unique and novel feature of the accelerated algorithm is that it attempts to generate cutting planes from heuristic solutions to the set covering problem whenever possible. Computational results reveal that this strategy of generating cutting planes has led to a significant reduction in the computational time required to solve a PP problem.This research was partially supported by National Sciences and Engineering Research Council Canada Grants 67-4181 and 67-3998, Office of Naval Research Contract N00014-76-C-0418, and National Science Foundation Grant ECS80-22027.     

A primal-dual approximation algorithm for generalized steiner network problems

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem. Ifk is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.Research supported by an NSF Graduate Fellowship, DARPA contracts N00014-91-J-1698 and N00014-92-J-1799, and AT&T Bell Laboratories.Research supported in part by Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.Part of this work was done while the author was visiting AT&T Bell Laboratories and Bellcore.     

$${\varvec{teaspoon}}$$ : solving the curriculum-based course timetabling problems with answer set programming

Annals of Operations Research - Answer Set Programming (ASP) is an approach to declarative problem solving, combining a rich yet simple modeling language with high performance solving capacities....     

Optimized location of light sources to cover a rectangular region

Central European Journal of Operations Research - The problem we considered was proposed by an industrial partner. The aim is to locate light sources around a rectangular field such that the areas...     

Selecting an agricultural technology package based on the flexible and interactive tradeoff method

Annals of Operations Research - The aim of this paper is to solve an agricultural technology packages selection problem by considering multiple dimensions which influence a maize producer’s...     

Multi-sample cluster analysis using Akaike's Information Criterion

Summary Multi-sample cluster analysis, the problem of grouping samples, is studied from an information-theoretic viewpoint via Akaike's Information Criterion (AIC). This criterion combines the maximum value of the likelihood with the number of parameters used in achieving that value. The multi-sample cluster problem is defined, and AIC is developed for this problem. The form of AIC is derived in both the multivariate analysis of variance (MANOVA) model and in the multivariate model with varying mean vectors and variance-covariance matrices. Numerical examples are presented for AIC and another criterion calledw-square. The results demonstrate the utility of AIC in identifying the best clustering alternatives. This research was supported by Office of Naval Research Contract N00014-80-C-0408, Task NR042-443 and Army Research Office Contract DAAG 29-82-K-0155, at the University of Illinois at Chicago.     

On the one-to-one pickup-and-delivery problem with time windows and trailers

Central European Journal of Operations Research - This paper studies an extension of the well-known one-to-one pickup-and-delivery problem with time windows. In the latter problem, requests to...     

Predictive modeling in a steelmaking process using optimized relevance vector regression and support vector regression

Annals of Operations Research - The existence of contaminants in metal alloys products is the main problem affecting the product quality, which is an important requirement for competitiveness in...     

Necessary Optimality Conditions for Problems with Equality and Inequality Constraints: Abnormal Case

This article concerns second-order necessary conditions for an abnormal local minimizer of a nonlinear optimization problem with equality and inequality constraints. The obtained optimality conditions improve the ones available in the literature in that the associated set of Lagrange multipliers is the smallest possible. The first and the second authors were supported by Russian Foundation of Basic Research, Projects 08-01-90267, 08-01-90001. The second and third authors were supported by FCT (Portugal), Research Projects SFRH/BPD/26231/2006, PTDC/EEA-ACR/75242/2006.     

Cost Optimized Design for the Local Wind Turbine Grid of an Onshore Wind Farm

Annals of Operations Research - This document analyses the problem of designing a minimum cost local wind turbine grid (or LWTG) for an onshore wind farm. The LWTG is responsible for adding up the...     

Scattering in a Forked-Shaped Waveguide

We consider wave scattering in a forked-shaped waveguide which consists of two finite and one half-infinite intervals having one common vertex. We describe the spectrum of the direct scattering problem and introduce an analogue of the Jost function. In case of the potential which is identically equal to zero on the half-infinite interval, the problem is reduced to a problem of the Regge type. For this case, using Hermite-Biehler classes, we give sharp results on the asymptotic behavior of resonances, that is, the corresponding eigenvalues of the Regge-type problem. For the inverse problem, we obtain sufficient conditions for a function to be the S-function of the scattering problem on the forked-shaped graph with zero potential on the half-infinite edge, and present an algorithm that allows to recover potentials on the finite edges from the corresponding Jost function. It is shown that the solution of the inverse problem is not unique. Some related general results in the spectral theory of operator pencils are also given. This work was supported by the grant UM1-2567-OD-03 from the Civil Research and Development Foundation (CRDF). YL was partially supported by the NSF grants 0338743, 0354339 and 0754705, by the Research Board and Research Council of the University of Missouri, and by the EU Marie Curie “Transfer of Knowledge” program.     

Linear pursuit-evasion games with bounded state spaces

The problem of linear pursuit-evasion games with bounded state spaces is considered. Some sufficient conditions for optimality are established, and an example is given.This research was carried out while the author was a Visiting Associate Research Engineer at the University of California at Berkeley. The research was supported by the Office of Naval Research, Grant No. N00014-69-A-0200-1012. The author would like to express his gratitude to Professor G. Leitmann for discussions and for making possible his visit at Berkeley.     

A note on the use of direct sufficient conditions in optimal control problems

It is always possible to transform a nonautonomous optimal control problem into an autonomous one. However, the direct sufficient conditions may yield no information when applied to this autonomous problem, even though they do allow one to conclude sufficiency when applied to the original nonautonomous problem.This research was supported by the Air Force Office of Scientific Research, under Grant No. AFOSR-76-2923.     

Quadratic programming with one negative eigenvalue is NP-hard

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Haijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.This author's work supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013. A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.