Search

In matrix theory, Fu and Markham showed using majorization technique that if a Hermitian matrix satisfies certain conditions, then the matrix must be block-diagonal. In this paper, we extend this result to the setting of simple Euclidean Jordan algebras by using the Cauchy interlacing theorem and the Schur complement Cauchy interlacing theorem. [ABSTRACT FROM AUTHOR]

A matrix M∈ R is said to be a column sufficient matrix if the solution set of LCP( M, q) is convex for every q∈ R. In a recent article, Qin et al. (Optim. Lett. 3:265-276, ) studied the concept of column sufficiency property in Euclidean Jordan algebras. In this paper, we make a further study of this concept and prove numerous results relating column sufficiency with the Z and Lypaunov-like properties. We also study this property for some special linear transformations. [ABSTRACT FROM AUTHOR]

This paper analyzes, and thus reveals the structure of the stable invariant subspace of the related Hamiltonian matrix arising from the measurement feedback H∞-control problem. Using this, it presents another method for the verification of the admissibility of the controller derived by Doyle et al. in 1989. The method not only eliminates unnecessary assumptions on stabilizability and detectability, but also gives deeper insight into the relationship among the stable parts of the associated matrices. [ABSTRACT FROM AUTHOR]

Recently, we have extended SDP by adding a quadratic term in the objective function and give a potential reduction algorithm using NT directions. This paper presents a predictor-corrector algorithm using both Dikin-type and Newton centering steps and studies properties of Dikin-type step. In this algorithm, when the condition K(XS) is less than a given number K0, we use Dikin-type step. Otherwise, Newton centering step is taken. In both cases, step-length is determined by line search. We show that at least a constant reduction in the potential function is guaranteed. Moreover the algorithm is proved to terminate in O(√n log(l/ϵ)) steps. In the end of this paper, we discuss how to compute search direction (ΔX, ΔS) using the conjugate gradient method. [ABSTRACT FROM AUTHOR]

This paper considers the problem of approximating a given symmetric matrix by a symmetric matrix with a prescribed spectrum so that the Frobenius norm of the matrix difference is minimized. By the introduction of a variable search direction, a new convergent algorithm for solving the problem is derived, which is guaranteed to be convergent and is capable of achieving a fast rate of convergence. It is shown that the set of fixed points of the proposed algorithm coincides with the set of equilibrium points of the original double bracket equation. A numerical example is presented to demonstrate superior performance of the proposed algorithm over a standard double bracket algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study a method for global optimization of increasing positively homogeneous functions over the unit simplex, which is a version of the cutting angle method. Some properties of the auxiliary subproblem are studied and a special algorithm for its solution is proposed. A cutting angle method based on this algorithm allows one to find an approximate solution of some problems of global optimization with 50 variables. Results of numerical experiments are discussed. [ABSTRACT FROM AUTHOR]

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]

In this paper, we introduce an additional constraint to the one-dimensional variable sized bin packing problem. Practically, some of items have to be packed separately in different bins due to their specific requirement. Therefore, these items are labelled as different types. The bins can be used to pack either any type of items if they are empty originally or the same type of items as what they already have. We model the problem as a type-constrained and variable sized bin packing problem (TVSBPP), and solve it via a branch and bound method. An efficient backtracking procedure is proposed to improve the efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

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]

Pairwise comparison is a popular method for establishing the relative importance of n objects. Its main purpose is to get a set of weights (priority vector) associated with the objects. When the information gathered from the decision maker does not verify some rational properties, it is not easy to search the priority vector. Goal programming is a flexible tool for addressing this type of problem. In this paper, we focus on a group decision-making scenario. Thus, we analyze different methodologies for getting a collective priority vector. The first method is to aggregate general pairwise comparison matrices (i.e., matrices without suitable properties) and then get the priority vector from the consensus matrix. The second method proposes to get the collective priority vector by formulating an optimization problem without determining the consensus pairwise comparison matrix beforehand. [ABSTRACT FROM AUTHOR]

