1,036 results
Search Results
2. [Untitled]
- Author
-
Ronny Aboudi and Paulo Bárcia
- Subjects
Mathematical optimization ,business.product_category ,Partition problem ,General Decision Sciences ,Management Science and Operations Research ,Paper machine ,Cutting stock problem ,Knapsack problem ,Theory of computation ,Subset sum problem ,Subprocedure ,business ,Stock (geology) ,Mathematics - Abstract
This paper investigates the problem of obtaining the best arrangement for cutting stockpatterns in the presence of defective material in the paper, which is a common problem inthe industry. This problem is modeled as a multiple subset sum problem and its structure isexploited in order to obtain a practical solution procedure. The solution methodologyemploys the subset sum problem as a subprocedure. Computational results are reported.
- Published
- 1998
3. The nearest adjoining order method for pairwise comparisons in the form of difference of ranks.
- Author
-
Klukowski, Leszek
- Subjects
CLUSTER set theory ,SET theory ,RANDOM variables ,MATHEMATICAL statistics ,PROBABILITY theory ,MATHEMATICS - Abstract
The problem of ranking of elements from some finite set on the basis of nearest adjoining order method for pairwise comparisons is investigated in this paper. It is assumed that in the set under consideration there exists a weak preference relation, which is to be identified estimated) on the basis of pairwise comparisons in the form of difference of ranks. Moreover, the results of comparisons may be disturbed with random errors; the assumptions made about error distributions are not restrictive. The paper comprises: the problem formulation definitions, assumptions, and optimisation problem, which provides the NAO solution) and the theoretical background - the form of distributions of random variables which make it possible to determine the properties of NAO solution, in particular, evaluation of the probability, that the NAO solution is equivalent to the errorless one. The approach presented in the paper can be extended to the case of more than one comparison for each pair of elements, i.e., completely formalised multi-experts ranking procedure. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
4. On the analytical derivation of efficient sets in quad-and-higher criterion portfolio selection.
- Author
-
Qi, Yue and Steuer, Ralph E.
- Subjects
DIVIDEND yield ,ALGORITHMS ,MATHEMATICS ,PARABOLOID ,SUSTAINABILITY - Abstract
This paper provides results in the area of the analytical derivation of the efficient set of a mean-variance portfolio selection problem that has more than three criteria. By "analytical" we mean derived by formula as opposed to being computed by algorithm. By "more than three criteria", we mean that beyond the mean and variance of regular portfolio selection, the problems addressed have two or more additional linear objectives. The additional objectives might include sustainability, dividend yield, liquidity, and R&D as extra objectives like these are being seen with greater frequency. While not all multiple criteria portfolio selection problems lend themselves to an analytical derivation, a certain class does and the problems in this class are covered by the mathematics of this paper. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
5. Stability of multistage stochastic programming.
- Author
-
Wang, Jinde
- Subjects
STOCHASTIC programming ,LINEAR programming ,DYNAMICS ,STOCHASTIC convergence ,MATHEMATICAL functions ,MATHEMATICS - Abstract
In this paper, we study the stability of multistage stochastic programming with recourse in a way that is different from that used in studying stability of two-stage stochastic programs. Here, we transform the multistage programs into mathematical programs in the space R
n x Lp with a simple objective function and multistage stochastic constraints. By investigating the continuity of the multistage multifunction defined by the multistage stochastic constraints and applying epi-convergence theory we obtain stability results for linear and linear-quadratic multistage stochastic programs. [ABSTRACT FROM AUTHOR]- Published
- 1995
- Full Text
- View/download PDF
6. Translation invariance in data envelopment analysis: A generalization.
- Author
-
Pastor, Jesús T.
- Subjects
DATA envelopment analysis ,LINEAR programming ,MULTIVARIATE analysis ,MATHEMATICAL models ,MATHEMATICS - Abstract
In this paper, we undertake a revision and a generalization of the results contained in the only paper so far published on the matter of translation invariance by allowing inputs and outputs to take not only zero but negative values. This broadens the field of application of the DEA methodology. [ABSTRACT FROM AUTHOR]
- Published
- 1997
7. A review of Goal Programming and its applications.
- Author
-
Tamiz, M., Jones, D. F., and E. El-Darzi
- Subjects
MATHEMATICAL programming ,ALGORITHMS ,COMPUTER programming ,FUNCTIONAL equations ,LEXICOGRAPHY ,UTILITY functions ,MATHEMATICS - Abstract
This paper presents a review of the current literature on the branch of multi-criteria decision modelling known as Goal Programming (GP). The result of our indepth investigations of the two main GP methods, lexicographic and weighted GP together with their distinct application areas is reported. Some guidelines to the scope of GP as an application tool are given and methods of determining which problem areas are best suited to the different GP approaches are proposed. The correlation between the method of assigning weights and priorities and the standard of the results is also ascertained. [ABSTRACT FROM AUTHOR]
- Published
- 1995
- Full Text
- View/download PDF
8. ON THE GEOMETRY OF PATHS GENERATED BY PL HOMOTOPY METHODS.
- Author
-
Zeke Wang
- Subjects
GEOMETRY ,MATHEMATICS ,HOMOTOPY theory ,TOPOLOGY ,GROUP theory ,OPERATIONS research - Abstract
PL homotopy methods are effective numerical methods for highly nonlinear problems. It is widely believed that the feasibility of a PL homotopy method depends on the nondegeneracy condition that the zero set (or the fixed point set in the case of finding fixed points instead of zeroes) of the PL approximation of the homotopy does not intersect the triangulation's skeletons of co-dimensions two and above. This paper shows that, although the sections of the PL approximation's zero set tracked by the PL homotopy method are of dimension one (while other sections may have higher dimensions), the paths generated by the pivoting method are potentially and essentially of dimension two. It makes path-crossing a safe thing. Thus, this paper first sets up the without exception feasibility of PL homotopy methods geometrically. [ABSTRACT FROM AUTHOR]
- Published
- 1990
- Full Text
- View/download PDF
9. Multicriteria optimisation and simulation: an industrial application.
- Author
-
Duvivier, D., Roux, O., Dhaevers, V., Meskens, N., and Artiba, A.
- Subjects
MATHEMATICAL optimization ,METHODOLOGY ,OPERATIONS research ,PROBABILITY theory ,MATHEMATICS - Abstract
This paper deals with multicriteria discrete-continuous problems of scheduling nonpreemptable jobs. The need for reusability and modularity leads us to build a “generic” optimisation and simulation framework, while the need to quickly generate good compromises between conflicting objectives requires the implementation of multicriteria scheduling models. This paper describes the practical possibilities of three hybrid models within this framework. The validation of the framework is presented in terms of its application to a real, highly constrained, discrete-continuous problem. The optimisation model is based on the hybridisation of a classical hill-climber meta-heuristic with the Promethee II multicriteria method. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
10. Improved Bounds and Simulation Procedures on the Value of the Multivariate Normal Probability Distribution Function.
- Author
-
Szántai, Tamás
- Subjects
DISTRIBUTION (Probability theory) ,MULTIVARIATE analysis ,BINOMIAL distribution ,ANALYSIS of variance ,OPERATIONS research ,MATHEMATICS - Abstract
Improved bounds and simulation procedures on the value of the multivariate normal probability distribution function value are given in the paper. The author's variance reduction technique was based on the Bonferroni bounds involving the first two binomial moments only. The new variance reduction technique is adapted to the most refined new bounds developed in the last decade for the estimation the probability of union respectively intersection of events. Numerical test results prove the efficiency of the simulation procedures described in the paper. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
11. Index Sets in Modeling Languages.
- Author
-
Hürlimann, Tony
- Subjects
INTEGRALS ,MATHEMATICAL models ,MATHEMATICAL notation ,MATHEMATICS ,SET theory ,OPERATIONS research - Abstract
Index sets are an integral and fundamental part of every mathematical modeling language. They assist the modeler in grouping various objects and entities. Index sets are also used extensively in the mathematical notation to write an expression in a concise way. An example is the sigma notation for formulating the summation of an unknown number n of terms. In this paper, the concept of index set is introduced in the context of modeling languages. The main objective is to propose an extension and generalization of the concept of index sets, which is the concept of hierarchical index sets. The paper concludes with an application, which clearly shows the usefulness of this concept. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
12. A surrogate constraint tabu thresholding implementation for the frequency assignment problem.
- Author
-
Castelino, Diane and Stephens, Nelson
- Subjects
TELECOMMUNICATION ,RADIO frequency ,COMBINATORIAL optimization ,COMBINATORICS ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,COMMUNICATION ,MATHEMATICS - Abstract
This paper presents a surrogate constraint tabu thresholding (SCTT) implementation for solving the frequency assignment problem. The frequency assignment problem is an important combinatorial optimisation problem that arises in telecommunications. The main objective is to assign radio frequencies to a number of communication links such that interference is minimised. Interference is minimised by satisfying a number of problem specific constraints. The surrogate constraint is created by taking a weighted sum of the constraints not satisfied. SCTT is compared with a tabu thresholding method from the literature on a set of simulated but realistic test problems with respect to quality of the solution in a given time period. Computational results show that SCTT is more efficient and effective for all the test problems. [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
13. Introduction of a new class of variables to discrete and integer programming problems.
- Author
-
Hajian, Mozafar T., Rodošek, Robert, and Richards, Barry
- Subjects
COMBINATORIAL optimization ,INTEGER programming ,NONLINEAR programming ,LINEAR programming ,MATHEMATICAL optimization ,COMBINATORICS ,MATHEMATICAL programming ,MATHEMATICS - Abstract
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]
- Published
- 1999
- Full Text
- View/download PDF
14. A simulated annealing code for general integer linear programs.
- Author
-
Abramson, David and Marcus Randall
- Subjects
SIMULATED annealing ,COMBINATORIAL optimization ,COMBINATORICS ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,MATHEMATICS - Abstract
This paper explores the use of simulated annealing (SA) for solving arbitrary combinatorial optimisation problems. It reviews an existing code called GPSIMAN for solving 0–1 problems, and evaluates it against a commercial branch-and-bound code, OSL. The problems tested include travelling salesman, graph colouring, bin packing, quadratic assignment and generalised assignment. The paper then describes a technique for representing these problems using arbitrary integer variables, and shows how a general simulated annealing algorithm can also be applied. This new code, INTSA, outperforms GPSIMAN and OSL on almost all of the problems tested. [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
15. Existence of additive utility on positive semigroups: An elementary proof.
- Author
-
Candeal, Juan C., Induráin, Esteban, and Olóriz, Esteban
- Subjects
UTILITY functions ,ECONOMIC demand ,UTILITY theory ,MATHEMATICS ,OPERATIONS research ,ECONOMICS - Abstract
This paper is concerned with the representability of totally ordered semigroups as subsets of the additive real line (R, +, ≤). We prove in an elementary way the existence of an additive utility function. [ABSTRACT FROM AUTHOR]
- Published
- 1998
- Full Text
- View/download PDF
16. On properties of geometric random problems in the plane.
- Author
-
Jaillet, Patrick
- Subjects
MOTIVATION (Psychology) ,TRAVELING sales personnel ,SALES personnel ,GEOMETRY ,COMMERCIAL agents ,MATHEMATICS - Abstract
In this paper, we present results dealing with properties of well-known geometric random problems in the plane, together with their motivations. The paper specifically concentrates on the traveling salesman and minimum spanning tree problems, even though most of the results apply to other problems such as the Steiner tree problem and the minimum weight matching problem. [ABSTRACT FROM AUTHOR]
- Published
- 1995
- Full Text
- View/download PDF
17. On n-person noncooperative multicriteria games described in strategic form.
- Author
-
Kruś, Lech and Bronisz, Piotr
- Subjects
MULTIPLE criteria decision making ,NONCOOPERATIVE games (Mathematics) ,GAME theory ,DECISION making ,DECISION theory ,MATHEMATICAL models ,MATHEMATICS - Abstract
This paper undertakes the problem of multicriteria decision support in conflict situations described as a noncooperative game. Construction of such a decision support requires the development of the noncooperative game theory to be generalized for the multicriteria case. New theoretical results in this case are presented. Features of the multicriteria noncooperative games are shown with use of a duopoly model in case of two goods and two criteria of each player. Concepts of the decision support are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 1994
- Full Text
- View/download PDF
18. Some concepts of non-myopic equilibria in games with finite strategy sets and their properties.
- Author
-
Selbirak, Tadeusz
- Subjects
EQUILIBRIUM ,NONCOOPERATIVE games (Mathematics) ,GAMES of strategy (Mathematics) ,GAME theory ,MATHEMATICAL models ,MATHEMATICS ,GROUP theory ,MATHEMATICAL optimization - Abstract
This paper presents a special class of equilibria in finite strategy noncooperative games, which are extensions of the traditional Nash equilibrium solution. An underlying role in these equilibria play the assumed extended models of players' rationality principles which admit their non-myopic behaviour. The crucial idea is that players possessing some information about their opponents and the game itself can forecast the consequences of their choices by analyzing the ‘move-countermove’ possible sequences and accordingly predict the stability of game outcomes. The class of discussed equilibria besides the classical Nash equilibrium includes all the solutions considered in metagame and hypergame theories, and its determinants allow for a useful characterization of new potential equilibria concepts in modeled real-life conflicts. For specific equilibrium concepts, their individual properties are discussed and some analytical characterizations are provided. The paper concludes with the description of a computer-based procedure developed for calculating different kinds of generalized equilibrium points. Possible applications of this procedure within simulation and gaming are briefly discussed. [ABSTRACT FROM AUTHOR]
- Published
- 1994
- Full Text
- View/download PDF
19. LINEAR PROGRAMMING WITH STOCHASTIC PROCESSES AS PARAMETERS AS APPLIED TO PRODUCTION PLANNING.
- Author
-
Jagannathan, Raj
- Subjects
LINEAR programming ,STOCHASTIC programming ,PRODUCTION planning ,MATHEMATICAL statistics ,PARAMETERS (Statistics) ,MATHEMATICS - Abstract
In formulating stochastic programming with recourse models, the parameters of the linear programs are usually assumed to be random variables with known distributions. In this paper, the requirement vector parameter is assumed to be a stochastic process {
i (t), t ϵ T, i = 1,..., m}. The properties of the deterministic equivalents for the cases of the discrete and continuous index set T are derived. The results of the paper are applied to a multi-item production planning model with continuous (periodic) review of the stock on hand of various items. [ABSTRACT FROM AUTHOR]- Published
- 1991
- Full Text
- View/download PDF
20. ADAPTATION OF THE PLANT LOCATION MODEL FOR REGIONAL ENVIRONMENTAL FACILITIES AND COST ALLOCATION STRATEGY.
- Author
-
Zhong Ping Zhu, ReVelle, Charles, and Rosing, Kenneth
- Subjects
ECONOMETRICS ,ECONOMIC models ,MATHEMATICAL models ,ECONOMIC statistics ,LINEAR substitutions ,LINEAR programming ,OPERATIONS research ,MATHEMATICS - Abstract
This paper is divided into two parts. In the first part of the paper, the plant location model is adapted for the special case of siting wastewater treatment facilities when the wastewater sources and treatment facilities are arranged in a chain or linear configuration. In this problem, flows or shipments may be merged in common pipes that provide economies of scale in transport. In order to apply the plant location model, an appropriate definition of the additional cost incurred when a waste source joins a regional facility is required. In addition, sequential priority constraints are developed in the siting model in order to make possible proper accounting of transport costs. The new siting model can be conveniently solved by linear programming. In the second part of the paper, a dual of the plant location model is explored as a cost allocation method for the fixed charge facility siting problem. The constraint sets of the dual model can be shown to imply the core conditions of the related cost game; hence, a set of the dual variables from the dual problem can be regarded as rational cost allocations. The analysis places both facility siting and cost allocation in a common framework. [ABSTRACT FROM AUTHOR]
- Published
- 1989
- Full Text
- View/download PDF
21. THE CAPACITATED MAXIMAL COVERING LOCATION PROBLEM WITH BACKUP SERVICE.
- Author
-
Pirkul, Hasan and Schilling, David
- Subjects
MAXIMAL functions ,MATHEMATICAL functions ,DIFFERENTIAL equations ,MATHEMATICAL analysis ,MATHEMATICAL models ,MATHEMATICS - Abstract
The maximal covering location problem has been shown to be a useful tool in siting emergency services. In this paper we expand the model along two dimensions - workload capacities on facilities and the allocation or multiple levels of backup or prioritized service for all demand points. In emergency service facility location decisions such as ambulance sitting, when all of a facility's resources are needed to meet each call for service and the demand cannot be queued, the need for a backup unit may be required. This need is especially significant in areas of high demand. These areas also will often result in excessive workload for some facilities. Effective siting decisions, therefore, must address both the need for a backup response facility for each demand point and a reasonable limit on each facility's workload. In this paper, we develop a model which captures these concerns as well as present an efficient solution procedure using Lagrangian relaxation. Results of extensive computational experiments are presented to demonstrate the viability of the approach. [ABSTRACT FROM AUTHOR]
- Published
- 1989
- Full Text
- View/download PDF
22. On duality theory for non-convex semidefinite programming.
- Author
-
Wenyu Sun, Chengjin Li, and Sampaio, Raimundo J. B.
- Subjects
SEMIDEFINITE programming ,DUALITY theory (Mathematics) ,MATHEMATICAL programming ,ALGEBRA ,MATHEMATICS - Abstract
In this paper, with the help of convex-like function, we discuss the duality theory for nonconvex semidefinite programming. Our contributions are: duality theory for the general nonconvex semidefinite programming when Slater's condition holds; perfect duality for a special case of the nonconvex semidefinite programming for which Slater's condition fails. We point out that the results of Fan (Appl. Math. Lett. 18:1068-1073, ) can be regarded as a special case of our result. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
23. Regression games.
- Author
-
Pintér, Miklós
- Subjects
BUSINESS ,REGRESSION analysis ,DECISION making ,MATHEMATICAL variables ,MATHEMATICS - Abstract
The solution of a TU cooperative game can be a distribution of the value of the grand coalition, i.e. it can be a distribution of the payoff (utility) all the players together achieve. In a regression model, the evaluation of the explanatory variables can be a distribution of the overall fit, i.e. the fit of the model every regressor variable is involved. Furthermore, we can take regression models as TU cooperative games where the explanatory (regressor) variables are the players. In this paper we introduce the class of regression games, characterize it and apply the Shapley value to evaluating the explanatory variables in regression models. In order to support our approach we consider Young's (Int. J. Game Theory 14:65-72, ) axiomatization of the Shapley value, and conclude that the Shapley value is a reasonable tool to evaluate the explanatory variables of regression models. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
24. A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric.
- Author
-
Gassner, Elisabeth
- Subjects
GAME theory ,LOCATION problems (Programming) ,ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICS - Abstract
This paper deals with downgrading the 1-median, i.e., changing values of parameters within certain bounds such that the optimal objective value of the location problem with respect to the new values is maximized. We suggest a game-theoretic view at this problem which leads to a characterization of an optimal solution. This approach is demonstrated by means of the Downgrading 1-median problem in the plane with Manhattan metric and implies an $\mathcal {O}(n\log^{2}n)$ time algorithm for this problem. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
25. The Shapley value for bicooperative games.
- Author
-
Bilbao, J., Fernández, J., Jiménez, N., and López, J.
- Subjects
GAME theory ,COOPERATION ,COMBINATORICS ,MATHEMATICAL analysis ,VALUES (Ethics) ,MATHEMATICS - Abstract
The aim of the present paper is to study a one-point solution concept for bicooperative games. For these games introduced by Bilbao (Cooperative Games on Combinatorial Structures, ) , we define a one-point solution called the Shapley value, since this value can be interpreted in a similar way to the classical Shapley value for cooperative games. The main result of the paper is an axiomatic characterization of this value. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
26. A machine learning approach to algorithm selection for $\mathcal{NP}$ -hard optimization problems: a case study on the MPE problem.
- Author
-
Guo, Haipeng and Hsu, William
- Subjects
MATHEMATICAL optimization ,ALGORITHMS ,METHODOLOGY ,ARTIFICIAL intelligence ,ALGEBRA ,MATHEMATICS - Abstract
Given one instance of an $\mathcal{NP}$ -hard optimization problem, can we tell in advance whether it is exactly solvable or not? If it is not, can we predict which approximate algorithm is the best to solve it? Since the behavior of most approximate, randomized, and heuristic search algorithms for $\mathcal{NP}$ -hard problems is usually very difficult to characterize analytically, researchers have turned to experimental methods in order to answer these questions. In this paper we present a machine learning-based approach to address the above questions. Models induced from algorithmic performance data can represent the knowledge of how algorithmic performance depends on some easy-to-compute problem instance characteristics. Using these models, we can estimate approximately whether an input instance is exactly solvable or not. Furthermore, when it is classified as exactly unsolvable, we can select the best approximate algorithm for it among a list of candidates. In this paper we use the MPE (most probable explanation) problem in probabilistic inference as a case study to validate the proposed methodology. Our experimental results show that the machine learning-based algorithm selection system can integrate both exact and inexact algorithms and provide the best overall performance comparing to any single candidate algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
27. Solving Difficult Multicommodity Problems with a Specialized Interior-Point Algorithm.
- Author
-
Castro, Jordi
- Subjects
LINEAR programming ,MATRICES (Mathematics) ,ALGORITHMS ,ALGEBRA ,MATHEMATICAL variables ,MATHEMATICS - Abstract
Due to recent advances in the development of linear programming solvers, some of the formerly considered difficult multicommodity problems can today be solved in few minutes, even faster than with specialized methods. However, for other kind of multicommodity instances, general linear solvers can still be quite inefficient. In this paper we will give an overview of the current state-of-the-art in solving large-scale multicommodity problems, comparing an specialized interior-point algorithm with CPLEX 6.5 in the solution of difficult multicommodity problems of up lo I million of variables and 300,000 constraints. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF
28. A Probabilistic Minimax Location Problem on the Plane.
- Author
-
Berman, Oded, Jiamin Wang, Drezner, Zvi, and Wesolowsky, George O.
- Subjects
LOCATION problems (Programming) ,MATHEMATICS ,COMPUTER software ,MATHEMATICAL programming ,ALGORITHMS ,PLANE-table - Abstract
In this paper we consider the weighted minimax (1-center) location problem in the plane when the weights are not given but rather drawn from independent uniform distributions. The problem is formulated and analyzed. For certain parameters of the uniform distributions the objective function is proven to be convex and thus can be easily solved by standard software such as the Solver in Excel. Computational experience is reported. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF
29. Characteristics of Good Meta-Heuristic Algorithms for the Frequency Assignment Problem.
- Author
-
Smith, D. H., Allen, S. M., and Hurley, S.
- Subjects
ALGORITHMS ,ASSIGNMENT problems (Programming) ,NONLINEAR assignment problems ,CONSTRAINT satisfaction ,MATHEMATICS ,OPERATIONS research - Abstract
Most writers on frequency assignment algorithms have described the details of a single algorithm, and evaluated the algorithm on selected data sets. There has been relatively little emphasis on describing the common features that are important if an algorithm is to have good performance. This paper describes the key features, with particular emphasis on algorithms for weighted fixed spectrum problems. The use of algorithms handling weighted constraints has become increasingly common in recent years. The advantages and disadvantages of weighting constraints are demonstrated. [ABSTRACT FROM AUTHOR]
- Published
- 2001
- Full Text
- View/download PDF
30. Constraint Generation for Network Reliability Problems.
- Author
-
Shaio, Jack
- Subjects
MATHEMATICS ,MATHEMATICAL programming ,RELIABILITY in engineering ,OPERATIONS research ,DYNAMICS - Abstract
This paper presents a constraint generation approach to the network reliability problem of adding spare capacity at minimum cost that allows the traffic on a failed link to be rerouted to its destination. Any number of non-simultaneous link failures can be part of the requirements on the spare capacity. The key result is a necessary and sufficient condition for a multicommodity flow to exist, which is derived in the appendix. Computational results on large numbers of random networks are presented. [ABSTRACT FROM AUTHOR]
- Published
- 2001
- Full Text
- View/download PDF
31. An Augmented Arborescence Formulation for the Two-Level Network Design Problem.
- Author
-
Gouvela, Luis and Telhad, João
- Subjects
MATHEMATICS ,LAGRANGE equations ,DYNAMICS ,LINEAR programming ,MATHEMATICAL programming - Abstract
In this paper we discuss formulations for the Two Level Network Design (TLND) problem. In particular, we present an arborescence based formulation with extra constraints guaranteeing that the set of primary nodes is spanned by primary edges. This characterization suggests an arborescence based Lagrangian relaxation where the extra constraints are dualized. Although the Linear Programming (LP) value of the new formulation is proved to be theoretically weaker than the LP bound given by the flow based formulation presented by Balakrishnan, Magnanti and Mirchandani, our computational results show that for certain classes of instances the two LP bounds are quite close. Our results also show that the Lagrangian relaxation based method is quite efficient, providing a reasonable alternative to handle the problem. [ABSTRACT FROM AUTHOR]
- Published
- 2001
- Full Text
- View/download PDF
32. A Learning Framework for Neural Networks Using Constrained Optimization Methods.
- Author
-
Perantonis, Stavros J., Ampazis, Nikolaos, and Virvilis, Vassilis
- Subjects
ARTIFICIAL neural networks ,MATHEMATICAL optimization ,STOCHASTIC convergence ,LEARNING ,OPERATIONS research ,MATHEMATICS - Abstract
Conventional supervised learning in neural networks is carried out by performing unconstrained minimization of a suitably defined cost function. This approach has certain drawbacks, which can be overcome by incorporating additional knowledge in the training formalism. In this paper, two types of such additional knowledge are examined: Network specific knowledge (associated with the neural network irrespectively of the problem whose solution is sought) or problem specific knowledge (which helps to solve a specific learning task). A constrained optimization framework is introduced for incorporating these types of knowledge into the learning formalism. We present three examples of improvement in the learning behaviour of neural networks using additional knowledge in the context of our constrained optimization framework. The two network specific examples are designed to improve convergence and learning speed in the broad class of feedforward networks, while the third problem specific example is related to the efficient factorization of 2-D polynomials using suitably constructed sigma-pi networks. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
33. An Interior Point Algorithm for Computing Saddle Points of Constrained Continuous Minimax.
- Author
-
Žaković, Stanislav, Pantelides, Costas, and Rustem, Berc
- Subjects
APPROXIMATION theory ,CHEBYSHEV approximation ,LOGARITHMS ,ALGORITHMS ,MATHEMATICAL variables ,MATHEMATICS - Abstract
The aim of this paper is to present an algorithm for finding a saddle point to the constrained minimax problem. The initial problem is transformed into an equivalent equality constrained problem, and then the interior point approach is used. To satisfy the original inequality constraints a logarithmic barrier function is used and special care is given to step size parameter to keep the variables within permitted boundaries. Numerical results illustrating the method are given. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
34. The Capacitated Minimal Spanning Tree Problem: An experiment with a hop-indexed model.
- Author
-
Gouveia, Luis and Martins, Pedro
- Subjects
TELECOMMUNICATION ,DIGITAL communications ,COMPUTER networks ,COST (Computer program language) ,TREE graphs ,GRAPH theory ,MATHEMATICAL analysis ,MATHEMATICS - Abstract
The Capacitated Minimal Spanning Tree Problem (CMSTP) is to find a minimal spanning tree with an additional cardinality constraint on the size of the subtrees off of a given root node. This problem is closely related to the design of centralized networks where one wants to link, with minimum cost, several terminals to a given root node (typically, a concentrator or a computer center). In this paper, we present a new extended and compact formulation for the CMSTP. This formulation is a ‘hop-indexed’ single-commodity flow model and generalizes a well-known single-commodity flow model. We introduce a new set of valid inequalities, denoted by ‘hop ordering’ inequalities, which are not redundant for the LP relaxation of the new formulation. We present a new cutting plane method for the CMSTP with the new formulation as the initial model and using constraint generation for adding ‘hop-ordering’ constraints and generalized subtour elimination constraints to the current LP model. We present computational results from a set of tests with 40 and 80 nodes which compare our lower bounds with the bounds given by other known methods. The main contribution of our proposed method is to considerably close previously known gaps for tests which have been classified as hard ones, namely tightly capacitated tests with the root in the comer of the grid of points. [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
35. Locating a facility on a network with multiple median-type objectives.
- Author
-
Ramos, R. M., Ramos, M. T., Colebrook, M., and Sicilia, J.
- Subjects
LOCATION problems (Programming) ,MATHEMATICAL programming ,STANDARD deviations ,ANALYSIS of variance ,MEDIAN (Mathematics) ,STATISTICS ,MATHEMATICAL analysis ,MATHEMATICS - Abstract
We consider the problem of locating a single facility on a network in the presence of r ≥ 2 median-type objectives, represented by r sets of edge weights (or lengths) corresponding to each of the objectives. When r = 1, then one gets the classical 1-median problem where only the vertices need to be considered for determining the optimal location (Hakimi [1]). The paper examines the case when r ≥ 2 and provides a method to determine the non-dominated set of points for locating the facility. [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
36. A tabu search approach to the uncapacitated facility location problem.
- Author
-
Al-Sultan, K. S. and Al-Fawzan, M. A.
- Subjects
ALGORITHMS ,ALGEBRA ,FOUNDATIONS of arithmetic ,MATHEMATICAL analysis ,MATHEMATICS - Abstract
In this paper, the uncapacitated facility location problem is considered, A tabu search algorithm for solving this problem is proposed. The algorithm is tested on some standard test problems taken from literature and its performance is compared with the known optimal solutions. Computational results show that the proposed algorithm produces optimal solutions for all test problems, and that it is very efficient in terms of time compared to existing algorithms in the literature. [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
37. Simulated Jumping.
- Author
-
Amin, Shara
- Subjects
COMBINATORIAL optimization ,COMBINATORICS ,MATHEMATICAL optimization ,SIMULATED annealing ,MATHEMATICAL analysis ,MATHEMATICS - Abstract
This paper describes a novel approach for solving combinatorial optimisation problems called Simulated Jumping. It is based on ideas from spin-glasses, simulated annealing and self-organisation. We start from a low temperature, and the system is then subjected to a rapid heating and cooling process (a shaking process). This process is controlled by the system's energy in a self-organised manner. The heating and cooling process will continuously melt and freeze local regions; this process pushes the system out of local minima and hence minimises the energy function. Application of the Simulated Jumping method to the Quadratic Assignment and Asymmetric Travelling Salesman problems gives promising results. [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
38. Gains and costs of information in stochastic programming.
- Author
-
Zvi Artstein
- Subjects
STOCHASTIC programming ,MATHEMATICAL analysis ,LINEAR programming ,MATRICES (Mathematics) ,MATHEMATICAL programming ,MATHEMATICS - Abstract
The paper reviews the role of sensors as a variable depicting information in a stochastic program. Through examples, and with mathematical analysis of random measures, it is shown how policy variables affect the sensors in a given problem. Sensors are amenable to mathematical derivations. It is shown how the trade-off between the gain from introducing new information into the problem, and the cost of that action, can be addressed. Suggestions for further investigation are offered. [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
39. Characterizable fuzzy preference structures.
- Author
-
de Walle, Bartel Van, de Baets, Bernard, and Kerre, Etienne
- Subjects
AUTOMORPHISMS ,FUZZY algorithms ,FUZZY mathematics ,FUZZY arithmetic ,FUZZY sets ,GROUP theory ,MATHEMATICS ,OPERATIONS research - Abstract
In this paper, we study the existence, construction and reconstruction of fuzzy preference structures. Starting from the definition of a classical preference structure, we propose a natural definition of a fuzzy preference structure, merely requiring the fuzzification of the set operations involved. Upon evaluating the existence of these structures, we discover that the idea of fuzzy preferences is best captured when fuzzy preference structures are defined using a Lukasiewicz triplet. We then proceed to investigate the role of the completeness condition in these structures. This rather extensive investigation leads to the proposal of a strongest completeness condition, and results in the definition of a one-parameter class of fuzzy preference structures. Invoking earlier results by Fodor and Roubens, the construction of these structures from a reflexive binary fuzzy relation is then easily obtained. The reconstruction of such a structure from its fuzzy large preference relation - inevitable to obtain a full characterization of these structures in analogy to the classical case - is more cumbersome. The main result of this paper is the discovery of a non-trivial characterizing condition that enables us to fully characterize the members of a two-parameter class of fuzzy preference structures in terms of their fuzzy large preference relation. As a remarkable side-result, we discover three limit classes of characterizable fuzzy preference structures, traces of which are found throughout the preference modelling literature. [ABSTRACT FROM AUTHOR]
- Published
- 1998
- Full Text
- View/download PDF
40. Extended partial orders: A unifying structure for abstract choice theory.
- Author
-
Nehring, Klaus and Puppe, Clemens
- Subjects
MATHEMATICAL functions ,MATHEMATICAL analysis ,DIFFERENTIAL equations ,OPERATIONS research ,MATHEMATICS ,SYSTEMS theory - Abstract
The concept of a strict extended partial order (SEPO) has turned out to be very useful in explaining (resp. rationalizing) non-binary choice functions. The present paper provides a general account of the concept of extended binary relations, i.e. relations between subsets and elements of a given universal set of alternatives. In particular, we define the concept of a weak extended partial order (WEPO) and show how it can be used in order to represent rankings of Opportunity sets that display a ‘preference for opportunities’. We also clarify the relationship between SEPOs and WEPOs, which involves a non-trivial condition, called ‘strict properness’. Several characterizations of strict (and weak) properness are provided, based on which we argue for properness as an appropriate condition demarcating ‘choice based’ preference. [ABSTRACT FROM AUTHOR]
- Published
- 1998
- Full Text
- View/download PDF
41. A statistical generalized programming algorithm for stochastic optimization problems.
- Author
-
Gaivoronski, A. A., Messina, E., and Sciomachen, A.
- Subjects
LINEAR programming ,MATHEMATICAL programming ,PRODUCTION scheduling ,STOCHASTIC analysis ,MATHEMATICAL analysis ,MATHEMATICAL optimization ,MATHEMATICS - Abstract
In this paper, we are concerned with an algorithm which combines the generalized linear programming technique proposed by Dantzig and Wolfe with the stochastic quasi-gradient method in order to solve stochastic programs with recourse. In this way, we overcome the difficulties arising in finding the exact values of the objective function of recourse problems by replacing them with the statistical estimates of the function. We present the basic steps of the proposed algorithm focusing our attention on its implementation alternatives aimed at improving both the convergence and computational performances. The main application areas are mentioned and some computational experience in the validation of our approach is reported. Finally, we discuss the possibilities of parallelization of the proposed algorithmic schemes. [ABSTRACT FROM AUTHOR]
- Published
- 1995
42. Some probabilistic properties of the nearest adjoining order method and its extensions.
- Author
-
Klukowski, Leszek
- Subjects
ERROR analysis in mathematics ,ERRORS ,PROBABILITY theory ,MATHEMATICAL statistics ,NUMERICAL analysis ,STATISTICS ,MATHEMATICS - Abstract
In this paper, some probabilistic properties of the nearest adjoining order (NAO) method are presented. They have been obtained under weaker assumptions than those commonly used. i.e. it is not assumed that comparisons are not independent and that probability of comparison errors are known. The results presented comprise the evaluation of the probability of obtaining an errorless solution with the use of the NAO method; asymptotic properties of this solution derived under the assumption that comparisons of different pairs (i.e. pairs x
i , xj and xi , xz for i ≅ r,s and j ≅ r, s) arc not correlated - for the case of one expert. An extension of results for the case of N » 1 independent experts is also presented. This extension is accomplished by including an additional step - the aggregation of comparisons made by all experts for each pair of objects. Two ways of such an aggregation are analyzed: the averaging of experts' opinions and the majority principle. In the latter case, the result of the comparison is the same as the opinion of the majority of experts. The results obtained indicate an exponential convergence of the probability of the NAO solution to an errorless one in both cases. However, an application of the majority principle leads to a minimization problem, which is the same as in the case of N = 1 and is much simpler than that corresponding to averaging of comparisons. [ABSTRACT FROM AUTHOR]- Published
- 1994
- Full Text
- View/download PDF
43. Modeling attitudes towards uncertainty and risk through the use of Choquet integral.
- Author
-
Chateauneuf, Alain
- Subjects
CHOQUET theory ,EXPECTED utility ,RISK ,UNCERTAINTY ,AXIOMS ,MATHEMATICS - Abstract
The aim of this paper is to present in a unified framework a survey of some results related to Choquet Expected Utility (CEU) models, a promising class of models introduced separately by Quiggin [35], Yaari [48] and Schmeidler [40, 41] which allow to separate attitudes towards uncertainty (or risk) from attitudes towards wealth, while respecting the first order stochastic dominance axiom. [ABSTRACT FROM AUTHOR]
- Published
- 1994
- Full Text
- View/download PDF
44. MINIMAL LENGTH TREE NETWORKS ON THE UNIT SPHERE.
- Author
-
Dolan, John, Weiss, Richard, and Smith, J. MacGregor
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,OPERATIONS research ,SIMULATION methods & models ,DECISION trees ,MATHEMATICAL models ,MATHEMATICS ,ALGORITHMS - Abstract
This paper considers the problem of finding minimal length tree networks on the unit sphere Φ of a given point set (V) where distance is measured along great circular arcs. The related problems of finding a Steiner Minimal Tree SMT (V) and of finding a Minimum Spanning Tree MST(V) are treated through a simplicial decomposition technique based on computing the Delaunay Triangulation DT (V) and the Voronoi Diagram VD(V) of the given point set. O (N log N) algorithms for computing DT(V), VD(V), and WST(V) as well as an O(N log N) heuristic for finding a sub-optimal SMT(V) solution are presented, together with experimental results for randomly distributed points on Φ. [ABSTRACT FROM AUTHOR]
- Published
- 1991
45. BOUNDING SEPARABLE RECOURSE FUNCTIONS WITH LIMITED DISTRIBUTION INFORMATION.
- Author
-
Birge, John R. and Dulá, José H.
- Subjects
MATHEMATICAL functions ,INTEGRALS ,STOCHASTIC programming ,LINEAR programming ,MATHEMATICAL statistics ,MATHEMATICS - Abstract
The recourse function in a stochastic program with recourse can be approximated by separable functions of the original random variables or linear transformations of them. The resulting bound then involves summing simple integrals. These integrals may themselves be difficult to compute or may require more information about the random variables than is available. In this paper, we show that a special class of functions has an easily computable bound that achieves the best upper bound when only first and second moment constraints are available. [ABSTRACT FROM AUTHOR]
- Published
- 1991
- Full Text
- View/download PDF
46. STOCHASTIC PROGRAMMING WITH RANDOM PROCESSES.
- Author
-
Cipra, Tomáš
- Subjects
STOCHASTIC programming ,LINEAR programming ,MATHEMATICAL optimization ,OPERATIONS research ,MATHEMATICAL programming ,MATHEMATICS - Abstract
Three possible approaches to stochastic programming problems defined in time (so that they contain random processes) are described in this paper: (1) an application of the extremal theory of random processes; (2) an exponential penalty model approach related to scenario analysis; (3) a modification of the entropic penalty approach. Explicit results are derived for some special cases. [ABSTRACT FROM AUTHOR]
- Published
- 1991
- Full Text
- View/download PDF
47. ADAPTIVE APPROACHES TO STOCHASTIC PROGRAMMING.
- Author
-
McAllister, Patrick H.
- Subjects
STOCHASTIC programming ,LINEAR programming ,MATHEMATICAL programming ,ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICS - Abstract
Economists have found a need to model agents who behave in ways that are not consistent with the traditional notions of rational behavior under uncertainty but that are oriented in some looser manner toward achieving ‘good’ outcomes. Adaptation over time in a myopic manner, rather that forward-looking optimization, has been proposed as one such model of behavior that displays bounded rationality. This paper investigates the relationship between adaptation as a model of behavior and as an algorithmic approach that has been used in computing solutions to optimization problems. It describes a specific adaptive model of behavior in discrete choice problems, one that is closely related to adaptive algorithms for optimization, and shows that this model can be fruitfully applied in studying several economic issues. [ABSTRACT FROM AUTHOR]
- Published
- 1991
- Full Text
- View/download PDF
48. ON THE CONSTRUCTION OF ε-OPTIMAL STRATEGIES IN PARTIALLY OBSERVED MDPs.
- Author
-
Runggaldier, Wolfgang J.
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,MATHEMATICS ,MAXIMA & minima ,OPERATIONS research ,SIMULATION methods & models - Abstract
The purpose of the paper is to give a survey of methods, partly derived by the author in joint work with other researchers, concerning the problem of constructing e-optimal strategies for partially observable MDPs. The methods basically consist in transforming the problem into one of approximation: Starting from the original problem a sequence of approximating problems is constructed such that: (i) For each approximating problem an optimal strategy can actually be computed, (ii) Given ϵ » 0, there exists an approximating problem such that the optimal strategy for the latter is ϵ-optimal for the original problem. [ABSTRACT FROM AUTHOR]
- Published
- 1991
- Full Text
- View/download PDF
49. A MINIMUM LENGTH COVERING SUBGRAPH OF A NETWORK.
- Author
-
Tae Ung Kim, Lowe, Timothy J., Ward, James E., and Francis, Richard L.
- Subjects
LOCATION problems (Programming) ,MATHEMATICAL programming ,LINEAR programming ,OPERATIONS research ,MATHEMATICAL optimization ,MATHEMATICS - Abstract
This paper concerns the problem of locating a central facility on a connected network N. The network, N, could be representative of a transport system, while the central facility takes the form of a connected subgraph of N. The problem is to locate a central facility of minimum length so that each of several demand points on N is covered by the central facility a demand point at v
i in N is covered by the central facility if the shortest path distance between vi and the closest point in the central facility does not exceed a parameter ri . This location problem is NP-hard, but for certain special cases, efficient solution methods are available. [ABSTRACT FROM AUTHOR]- Published
- 1989
- Full Text
- View/download PDF
50. DETERMINATION OF EFFICIENT SOLUTIONS FOR POINT-OBJECTIVE LOCATIONAL DECISION PROBLEMS.
- Author
-
Pelegrin, B. and Fernandez, F. R.
- Subjects
MODULES (Algebra) ,ALGORITHMS ,MATHEMATICAL functions ,FINITE groups ,MATHEMATICAL analysis ,MATHEMATICS - Abstract
In this paper we study the point-objective problem of locating in R
2 a facility serving a finite number of customers to minimize the travel time, or the distance, to each customer. Travel times, or distances, are measured by going in the directions of some given vectors which means that, under some conditions, are evaluated by a norm function. An algorithm is proposed to find all the quasi-efficient points and all the efficient points (alternately or strictly), for any given set of travelling directions. Consequently, the problem of efficiency is addressed in a general framework. [ABSTRACT FROM AUTHOR]- Published
- 1989
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.