Search

LU and Cholesky matrix factorization algorithms are core subroutines used to solve systems of linear equations (SLEs) encountered when solving an optimization problem. Standard floating-point algorithms are highly efficient but remain susceptible to the accumulation of round-off errors, which can lead solvers to return feasibility and optimality claims that are actually invalid. This paper introduces a novel direct solution approach for solving sequences of closely related SLEs encountered in nonlinear programming efficiently and without round-off errors. Specifically, it introduces rank-one update algorithms for the round-off error–free factorization framework, a tool set built on integer-preserving arithmetic that has led to the development and implementation of extremely reliable subroutines for solving SLEs occurring in linear programming. The formal guarantees of the presented algorithms are established through the derivation of theoretical insights. Their advantages are supported with computational experiments, which demonstrate upward of 75× improvements over exact factorization runtimes on fully dense matrices with more than one million entries. A significant advantage of the featured integer-preserving framework is that the length of any matrix coefficient produced by its algorithms is bounded polynomially in the size of the inputs without having to resort to greatest common divisor operations, which are required by and thereby hinder an efficient implementation of exact rational arithmetic approaches. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0331) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0331). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

A linear problem of regression analysis is considered under the assumption of the presence of noise in the output and input variables. This approximation problem may be interpreted as an improper interpolation problem, for which it is required to correct optimally the positions of the original points in the data space so that they all lie on the same hyperplane. The use of the quadratic approximation criterion for such a problem led to the appearance of the total least squares method. In this paper, we use the minimax criterion to estimate the measure of correction of the initial data. It leads to a nonlinear mathematical programming problem. It is shown that this problem can be reduced to solving a finite number of linear programming problems. However, this number depends exponentially on the number of parameters. Some methods for overcoming this complexity of the problem are proposed. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to delineate an algorithm for fractional programming with nonlinear as well as linear terms in the numerator and denominator. The algorithm presented is based on a theorem by Jagannathan [7] concerning the relationship between fractional and parametric programming. This theorem is restated and proved in a somewhat simpler way. Finally, it is shown how the given algorithm can be related to the method of Isbell and Marlow [6] for linear fractional programming and to the quadratic parametric approach by Ritter [10]. The Appendix contains a numerical example. [ABSTRACT FROM AUTHOR]