We consider an open queueing network consisting of servers linked in an arbitrary configuration with exponential service times and separated by intermediate finite buffers. The model allows any number of saturated servers (never starved) and exit servers (never blocked). The considered blocking mechanism is blocking-after-service. In the case of simultaneous blocking, blocked customers enter the destination node on a first-blocked-first- enter basis. If feedback loops exist in the network, deadlocks may arise. We assume that a deadlock is detected and resolved instantaneously by transferring all the blocked customers simultaneously. In this paper, we present an approximation method to analyze this kind of networks. The method decomposes the original network into subsystems. Each subsystem is composed of one or many upstream servers and one downstream server, separated by a finite buffer. The upstream and downstream servers are characterized by exponential service time distributions. Based on the symmetrical approach [2]. we develop an algorithm to determine the unknown parameters corresponding to each subsystem. The class of models considered in this paper includes the class of open loss models for feed-forward networks considered by Lee and Pollock [11]. For this class of models, we can show that the system of equations in our algorithm is equivalent to the one used in the algorithm proposed by Lee and Pollock. As a result, our algorithm provides the same results as the algorithm of Lee and Pollock for this class of models. However, it is observed that our algorithm takes less CPU execution time than the one proposed by Lee and Pollock. For the cases of networks with feedback loops, extensive numerical experiments show that the new algorithm, in general, converges very fast and yields accurate results compared with those obtained by simulation as long as deadlocks do not occur too frequently. Moreover, for the merge configuration, we provide the proof of the convergence of the algorithm as well as the existence and uniqueness of the solution by exploiting the properties associated with a symmetric approach. [ABSTRACT FROM AUTHOR]

In this paper, foundations of a new approach for solving vector optimization problems are introduced. Generalized Lagrangian duality, related for the first time with vector optimization, provides new scalarization techniques and allows for the generation of efficient solutions for problems which are not required to satisfy any convexity assumptions. [ABSTRACT FROM AUTHOR]

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]

In this paper, a new notion of exceptional family of elements (EFE) for a pair of functions involved in the implicit complementarity problem (ICP) is introduced. Based upon this notion and the Leray-Schauder Alternative, a general alternative is obtained which gives more general existence theorems for the implicit complementarity problem. Finally, via the techniques of continuous selections, these existence theorems are extended to the multi-valued implicit complementarity problems (MIPS). [ABSTRACT FROM AUTHOR]

In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem. [ABSTRACT FROM AUTHOR]

Many optimization problems can be expressed naturally in a recursive manner. Problems with a dynamic structure are commonly expressed in this way especially when they are to be solved by dynamic programming. Many stochastic linear programming problems have an underlying Markov structure, and for these a recursive definition is natural. Real-world examples of such problems are often so large that it is not practical to solve them without a modeling language. No existing algebraic modeling language provides a natural way of specifying a model using a dynamic programming recurrence. This paper describes the advantages of recursive model definition for stochastic linear programming problems, and presents the language constructs necessary to implement this within an algebraic modeling language. [ABSTRACT FROM AUTHOR]

In the present paper we describe a new, class of algorithms for solving Diophantine systems of equations in integer arithmetic. This algorithm, designated as the integer ABS (iABS) algorithm, is based on the ABS methods in the real space, with extensive modifications to ensure that all calculations remain in the integer space. Importantly, the iABS solves Diophantine systems of equations without determining the Hermite normal form. The algorithm is suitable for solving determined, over- or underdetermined, full rank or rank deficient linear integer equations. We also present a scaled integer ABS system and two special cases for solving general Diophantine systems of equations. In the scaled symmetric iABS (ssiABS), the Abaffian matrix Hi is symmetric, allowing that only half of its elements need to be calculated and stored. The scaled non-symmetric iABS system (snsiABS) provides more freedom in selecting the arbitrary parameters and thus the maximal values of Hi can be maintained at a certainly lower level. In addition to the above theoretical results, we also provide numerical experiments to test the performance of the ssiABS and the snsiABS algorithms. These experiments have confirmed the suitability of the iABS system for practical applications. [ABSTRACT FROM AUTHOR]

Let S: [0,1] ↵ [0,1] be a nonsingular transformation and let P : L1 ( 0 , 1 ) ↵ L1(0,1) be the corresponding Frobenius-Perron operator. In this paper we propose a parallel algorithm for computing a fixed density of P, using Ulam's method and a modified Monte Carlo approach. Numerical results are also presented. [ABSTRACT FROM AUTHOR]

This paper studies a class of infinite dimensional linear programming problems known as the general capacity problem. A relaxed cutting plane algorithm is proposed. A convergence proof together with some analysis of the results produced by the algorithm are given. A numerical example is also included to illustrate the computational procedure. [ABSTRACT FROM AUTHOR]

The innovation design and process engineering, two inevitable interrelated stages in the development of a new technology, are captured in this paper as a non-antagonistic leader-follower target-pursuit system subject to uncertainty in market and technology changes. The innovation design team (leader) is driven by market needs, while the process engineering team (follower) then strives to attain suitable production means with a focus on technological availability and profitability. In face of uncertainty in market changes and technological advances, the proposed strategic regulation of overlaps (SRO) model addresses relevant scheduling issues such as when to start, to overlap, and then to end the development activities. We obtain the optimal timing of the overlaps in these development activities. An algorithm is developed to calculate the optimal overlap schedule which is easy to be implemented for realistic applications. [ABSTRACT FROM AUTHOR]

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]

The paper surveys more than forty characterizations of scoring methods for preference aggregation and contains one new result. A general scoring operator is self-consistent if alternative i is assigned a greater score than j whenever i gets no worse (better) results of comparisons and its ‘opponents’ are assigned, respectively, greater (no smaller) scores than those of j . We prove that self-consistency is satisfied if and only if the application of a scoring operator reduces to the solution of a homogeneous system of algebraic equations with a monotone function on the left-hand side. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of determining lower and upper bounds on probabilities of atomic propositions in sets of logical formulas represented by digraphs. We establish a sharp upper bound, as well as a lower bound that is not in general sharp. We show further that under a certain condition the lower bound is sharp. In that case, we obtain a closed form solution for the possible probabilities of the atomic propositions. [ABSTRACT FROM AUTHOR]

This paper deals with so-called vague matrices, the columns of which are convex sets. A special ‘square’ problem of the vague optimization is analysed. The results form a base for the subsequent outline of an algorithm for solving the LP-problem with a vague matrix. The paper is concluded by the discussion of possible types of degeneracy. [ABSTRACT FROM AUTHOR]

The DFP algorithm of unconstrained optimization possesses excellent properties of convergence for convex functions. However, a convergence theory of the DFP algorithm without the convexity assumption has not yet been established. This paper gives the following result: If the objective function is suitably smooth, and if the DFP algorithm produces a convergent point sequence, then the limit point of the sequence is a critical point of the objective function. Also, some open questions are mentioned. [ABSTRACT FROM AUTHOR]

Based on the analysis of the basic schemes of a variety of population-based metaheuristics (PBMH), the main components of PBMH are described with functional relationships in this paper and a unified framework (UF) is proposed for PBMH to provide a comprehensive way of viewing PBMH and to help understand the essential philosophy of PBMH from a systematic standpoint. The relevance of the proposed UF and some typical PBMH methods is illustrated, including particle swarm optimization, differential evolution, scatter search, ant colony optimization, genetic algorithm, evolutionary programming, and evolution strategies, which can be viewed as the instances of the UF. In addition, as a platform to develop the new population-based metaheuristics, the UF is further explained to provide some designing issues for effective/efficient PBMH algorithms. Subsequently, the UF is extended, namely UFmeme to describe the Memetic Algorithms (MAs) by adding local search (memetic component) to the framework as an extra-feature. Finally, we theoretically analyze the asymptotic convergence properties of PBMH described by the UF and MAs by the UFmeme. [ABSTRACT FROM AUTHOR]