This paper considers the mathematical properties of chance constrained programming problems where the restriction is on the joint probability of a multivariate random event. One model that is considered arises when the right-hand side constants of the linear constraints are random. Another model treated here occurs when the coefficients of the linear programming variables are described by a multinormal distribution. It is shown that under certain restrictions both situations can be viewed as a deterministic nonlinear programming problem. Since most computational methods for solving nonlinear programming models require the constraints be concave, this paper explores whether the resultant problem meets the concavity assumption. For many probability laws of practical importance, the constraint in the first type of model is shown to violate concavity. However, a simple logarithmic transformation does produce a concave restriction for an important class of problems. The paper also surveys the `generalized linear programming' method for solving such problems when the logarithmic transformation is justified. For the second type model, the constraint is demonstrated to be nonconcave. [ABSTRACT FROM AUTHOR]

This paper presents a new nonlinear programming problem arising in the control of power systems, called optimal power flow with transient stability constraint and variable clearing time of faults and abbreviated as OTS-VT. The OTS-VT model is converted into a implicit generalized semi-infinite programming (GSIP) problem. According to the special box structure of the reformulated GSIP, a solution method based on bi-level optimization is proposed. The research in this paper has two contributions. Firstly, it generalizes the OTS study to general optimal power flow with transient stability problems. From the viewpoint of practical applications, the proposed research can improve the decision-making ability in power system operations. Secondly, the reformulation of OTS-VT also provides a new background and a type of GSIP in the research of mathematical problems. Numerical results for two chosen power systems show that the methodology presented in this paper is effective and promising. [ABSTRACT FROM AUTHOR]

This paper describes a novel approach to quantization in oversampled filter banks. The new technique is based on moving horizon optimization, does not rely on an additive white noise quantization model and allows stability to be explicitly enforced in the associated nonlinear feedback loop. Moreover, the quantization structure proposed here includes ΣΔ and linear predictive subband quantizers as a special case and, in general, out- performs them. [ABSTRACT FROM AUTHOR]

Optimization solvers include many options that allow users to control algorithmic aspects that may have a considerable impact on solver performance. Tuning solver options is often necessary to reduce execution time and improve solution quality. Previous studies of solver tuning techniques have focused on mixed-integer linear programming and local nonlinear programming solvers. In this paper, we investigate the potential of tuning a global optimization solver for nonlinear and mixed-integer nonlinear programming problems. In particular, derivative-free optimization (DFO) algorithms are used to find optimal values for options of the global optimization solver BARON. A set of 126 problems from the GLOBALLib and MINLPLib collections are utilized in a computational study from which we conclude that tuning options can improve the default performance of BARON for individual problems and an entire library. Additionally, we present a systematic comparison of 27 DFO solvers in terms of their ability to improve the performance of the global solver. We find that several DFO implementations are much better than others in terms of finding optimal tuning parameters. [ABSTRACT FROM AUTHOR]

In formulating a combinatorial optimisation problem (COP) using Discrete or Integer Programming (IP) modelling techniques, the modeller is restricted to use only certain predefined discrete variables and sets which are linked by sets of linear equality and inequality constraints. Definition of many COPs includes restrictions in which the use of dis-equality (DI) constraints in their mathematical representation is inevitable. To represent this type of constraint a number of binary variables and extra constraints are usually introduced, which lead to an increase in the size of the model in terms of variables and constraints. In this paper, we introduce a new class of discrete variables which enables the modeller to represent DI constraints more efficiently in the mathematical formulation of a combinatorial optimisation problem. We have also introduced a new branching scheme to the conventional simplex based Branch and Bound (B&B) algorithm in order to deal with this type of variables. To study the effect of these variables, we modelled and solved a set of five classic problems, first using conventional MP variables and second, exploiting the new proposed variables, and compared the results. The empirical results show a promising improvement on the performance of the B&B algorithm. The contribution of this paper is (1) the introduction of a new class of discrete variables which can help to build smaller models, and (2) new branching schemes on these variables that can improve the B&B performance. [ABSTRACT FROM AUTHOR]

A criticism of linear programming has been that the data which are available in practice are too inexact and unreliable for linear programming to properly work. Managers are therefore concerned with how much actual values may differ from the estimates that were used in the model before the results become irrelevant. Sensitivity analysis emerged to help deal with the uncertainties inherent in the linear programming model. However, the ranges calculated are generally valid only when a single coefficient is varied. An extension of sensitivity analysis, the 100 Percent Rule, allows the simultaneous variation of more than one element in a vector, but does not permit the independent variation of the elements. A tolerance approach to sensitivity analysis enables the consideration of simultaneous and independent change of more than one coefficient. However, the ranges developed are unnecessarily restricted and may be reduced in width to zero when primal or dual degeneracy exists. This paper presents an extension of the tolerance approach which reduces the limitations of both the traditional and tolerance approaches to sensitivity analysis. [ABSTRACT FROM AUTHOR]

This paper demonstrates the feasibility of applying nonlinear programming methods to solve the classification problem in discriminant analysis. The application represents a useful extension of previously proposed linear programming-based solutions for discriminant analysis. The analysis of data obtained by conducting a Monte Carlo simulation experiment shows that these new procedures are promising. Future research that should promote application of the proposed methods for solving classification problems in a business decision-making environment is discussed. [ABSTRACT FROM AUTHOR]

This paper considers the problem of partitioning N entities into M disjoint and nonempty subsets (clusters). Except when both N and N--M are very small, a search for the optimal solution by total enumeration of all clustering alternatives is quite impractical. The paper presents a dynamic programming approach that reduces the amount of redundant transitional calculations implicit in a total enumeration approach. A comparison of the number of calculations required under each approach is presented in Appendix A. Unlike most clustering approaches used in practice, the dynamic programming algorithm will always converge on the best clustering solution. The efficiency of the dynamic programming approach depends upon the rapid-access computer memory available. A numerical example is given in Appendix B. [ABSTRACT FROM AUTHOR]

The recent literature contains several papers which explore mathematical programming formulations of particular Markov sequential decision problems. Each of these papers deals with finite state and action spaces; thus, the corresponding programming formulations yield dual finite linear programs. In this paper these investigations are extended to include countable action and/or state spaces for finite horizon problems. Of particular interest are the duality aspects of the mathematical programming formulations. In addition, employing conditions analogous to fundamental concepts of Haar semi-infinite dual programming, we provide sufficient conditions for the existence of optimal rules for countable action spaces. Guided by the semi-infinite duality theory we explore mathematical programming formulations for two cases: 1) Countable action space and finite state space--the result is a pair of dual semi-infinite programs; and 2) Finite action space and countable state space--we obtain a pair of infinite programs. In the latter case we show that no duality gap occurs and obtain duality results comparable to those of finite linear programming. [ABSTRACT FROM AUTHOR]

In a team decision problem there are two or more decision variables, and these different decisions can be made to depend upon different aspects of the environment, or information variables, the resulting payoff being a random variable. The choice of optimal rules for selecting information variables and for making decisions is the central problem of the economic theory of teams. This paper shows, by means of an example, how linear programming can be applied to obtain optimal team decision functions in the case in which the payoff to the team is a convex polyhedral function of the decision variables. [ABSTRACT FROM AUTHOR]

This paper analyzes the solvability of a railway network design problem and its robust version. These problems are modeled as integer linear programming problems with binary variables, and their solutions provide topological railway networks maximizing the trip coverage in the presence of a competing mode, both assuming that the network works fine and that links can fail, respectively. Since these problems are computationally intractable for realistic sizes, GRASP heuristics are proposed for finding good feasible solutions. The results obtained in a computational experience indicate that our GRASP algorithms are suitable for railway network design problems. [ABSTRACT FROM AUTHOR]

Transistor aging is a major reliability concern for nanoscale CMOS technology that can significantly reduce the operation lifetime of very large-scale integration chips. Negative bias temperature instability (NBTI) is a major contributor to transistor aging that affects pMOS transistors. On the other hand, leakage power is becoming a dominant factor of the total power with successive technology scaling. Since the input combinations applied to a logic core have a significant impact on both NBTI and leakage power, input vector control can be used to optimize both phenomena during idle cycles. In this paper, we present an efficient input vector selection technique based on linear programming for cooptimizing the NBTI-induced delay degradation and leakage power consumption during standby mode. Since the NBTI-induced delay degradation and leakage power are not affected by the input vector in the same direction, we provide a pareto curve based on both phenomena. A suitable point from such a pareto curve is chosen based on circuit conditions and requirements during runtime. [ABSTRACT FROM AUTHOR]

This paper proposes a new algorithm for solving mixed discrete nonlinear programming (MDNLP) problems, designed to efficiently combine particle swarm optimization (PSO), which is a well-known global optimization technique, and branch-and-bound (BB), which is a widely used systematic deterministic algorithm for solving discrete problems. The proposed algorithm combines the global but slow search of PSO with the rapid but local search capabilities of BB, to simultaneously achieve an improved optimization accuracy and a reduced requirement for computational resources. It is capable of handling arbitrary continuous and discrete constraints without the use of a penalty function, which is frequently cumbersome to parameterize. At the same time, it maintains a simple, generic, and easy-to-implement architecture, and it is based on the sequential quadratic programming for solving the NLP subproblems in the BB tree. The performance of the new hybrid PSO-BB architecture algorithm is evaluated against real-world MDNLP benchmark problems, and it is found to be highly competitive compared with existing algorithms. [ABSTRACT FROM AUTHOR]

This paper establishes a theory framework of a class of nonlinear Lagrangians for solving nonlinear programming problems with inequality constraints. A set of conditions are proposed to guarantee the convergence of nonlinear Lagrangian algorithms, to analyze condition numbers of nonlinear Lagrangian Hessians as well as to develop the dual approaches. These conditions are satisfied by well-known nonlinear Lagrangians appearing in literature. The convergence theorem shows that the dual algorithm based on any nonlinear Lagrangian in the class is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions and the error bound solution, depending on the penalty parameter, is also established. The paper also develops the dual problems based on the proposed nonlinear Lagrangians, and the related duality theorem and saddle point theorem are demonstrated. Furthermore, it is shown that the condition numbers of Lagrangian Hessians at optimal solutions are proportional to the controlling penalty parameters. We report some numerical results obtained by using nonlinear Lagrangians. [ABSTRACT FROM AUTHOR]

Nonnegative large-scale linear programming problems with group constraints are extremely important for different applications in economics, technology, and other spheres. In this paper, we describe a new approach to preprocessing of these problems so that to reduce their dimensions considerably by defining and removing redundant constraints and variables. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the lexicographically minimum load linear programming problem, and we provide a polynomial approach followed by the proof of correctness. This problem has applications in numerous areas where it is desirable to achieve an equitable distribution or sharing of resources. We consider the application of our technique to the problem of lexicographically minimum load in capacitated multicommodity networks and discuss a special nonlinear case, the so-called Kleinrock load function. We next define the lexicographically maximum load linear programming problem and deduce a similar approach. An application in the lexicographically maximum concurrent flow problem is depicted followed by a discussion on the minimum balance problem as a special case of the lexicographically maximum load problem. [ABSTRACT FROM AUTHOR]

In this paper, an important but frequently overlooked aspect of production batch-size planning is addressed: namely, the consideration of unit load and material handling. Thus, an additional cost factor to account for the transportation of unit loads is incorporated in the total cost function which is typically broken down into reorder cost, inventory holding cost, and back order cost. A cost minimization model is developed that includes constraints related to volume and weight restrictions on unit loads and in-process storage space. A dynamic programming procedure is utilized to find the minimum cost solution. An example problem is also given. [ABSTRACT FROM AUTHOR]

In this note we construct some counterexamples concerning upper semicontinuity and linear upper and lower semicontinuity of the solution sets and ε-solution sets of nonlinear programming programs: max f(x), subject to g(x) (This character cannot be converted in ASCII text) b. These examples answer some of the questions in a recent paper by Stern and Topkis. [ABSTRACT FROM AUTHOR]

Planning the allocation of scarce resources to competing activities over multiple time periods is one of the most important problems facing decision makers in modern organizations. Much of the previous research in this area has concentrated on the use of linear programming procedures and has assumed that the technology through which scarce resource inputs are transformed into competing activity outputs is fixed. A more realistic assumption in many situations is that certain technology coefficients are likely to vary over the planning horizon as a function of activity levels in previous periods. In this paper, a multiperiod resource allocation model with variable technology is formulated. Enriching a more traditional fixed technology model to include variable technology results in a nonlinear model which is more realistic, but is also more difficult to solve. A heuristic procedure that is both straightforward and intuitively appealing is developed for obtaining good feasible solutions to the variable technology model. The solution procedure requires little additional computational effort beyond solving the associated, less realistic fixed technology model. [ABSTRACT FROM AUTHOR]

Successive Linear Programming (SLP), which is also known as the Method of Approximation Programming, solves nonlinear optimization problems via a sequence of linear programs. This paper reports on promising computational results with SLP that contrast with the poor performance indicated by previously published comparative tests. The paper provides a detailed description of an efficient, reliable SLP algorithm along with a convergence theorem for linearly constrained problems and extensive computational results. It also discusses several alternative strategies for implementing SLP. The computational results show that SLP compares favorably with the Generalized Reduced Gradient Code GRG2 and with MINOS/GRG. It appears that SLP will be meat successful when applied to large problems with low degrees of freedom. [ABSTRACT FROM AUTHOR]

A variety of combinatorial problems (e.g., in capital budgeting, scheduling, allocation) can be expressed as a linear integer programming problem. However, the standard devices for doing this often produce an inordinate number of variables and constraints, putting the problem beyond the practical reach of available integer programming methods. This paper presents new formulation techniques for capturing the essential nonlinearities of the problem of interest, while producing a significantly smaller problem size than the standard techniques. [ABSTRACT FROM AUTHOR]

This paper describes a decentralized linear programming solution procedure. Unlike the classic Dantzig-Wolfe decomposition algorithm, this procedure is a complete decentralization, where the subproblems act independently to generate the optimal solution. In Dantzig-Wolfe decomposition, the master problem must "dictate" the final optimal solution. Our procedure is an improvement over Dantzig-Wolfe decomposition in this sense. The procedure works by adding a "coercion" function to the subproblem objective. Under proper conditions, this function "coerces" the subproblem to behave as desired. Such total decentralization is important for loosely coupled systems where it is not possible for the master level to dictate optimal decision values for the subsystems. [ABSTRACT FROM AUTHOR]

In this paper we consider a class of generalized equations, which are a unified way of formulating problems of linear and nonlinear programming, complementarity, variational inequalities and mathematical economics among others. We introduce a set of conditions, which we call the strong positivity conditions, prove that they are sufficient for a solution of a generalized equation to be locally unique, and discuss their stability when the functions involved in the problem are subjected to small perturbations. Applications to linear generalized equations and nonlinear programming problems are discussed. [ABSTRACT FROM AUTHOR]

This paper presents an efficient algorithm for finding a minimum-weight generalized matching in a weighted bipartite graph. Computational evidence is given that indicates that the time required to find a least-cost assignment of n jobs to n workers goes roughly as n[sub2] for 10=

During the last decade a great number of approaches and schemes have been proposed for solving integer linear programming problems. These range from the implicit enumeration schemes including, for example, the additive algorithm of BALAS to schemes that proceed in a simplicial fashion to an optimal solution as does, for example, the All-Integer Method of GOMORY. Still other approaches have been heuristic in nature and strive to achieve so-called good (not necessarily optimal) solutions. The purpose of this paper is to discuss a framework that appears to offer some potential for devising new algorithms, and, at the same time, provides a theory that helps to unify some of the previously advanced methods for solving integer linear programming problems. The framework involves the use of bounds on variables and is related to some of the author's earlier work on the Geometric Definition Method of linear programming. [ABSTRACT FROM AUTHOR]

This paper summarizes experimental results from applying several computational methods for solving the classic three-machine scheduling model. The basic mathematical problem is to select an optimal permutation of a items, where the objective function employed is the total amount of processing time elapsing for the completion of all n items on three machines. The methods tested are integer linear programming, ordinary linear programming with answers rounded to integers, a heuristic algorithm, and random sampling. Throughout the experimentation n=6. A dual integer programming code is tested on six trial problems. Consideration is given to studying the phenomenon of input-form sensitivity. The results are not encouraging and confirm previous experimental evidence as to the strong effect of varying the input form. However, the addition of a powerful bound on the objective function has a significant beneficial effect on the convergence of the dual algorithm. A sampling study of the statistical characteristics of this model is made with 100 sets of data randomly generated. Frequency distributions of minimum and mean total processing time are tabulated and analyzed. On this same set of problems, a linear programming approach is examined for effectiveness in producing nearly optimal schedules. Such an approach tends to give answers that are better than would be obtained by a single permutation drawn at random, but the LP rounded solutions average about an 11 per cent increase over the optimal processing time. A heuristic algorithm based on Johnson's method is tested on 20 of the 100 eases and gives excellent results. Finally attention is turned to the method of randomly sampling the permutations, possibly applying a simple heuristic gradient method to improve each sampled schedule. A feature of this method is that elementary probability theory can be applied to yield corresponding statements about the accuracy guaranteed by the approach. [ABSTRACT FROM AUTHOR]

As interest grows rapidly in industry on the potentialities of mathematical programming techniques, it appears worthwhile to have a paper devoted to some of the more promoting developments which may speed up the transition from interest to use. Three topics have been selected (in three sections that follow) which have recently come into prominence: uncertainty, combinatorial problems, and large scale systems. The reader will find in the course of their dissensions that a survey--though perhaps not a systematic survey--has been made of current techniques in the linear programming field. [ABSTRACT FROM AUTHOR]

This article presents information regarding structural reliability bounds. They have applied linear programming techniques and obtained optimal bounds for a few examples in structural mechanics. However the authors have inadvertently omitted a few useful publications on probability bounds, which contain methods of obtaining near-optimal bounds without linear programming. The authors believe that with rapidly advancing speed and capacity of computers this purely computational issue may not be a hindrance in application of the LP approach to large-scale system reliability problems.

In millimeter wave (mmW) dense femto-networks, major challenges are overcoming the performance loss imposed by the channel and managing the co-channel interference. The former is due to the mmW susceptibility to pathloss and shadowing and the latter is due to density of the network. We cope with both challenges by a clustering method designed for mmW environment. In our approach, the femto access points (FAP) and femto users (FU) are clustered based on having the most line of sight connectivity. We modify this binary optimization problem into a continuous problem using deductive penalty functions and solve it by difference of two convex functions (D.C.) programming. Our clustering algorithm achieves higher data rate compared to the foremost clustering method. We also propose a technique to assign FUs to FAPs in each cluster which has near-optimal performance and polynomial time complexity. We solve mixed integer nonlinear programming of power and sub-channel allocation by D.C. programming. Instead of using the deductive penalty terms in D.C. programming, we penalize the objective function in a multiplicative manner. Thus, the penalty term depends on both constraint violation and objective function. Our scheme achieves around 10% higher data rate compared to the method using deductive penalty terms. [ABSTRACT FROM AUTHOR]

This paper aims to totally remove intercore communication overhead with joint computation and communication task scheduling for streaming applications on Multiprocessor System-on-Chips (MPSoCs). Our basic idea is to let some computation and communication tasks be executed in earlier periods (the added periods are called the prologue) such that intercore data transfer can be finished before the execution of the tasks that need the data to start. In particular, we solve the following problem: how to do rescheduling in such a way that the schedule length can be minimized with the minimum prologue length (the number of periods in the prologue) while the intercore communication overhead can be totally removed? To solve this problem, we first perform schedulability analysis and obtain the upper bound of the times needed to reschedule each computation task. Then we formulate the problem as an Integer Linear Programming (ILP) formulation and obtain an optimal solution. We evaluate our technique with a set of benchmarks from both real-life streaming applications and synthetic task graphs. The experimental results show that our technique can achieve significant reductions in schedule length and energy consumption compared with the previous work. [ABSTRACT FROM AUTHOR]

The paper is a manifestation of the fundamental importance of the linear program with linear complementarity constraints (LPCC) in disjunctive and hierarchical programming as well as in some novel paradigms of mathematical programming. In addition to providing a unified framework for bilevel and inverse linear optimization, nonconvex piecewise linear programming, indefinite quadratic programs, quantile minimization, and ℓ minimization, the LPCC provides a gateway to a mathematical program with equilibrium constraints, which itself is an important class of constrained optimization problems that has broad applications. We describe several approaches for the global resolution of the LPCC, including a logical Benders approach that can be applied to problems that may be infeasible or unbounded. [ABSTRACT FROM AUTHOR]

An extension of the DS/AHP method is proposed in the paper. It takes into account the fact that the multi-criteria decision problem might have several levels of criteria. Moreover, it is assumed that expert judgments concerning the criteria are imprecise and incomplete. The proposed extension also uses groups of experts or decision makers for comparing decision alternatives and criteria. However, it does not require assigning favorability values for groups of decision alternatives and criteria. The computation procedure for processing and aggregating the incomplete information about criteria and decision alternatives is reduced to solving a finite set of linear programming problems. Numerical examples explain in detail and illustrate the proposed approach. [ABSTRACT FROM AUTHOR]

This paper studies the global optimization of polynomial programming problems using Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations. We introduce a new class of bound-grid-factor constraints that can be judiciously used to augment the basic RLT relaxations in order to improve the quality of lower bounds and enhance the performance of global branch-and-bound algorithms. Certain theoretical properties are established that shed light on the effect of these valid inequalities in driving the discrepancies between RLT variables and their associated nonlinear products to zero. To preserve computational expediency while promoting efficiency, we propose certain concurrent and sequential cut generation routines and various grid-factor selection rules. The results indicate a significant tightening of lower bounds, which yields an overall reduction in computational effort for solving a test-bed of polynomial programming problems to global optimality in comparison with the basic RLT procedure as well as the commercial software BARON. [ABSTRACT FROM AUTHOR]

Abstract: Multi-choice programming solves some optimization problems where multiple information exists for a parameter. The aim of this paper is to select an appropriate parameter from a set of multiple choices, which optimizes the objective function. We consider a linear programming problem where the right hand side parameters are multi-choice in nature. In this paper, the multiple choices of a parameter are considered as functional values of an affine function at some non-negative integer nodes. An interpolating polynomial is formulated using functional values at non-negative integer nodes to take care of any multi-choice parameter. After establishing interpolating polynomials of all multi-choice parameters, a mathematical programming problem is formulated. The formulated problem is treated as a nonlinear programming problem involving mixed integer type variables. It can be solved by using standard nonlinear programming software. Finally, a numerical example is presented to illustrate the solution procedure. [Copyright &y& Elsevier]

The article discusses a linear programming formulation of the general portfolio selection problem. The author states that in the 1950s a scientist developed the portfolio selection problem as a parametric quadratic programming problem. He explains that the point of his formulation was the mean-variance assumption which suggested that a portfolio is efficient if it has less variance than any other practical portfolio with the same return and it has more return than any other feasible portfolio with the same variance. The article also presents index models which have been formulated to simplify both the informational and computational complexity of the general model.

In this paper, we present a new neural network for solving linear and quadratic programming problems in real time by introducing some new vectors. The proposed neural network is stable in the sense of Lyapunov and can converge to an exact optimal solution of the original problem when the objective function is convex on the set defined by equality constraints. Compared with existing one-layer neural networks for quadratic programming problems, the proposed neural network has the least neurons and requires weak stability conditions. The validity and transient behavior of the proposed neural network are demonstrated by some simulation results. [ABSTRACT FROM AUTHOR]

Abstract: A global optimization algorithm is proposed in order to locate the global minimum of the special reverse convex programming which is both nonconvex and nonlinear. Three new strategies are adopted in this paper. Some of them can be used to solve general reverse convex programming. Global solution locating is to identify the location of the solution. The linear relaxation method is used to obtain the lower bound of the optimum of the primal programming, and in this paper the relaxed programming is a kind of linear programming, which can be solved by standard simplex algorithm. The final strategy is upper bound updating method, which provides a better upper bound than the standard branch and bound method. According to the strategies, a global optimization algorithm is derived based on branch and bound theory. It is proved that the algorithm possesses global convergence. Finally, a numerical experiment is given to illustrate the feasibility and the smaller computational effort. [Copyright &y& Elsevier]

In this paper we consider solution methods for multiobjective integer programming (MOIP) problems based on scalarization. We define the MOIP, discuss some common scalarizations, and provide a general formulation that encompasses most scalarizations that have been applied in the MOIP context as special cases. We show that these methods suffer some drawbacks by either only being able to find supported efficient solutions or introducing constraints that can make the computational effort to solve the scalarization prohibitive. We show that Lagrangian duality applied to the general scalarization does not remedy the situation. We also introduce a new scalarization technique, the method of elastic constraints, which is shown to be able to find all efficient solutions and overcome the computational burden of the scalarizations that use constraints on objective values. Finally, we present some results from an application in airline crew scheduling as evidence. [ABSTRACT FROM AUTHOR]

Constraint programming offers modeling features and solution methods that are unavailable in mathematical programming but are often flexible and efficient for scheduling and other combinatorial problems. Yet mathematical programming is well suited to declarative modeling languages and is more efficient for some important problem classes. This raises this issue as to whether the two approaches can be combined in a declarative modeling framework. This paper proposes a general declarative modeling system in which the conditional structure of the constraints shows how to integrate any ‘checker’ and any special-purpose ‘solver’. In particular this integrates constraint programming and optimization methods, because the checker can consist of constraint propagation methods, and the solver can be a linear or nonlinear programming routine. [ABSTRACT FROM AUTHOR]

The goals of this paper are to present a two-stage programming model for the capacity expansion problem under uncertainty of demand and explore the impact of this uncertainty on cost. The model is a mixed integer nonlinear programming (MINLP) model with the consideration of uncertainty used to maximize the expected present value of utility profits over the planning horizon, under the constraints of rate of return and reserve margin regulation. The results reveal that the uncertainty harms the profit seriously. In this paper both microeconomics and mathematical programming are used to analyse the problem. We try to observe the economic behaviour of the utility with uncertainty involved. We also investigate the influence on the cost of uncertainty of each economic parameter. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper represents an integration of Mixed Integer Programming (MIP) and Constraint Logic Programming (CLP) which, like MIP, tightens bounds rather than adding constraints during search. The integrated system combines components of the CLP system ECLiPSe [7] and the MIP system CPLEX [5], in which constraints can be handled by either one or both components. Our approach is introduced in three stages. Firstly, we present an automatic transformation which maps CLP programs onto such CLP programs that any disjunction is eliminated in favour of auxiliary binary variables. Secondly, we present improvements of this mapping by using a committed choice operator and translations of pre-defined nonlinear constraints. Thirdly, we introduce a new hybrid algorithm which reduces the solution space of the problem progressively by calling finite domain propagation of ECLiPSe as well as dual simplex of CPLEX. The advantages of this integration are illustrated by efficiently solving difficult optimisation problems like the Hoist Scheduling Problem [23] and the Progressive Party Problem [27]. [ABSTRACT FROM AUTHOR]

Sampling and decomposition constitute two of the most successful approaches for addressing large-scale problems arising in statistics and optimization, respectively. In recent years, these two approaches have been combined for the solution of large-scale stochastic linear programming problems. This paper presents the algorithmic motivation for such methods, as well as a broad overview of issues in algorithm design. We discuss both basic schemes as well as computational enhancements and stopping rules. We also introduce a generalization of current algorithms to handle problems with random recourse. [ABSTRACT FROM AUTHOR]

This paper describes a problem in which the "cost" of satisfying the demand at a particular location is a weighted average of the travel times for the items that are supplied. The greatest weight is given to the first-arriving item, with decreasing weights given to each succeeding item. In the case of known demand, the problem is transformed into an equivalent transportation problem. In the case of stochastic demand, the problem is transformed into a transportation problem whose objective is to minimize the sum of a linear function and a convex function of the sum of the flows on selected arcs. This problem is linearized by substituting for the convex function the product of a parameter and a linear term. The parameterized problem is solved by parametric linear programming and by "updating the slope.". [ABSTRACT FROM AUTHOR]

Successive Linear Programming (SLP) algorithms solve nonlinear optimization problems via a sequence of linear programs. They have been widely used, particularly in the oil and chemical industries, beginning with their introduction by Griffith and Stewart of Shell Development Company in 1961. Since then, several applications and variants of SLP have appeared, the most recent being the SLPR algorithm described in this journal in 1982 (Palacios-Gomez et al.). SLP procedures are attractive because they are fairly easy to implement if an efficient, flexible LP code is available, can solve nonseparable as well as separable problems, can be applied to as large a problem as the LP code can handle (often thousands of constraints and variables), and have been successful in many practical applications. This paper describes a new SLP algorithm called PSLP (Penalty SLP). PSLP represents a significant strengthening and refinement of the SLPR procedure described in Palacios-Gomez et al. (1982). We give a convergence proof for PSLP--the first SLP convergence proof for nonlinearly constrained problems of general form. This theory is supported by computational performance--in our tests, PSLP is significantly more robust than SLPR, and at least as efficient. A Fortran computer implementation is described. A simplified version of PSLP has already solved several "real world" NLP problems at Exxon (Baker and Lasdon 1985), including nonlinear refinery models of up to 1000 rows. As with other SLP algorithms, PSLP is especially efficient on problems which are highly constrained, i.e., which have nearly as many active constraints as there are variables. For problems with vertex optima (at least as many active constraints as variables), it is quadratically convergent. Nonlinear refinery models often have vertex optima, since they are large and mostly linear, and on line process unit optimization problems are likely to possess highly constrained solutions as well. PSLP has great potential for accurate, efficient solution of such problems [ABSTRACT FROM AUTHOR]

In recent years, much research has been done on the application of mathematical programming (MP) techniques to the discriminant problem. While promising results have been obtained, many of these techniques are plagued by a number of problems associated with the model formulation including unbounded, improper, and unacceptable solutions as well as solution instability under linear transformation of the data. In attempting to solve these problems, numerous formulations have been proposed involving additional variables and/or normalization constraints. While effective, these models can also become quite complex. In this paper we demonstrate that a simple, well-known special case of Hand's original formulation provides an implicit normalization which avoids the problems for which various complicated remedies have been devised. While other researchers have made use of this formulation, its properties have not previously been fully recognized. [ABSTRACT FROM AUTHOR]