Data Envelopment Analysis (DEA) models with undesirable inputs and outputs have been frequently discussed in DEA literature, e.g., via data transformation. These studies were scatted in the literature, and often confined to some particular applications. In this paper we present a systematic investigation on model building of DEA without transferring undesirable data. We first describe the disposability assumptions and a number of different performance measures in the presence of undesirable inputs and outputs, and then discuss different combinations of the disposability assumptions and the metrics. This approach leads to a unified presentation of several classes of DEA models with undesirable inputs and/or outputs. [ABSTRACT FROM AUTHOR]

Given a graph G=( V, E), the Hamiltonian completion number of G, HCN( G), is the minimum number of edges to be added to G to make it Hamiltonian. This problem is known to be $\mathcal{NP}$ -hard even when G is a line graph. In this paper, local search algorithms for finding HCN( G) when G is a line graph are proposed. The adopted approach is mainly based on finding a set of edge-disjoint trails that dominates all the edges of the root graph of G. Extensive computational experiments conducted on a wide set of instances allow to point out the behavior of the proposed algorithms with respect to both the quality of the solutions and the computation time. [ABSTRACT FROM AUTHOR]

In this paper, a linear bilevel programming problem (LBP) is considered. Local optimality conditions are derived. They are based on the notion of equilibrium point of an exact penalization for LBP. It is described how an equilibrium point can be obtained with the simplex method. It is shown that the information in the simplex tableaux can be used to get necessary and sufficient local optimality conditions for LBP. Based on these conditions, a simplex type algorithm is proposed, which attains a local solution of LBP by moving in equilibrium points. A numerical example illustrates how the algorithm works. Some computational results are reported. [ABSTRACT FROM AUTHOR]

A fixed charge capacitated multicommodity network design problem on undirected networks is addressed. At the present time, there exists no algorithm that can solve large instances, common in several applications, in a reasonable period of time. This paper presents an efficient procedure using a scatter search framework. Computational experiments on a large set of randomly generated problems show that this procedure is capable of finding good solutions to large-scale problems within a reasonable amount of time. [ABSTRACT FROM AUTHOR]

In 1, we have previously observed that, in a chordal graph G, the maximum number of independent r-cliques (i.e., of vertex disjoint subgraphs of G, each isomorphic to K r, with no edges joining any two of the subgraphs) equals the minimum number of cliques of G that meet all the r-cliques of G. When r = 1, this says that chordal graphs have independence number equal to the clique covering number. When r = 2, this is equivalent to a result of Cameron (1989), and it implies a well known forbidden subgraph characterization of split graphs. In this paper we consider a weighted version of the above min-max optimization problem. Given a chordal graph G, with a nonnegative weight for each r-clique in G, we seek a set of independent r-cliques with maximum total weight. We present two algorithms to solve this problem, based on the principle of complementary slackness. The first one operates on a graph derived from G, and is an adaptation of an algorithm of Farber (1982). The second one improves the performance by reducing the number of constraints of the linear programs. Both results produce a min-max relation. When the algorithms are specialized to the situation in which all the r-cliques have the same weight, we simplify the algorithms reported in 1, although these simpler algorithms are not as efficient. As a byproduct, we also obtain new elementary proofs of the above min-max result. [ABSTRACT FROM AUTHOR]

This paper presents an adaptive memory-based method for solving the Capacitated Vehicle Routing Problem (CVRP), called BoneRoute. The CVRP deals with the problem of finding the optimal sequence of deliveries conducted by a fleet of homogeneous vehicles, based at one depot, to serve a set of customers. The computational performance of the BoneRoute was found to be very efficient, producing high quality solutions over two sets of well known case studies examined. [ABSTRACT FROM AUTHOR]

Systematic backtracking is used in many constraint solvers and combinatorial optimisation algorithms. It is complete and can be combined with powerful search pruning techniques such as branch-and- bound, constraint propagation and dynamic variable ordering. However, it often scales poorly to large problems. Local search is incomplete, and has the additional drawback that it cannot exploit pruning techniques, making it uncompetitive on some problems. Nevertheless its scalability makes it superior for many large applications. This paper describes a hybrid approach called Incomplete Dynamic Backtracking, a very flexible form of backtracking that sacrifices completeness to achieve the scalability of local search. It is combined with forward checking and dynamic variable ordering, and evaluated on three combinatorial problems: on the n-queens problem it out-performs the best local search algorithms; it finds large optimal Golomb rulers much more quickly than a constraint-based backtracker. and better rulers than a genetic algorithm; and on benchmark graphs it finds larger cliques than almost all other tested algorithms. We argue that this form of backtracking is actually local search in a space of consistent partial assignments, offering a generic way of combining standard pruning techniques with local search. [ABSTRACT FROM AUTHOR]

Recently, various algebraic integer programming (IP) solvers have been proposed based on the theory of Gröbner bases. The main difficulty of these solvers is the size of the Gröbner bases generated. In algorithms proposed so far, large Gröbner bases are generated by either introducing additional variables or by considering the generic IP problem IPA, C. Some improvements have been proposed such as Hosten and Sturmfels' method (GRIN) designed to avoid additional variables and Thomas' truncated Gröbner basis method which computes the reduced Gröbner basis for a specific IP problem IPA, C(b) (rather than its generalisation IPA, C). In this paper we propose a new algebraic algorithm for solving IP problems. The new algorithm, called Minimised Geometric Buchberger Algorithm, combines Hosten and Sturmfels' GRIN and Thomas' truncated Gröbner basis method to compute the fundamental segments of an IP problem IPA, C directly in its original space and also the truncated Gröbner basis for a specific IP problem IPA, C(b). We have carried out experiments to compare this algorithm with others such as the geometric Buchberger algorithm, the truncated geometric Buchberger algorithm and the algorithm in GRIN. These experiments show that the new algorithm offers significant performance improvement. [ABSTRACT FROM AUTHOR]

This paper introduces two tokens of syntax for algebraic modeling languages that are sufficient to model a wide variety of stochastic optimization problems. The tokens are used to declare random parameters and to define a precedence relationship between different random events. It is necessary to make a number of assumptions in order to use this syntax, and it is through these assumptions, which cover the areas of model structure, time, replication, and stages, that we can attain a deeper understanding of this class of problem. [ABSTRACT FROM AUTHOR]

In this paper, an adaptive algorithm based on the normal equations for solving large nonsymmetric linear systems is presented. The new algorithm is a hybrid method combining polynomial preconditioning with the CGNR method. Residua] polynomial is used in the preconditioning to estimate the eigenvalues of the s.p.d. matrix ATA, and the residual polynomial is generated from several steps of CGNR by recurrence. The algorithm is adaptive during its implementation. The robustness is maintained, and the iteration convergence is speeded up. A numerical test result is also reported. [ABSTRACT FROM AUTHOR]

In this paper, a functional inequality constrained optimization problem is studied using a discretization method and an adaptive scheme. The problem is discretized by partitioning the interval of the independent parameter. Two methods are investigated as to how to treat the discretized optimization problem. The discretization problem is firstly converted into an optimization problem with a single nonsmooth equality constraint. Since the obtained equality constraint is nonsmooth and does not satisfy the usual constraint qualification condition, relaxation and smoothing techniques are used to approximate the equality constraint via a smooth inequality constraint. This leads to a sequence of approximate smooth optimization problems with one constraint. An adaptive scheme is incorporated into the method to facilitate the computation of the sum in the inequality constraint The second method is to apply an adaptive scheme directly to the discretization problem. Thus a sequence of optimization problems with a small number of inequality constraints are obtained. Convergence analysis for both methods is established. Numerical examples show that each of the two proposed methods has its own advantages and disadvantages over the other. [ABSTRACT FROM AUTHOR]

We consider the problem of determining an optimal driving strategy in a train control problem with a generalised equation of motion. We assume that the journey must be completed within a given time and seek a strategy that minimises fuel consumption. On the one hand we consider the case where continuous control can be used and on the other hand we consider the case where only discrete control is available. We pay particular attention to a unified development of the two cases. For the continuous control problem we use the Pontryagín principle to find necessary conditions on an optimal strategy and show that these conditions yield key equations that determine the optimal switching points. In the discrete control problem, which is the typical situation with diesel-electric locomotives, we show that for each fixed control sequence the cost of fuel can be minimised by finding the optimal switching times. The corresponding strategies are called strategies of optimal type and in this case we use the Kuhn-Tucker equations to find key equations that determine the optimal switching times. We note that the strategies of optimal type can be used to approximate as closely as we please the optimal strategy obtained using continuous control and we present two new derivations of the key equations. We illustrate our general remarks by reference to a typical train control problem. [ABSTRACT FROM AUTHOR]

The paper considers the three-machine open shop scheduling problem to minimize the makespan. It is assumed that each job consists of at most two operations, one of which is to be processed on the bottleneck machine, the same for all jobs. A new lower bound on the optimal makespan is derived, and a linear-time algorithm for finding an optimal non-preemptive schedule is presented. [ABSTRACT FROM AUTHOR]

A short proof is given of the necessary and sufficient conditions for the convergence of the Iterative Proportional Fitting procedure. The input consists of a nonnegative matrix and of positive target marginals for row sums and for column sums. The output is a sequence of scaled matrices to approximate the biproportional fit, that is, the scaling of the input matrix by means of row and column divisors in order to fit row and column sums to target marginals. Generally it is shown that certain structural properties of a biproportional scaling do not depend on the particular sequence used to approximate it. Specifically, the sequence that emerges from the Iterative Proportional Fitting procedure is analyzed by means of the L-error that measures how current row and column sums compare to their target marginals. As a new result a formula for the limiting L-error is obtained. The formula is in terms of partial sums of the target marginals, and easily yields the other well-known convergence characterizations. [ABSTRACT FROM AUTHOR]

Recently, several classical Genetic Algorithm principles have been challenged - including the Fundamental Theorem of Genetic Algorithms and the Principle of Minimal Alphabets. In addition, the recent No Free Lunch theorems raise further concerns. In this paper we review these issues and offer some new directions for GA researchers. [ABSTRACT FROM AUTHOR]

Algebraic modelling languages have simplified management of many types of large linear programs but have not specifically supported stochastic modelling. This paper considers modelling language support for multistage stochastic linear recourse problems with finite distributions. We describe basic language requirements for formulation of finite event trees in algebraic modelling languages and show representative problems in AMPL using three commonly used scenario types. [ABSTRACT FROM AUTHOR]

This paper describes how the scenario aggregation principle can be combined with approximate solutions of the individual scenario problems, resulting in a computationally efficient algorithm where two individual Lagrangian-based procedures are merged into one. Computational results are given for an example from fisheries management. Numerical experiments indicate that only crude scenario solutions are needed. [ABSTRACT FROM AUTHOR]

The introduction of uncertainty to mathematical programs greatly increases the size of the resulting optimization problems. Specialized methods that exploit program structures and advances in computer technology promise to overcome the computational complexity of certain classes of stochastic programs. In this paper we examine the progressive hedging algorithm for solving multi-scenario generalized networks. We present computational results demonstrating the effect of various internal tactics on the algorithm's performance. Comparisons with alternative solution methods are provided. [ABSTRACT FROM AUTHOR]

We consider the well-known problem of scheduling n independent tasks nonpreemptively on m identical processors with the aim of minimizing the makespan. Coffman, Garey and Johnson [1] described an algorithm, MULTIFTT, based on techniques from bin-packing, with better worst performance than the LPT algorithm and proved that it satisfies a bound of 1.22. It has been claimed by Friesen [2] that this bound can be improved upon to 1.2. However, we found his proof, in particular his lemma 4.9, difficult to understand. Yue, Kellerer and Yu [3] have presented the bound 1.2 in a simpler way. In this paper, we prove first that the bound cannot exceed 13/11 and then prove that it is exactly 13/11. [ABSTRACT FROM AUTHOR]

In this paper, the problem of sequencing jobs on a single machine to minimize the weighted number of tardy jobs is considered. Some new dominances between jobs are proposed and studied. A new branch and bound algorithm that can solve large problems, e.g. 85 jobs, is presented. [ABSTRACT FROM AUTHOR]

This paper is concerned with computational experimentation leading to the design of effective branch and bound algorithms for an important class of nonlinear integer programming problems, namely linearly constrained problems, which are used to model several real-world situations. The main contribution here is a study of the effect of node and branching variable selection and storage reduction strategies on overall computational effort for this class of problems, as well as the generation of a set of adequate test problems. Several node and branching variable strategies are compared in the context of a pure breadth-first enumeration, as well as in a special breadth and depth enumeration combination approach presented herein. Also, the effect of using updated pseudocosts is briefly addressed. Computational experience is presented on a set of eighteen suitably-sized nonlinear test problems, as well as on some random linear integer programs. Some of the new rules proposed are demonstrated to be significantly superior to previously suggested strategies; interestingly, even for linear integer programming problems. [ABSTRACT FROM AUTHOR]

This paper describes the formulation of a nonlinear mixed integer programming model for a large-scale product development and distribution problem and the design and computational implementation of a special purpose algorithm to solve the model. The results described demonstrate that integrating the art of modeling with the sciences of solution methodology and computer implementation provides a powerful approach for attacking difficult problems. The efforts described here were successful because they capitalized on the wealth of existing modeling technology and algorithm technology, the availability of efficient and reliable optimization, matrix generation and graphics software, and the speed of large-scale computer hardware. The model permitted the combined use of decomposition, general linear programming and network optimization within a branch and bound algorithm to overcome mathematical complexity. The computer system reliably found solutions with considerably better objective function values 30 to 50 times faster than had been achieved using general purpose optimization software alone. Throughout twenty months of daily use, the system was credited with providing insights and suggesting strategies that led to very large dollar savings. [ABSTRACT FROM AUTHOR]

We present two solution algorithms for a large-scale integrated assessment model of climate change mitigation: the well known Negishi algorithm and a newly developed Nash algorithm. The algorithms are used to calculate the Pareto-optimum and competitive equilibrium, respectively, for the global model that includes trade in a number of goods as an interaction between regions. We demonstrate that in the absence of externalities both algorithms deliver the same solution. The Nash algorithm is computationally much more effective, and scales more favorably with the number of regions. In the presence of externalities between regions the two solutions differ, which we demonstrate by the inclusion of global spillovers from learning-by-doing in the energy sector. The non-cooperative treatment of the spillover externality in the Nash algorithm leads to a delay in the expansion of renewable energy installations compared to the cooperative solution derived using the Negishi algorithm. [ABSTRACT FROM AUTHOR]

We consider the robust 1-center problem on trees with uncertainty in vertex weights and edge lengths. The weights of the vertices and the lengths of the edges can take any value in prespecified intervals with unknown distribution. We show that this problem can be solved in O(n³ log n) time thus improving on Averbakh and Berman's algorithm with time complexity O(n6. For the case when the vertices of the tree have weights equal to 1 we show that the robust 1-center problem can be solved in O(n log n) time, again improving on Averbakh and Berman's time complexity of O(n² log n). [ABSTRACT FROM AUTHOR]