Search

This paper combines two rival preference modeling techniques in a new approach to multi-attribute decision making. Currently existing multi-attribute procedures use either global or local preference modeling. In the global modeling technique, a single preference function is constructed in the large; its maximum is the optimal alternative. In the local procedure, sequential approximations of the preference function are constructed in the small. Each approximation generates a trial solution. Under suitable conditions, each trial solution is preferred to its predecessor, so the trial sequence eventually reaches the optimum. Each technique has advantages and disadvantages; this paper combines the desirable features of both techniques in a new improved method. This new method, called the proxy approach, uses the advantages of one technique to overcome the disadvantages of the other. This paper first develops the theoretical aspects of the proxy approach and then compares it to existing procedures. Finally, the proxy algorithm is applied to a curriculum planning problem and numerous insights are gained. [ABSTRACT FROM AUTHOR]

The motivation for this paper is a problem faced by banks which process large volumes of deposited checks. The checks must be separated by bank number before shipment to the Federal Reserve or other banks. The sorting is usually accomplished using a reader-sorter which reads the magnetic ink characters on the checks and separates them into different "pockets." This paper characterizes the optimal sorting strategy and describes an efficient procedure for finding the optimal solution for problems of the size generally found in practice. The algorithm is based on a two state dynamic programming recursion in which characterization theorems are used to drastically reduce the size of the state space and in which the storage requirements are minimal. The paper includes an analysis of computational experience and describes how the algorithm can be used in a real time environment with deadlines. [ABSTRACT FROM AUTHOR]

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch-and-cut solvers for mixed-integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a closed-form expression. In this paper, we use the lift-and-project framework introduced by Balas and Perregaard to provide the basis, and the reduce-and-split algorithm as described by Cornuéjols and Nannicini to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory mixed-integer cut and alternates between lift-and-project and reduce-and-split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable to split disjunctions on multiple variables. Second, we apply the reduce-and-split algorithm to nonoptimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods. [ABSTRACT FROM AUTHOR]

This paper develops a new algorithm for solving the general nonlinear programming problem that melds the flexible simplex search of NELDER AND MEAD with various additional rules to take care of equality and/or inequality constraints. The set of violated inequalities and equalities is lumped into one inequality constraint loosely satisfied during the early progress of the optimization and more closely satisfied during its final stages. To permit this type of search, the method sets up a special tolerance criterion, a function that does not depend on either the values of the objective function or the values of the constraints. The new algorithm has solved successfully a number of problems that have been proposed in the literature as test problems. Finally, to indicate the algorithm's capabilities, the paper describes an example composed of a linear objective function of twenty-four variables subject to fourteen nonlinear equalities and thirty inequalities. [ABSTRACT FROM AUTHOR]

In an earlier paper [20] combinatorial programming procedures were presented for solving a class of integer programming problems in which all elements are zero or one. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problem-solving process, a number of problems involving several hundred integer variables were solved in a matter of seconds. In the present paper a number of improvements in these earlier algorithms are presented, including a new search strategy, methods for reducing the original problem, and mechanisms for feasibility filtering in multi-word problems. With these improvements problem-solving efficiency has been increased in many instances by an order of magnitude. In addition, the present paper contains computational experience obtained in solving problems for the k-best solutions. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of the capacitated dynamic lot size problem, where, over time, the setup costs are nonincreasing, the unit holding costs have arbitrary pattern, the unit production costs are nonincreasing and the capacities are nondecreasing. We investigate the properties of the optimal solution for the problem and develop the concept of candidate subplan. It is proven that only the candidate subplans need to be examined in searching for an optimal solution. A dynamic programming algorithm, incorporating the concept of candidate subplan, is then devised which has run time complexity of O(T[SUP2]). [ABSTRACT FROM AUTHOR]

This paper is intended to present a simple and quick method for obtaining approximate solutions to large scale zero-one programming problems. The method does not use enumeration. Instead, it assigns measures of preferability to zero-one variables that change the values of the variables from zero to one. The method yields very good approximate solutions to zero-one programming problems in dramatically short computation time. Even for problems involving more than a thousand zero-one variables the computation time is of little concern. The method is applicable not only to those problems associated with obtaining the optimal package of variables with the value one but also to a great variety of binary choice ("Yes-No") problems. [ABSTRACT FROM AUTHOR]

The author responds to the paper "The Loading Problem," by Eilon and Christofides. He focuses on suggesting a solution to the problem. The recommended solution involves a heuristic algorithm that allegedly requires fewer computations than the one proposed by Eilon and Christofides. It is suggested that the simpler algorithm offered by the author reaches mathematical optimization as often as the aforementioned algorithm. It is further proposed that the algorithm presented by Eilon and Christofides cannot be used to solve multi-dimensional programming problems. The author goes on to discuss a numerical analysis that can be used for the allocation of industrial resources. Related mathematical models are discussed in detail. A table comparing the results of the two algorithms is also presented.

In this paper the Fiacco-McCormick SUMT technique is embedded in a class of inside-out algorithms. Convergence is demonstrated for the nonlinear programming problem under fairly general conditions and the algorithms are interpreted in a geometric structure. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to illustrate some applications of the functional equation technique of the theory of dynamic programming to a general class of problems arising in the study of networks, particularly those arising in transportation theory. [ABSTRACT FROM AUTHOR]

In the stochastic orienteering problem, we are given a finite metric space, where each node contains a job with some deterministic reward and a random processing time. The processing time distributions are known and independent across nodes. However the actual processing time of a job is not known until it is completely processed. The objective is to compute a nonanticipatory policy to visit nodes (and run the corresponding jobs) so as to maximize the total expected reward, subject to the total distance traveled plus the total processing time being at most a given budget of B. This problem combines aspects of the stochastic knapsack problem with uncertain item sizes as well as the deterministic orienteering problem. In this paper, we consider both nonadaptive and adaptive policies for Stochastic Orienteering. We present a constant-factor approximation algorithm for the nonadaptive version and an O(log logB)-approximation algorithm for the adaptive version. We extend both these results to directed metrics and a more general sequence orienteering problem. Finally, we address the stochastic orienteering problem when the node rewards are also random and possibly correlated with the processing time and obtain an O(log n logB)-approximation algorithm; here n is the number of nodes in the metric. All our results for adaptive policies also bound the corresponding "adaptivity gaps". [ABSTRACT FROM AUTHOR]

This paper describes a generic branch-and-cut algorithm applicable to the solution of multiobjective optimization problems for which a lower bound can be defined as a polynomially solvable multiobjective problem. The algorithm closely follows standard branch and cut except for the definition of the lower and upper bounds and some optional speed-up mechanisms. It is applied to a routing problem called the multilabel traveling salesman problem, a variant of the traveling salesman problem in which labels are attributed to the edges. The goal is to find a Hamiltonian cycle that minimizes the tour length and the number of labels in the tour. Implementations of the generic multiobjective branch-and-cut algorithm and speed-up mechanisms are described. Computational experiments are conducted, and the method is compared to the classical ∈-constraint method. [ABSTRACT FROM AUTHOR]

In this paper, a market-based decomposition method for decomposable linear systems is developed. The solution process iterates between a master problem that solves the market-matching problem, and subproblems that solve the agents' bundle-determination problems. Starting from any initial price and feasible allocation, system optimality can be achieved under a dynamic market-trading algorithm in a finite number of trades. The final market-clearing prices are discovered by this market trading and an efficient allocation is achieved by direct, wealth-improving resource exchanges among self-interested agents. Certain types of strategic behavior by the agents and a dealer in the marketplace are studied as well. Our proposed market mechanism addresses price dynamics, incentive issues, and economic transactions of real-world, distributed decision-making situations more realistically than traditional decomposition approaches. In addition, it can be operated in both synchronous and asynchronous environments. We provide a market-based paradigm for decentralized problem solving and information processing that can be easily implemented to support real-time optimization of distributed systems. [ABSTRACT FROM AUTHOR]

In the last two decades, a number of algorithms for the linear single-commodity min-cost flow (MCF) problem have been proposed, and several efficient codes are available that implement different variants of the algorithms. The practical significance of the algorithms has been tested by comparing the time required by their implementations for solving "from-scratch" instances of MCF, of different classes, as the size of the problem (number of nodes and arcs) increases. However, in many applications several closely related instances of MCF have to be sequentially solved, so that reoptimization techniques can be used to speed up computations, and the most attractive algorithm is the one that minimizes the total time required to solve all the instances in the sequence. In this paper we compare the performances of four different efficient implementations of algorithms for MCF under cost reoptimization in the context of decomposition algorithms for the multicommodity min-cost flow (MMCF) problem, showing that for some classes of instances the relative performances of the codes doing "from-scratch" optimization do not accurately predict the relative performances when reoptimization is used. Because the best solver depends both on the class and on the size of the instance, this work also shows the usefulness of a standard interface for MCF problem solvers that we have proposed and implemented. [ABSTRACT FROM AUTHOR]

Cell suppression is a widely used technique for protecting sensitive information in statistical data presented in tabular form. Previous works on the subject mainly concentrate on 2-and 3-dimensional tables whose entries are subject to marginal totals. In this paper we address the problem of protecting sensitive data in a statistical table whose entries are linked by a generic system of linear constraints. This very general setting covers, among others, k -dimensional tables with marginals as well as the so-called hierarchical and linked tables that are very often used nowadays for disseminating statistical data. In particular, we address the optimization problem known in the literature as the (secondary) Cell Suppression Problem, in which the information loss due to suppression has to be minimized. We introduce a new integer linear programming model and outline an enumerative algorithm for its exact solution. The algorithm can also be used as a heuristic procedure to find near-optimal solutions. Extensive computational results on a test-bed of 1,160 real-world and randomly generated instances are resented, showing the effectiveness of the approach In particular, we were able to solve to proven optimality 4-dimensional tables with marginals as well as linked tables of reasonable size (to our knowledge, tables of this kind were never solved optimally by previous authors). [ABSTRACT FROM AUTHOR]

Routing problems appear frequently when dealing with the operation of communication or transportation networks. Among them, the message routing problem plays a determinant role in the optimization of network performance. Much of the motivation for this work comes from this problem which is shown to belong to the class of nonlinear convex multicommodity flow problems. This paper emphasizes the message routing problem in data networks, but it includes a broader literature overview of convex multicommodity flow problems. We present and discuss the main solution techniques proposed for solving this class of large-scale convex optimization problems. We conduct some numerical experiments on the message routing problem with four different techniques. [ABSTRACT FROM AUTHOR]

The bandwidth packing (BWP) problem is a combinatorially difficult problem arising in the area of telecommunications. The problem consists of assigning calls to paths in a capacitated graph, such that capacities are not violated and the total profit is maximized. In this paper we discuss the development of a tabu search (TS) method for the BWP problem. The method makes use of an efficient implementation of the k-shortest path algorithm, that allows the identification of a controlled set of feasible paths for each call. A tabu search is then performed to find the best path assignment for each call. The TS method developed here incorporates a number of features that have proved useful for obtaining optimal and near optimal solutions to difficult combinatorial problems. We establish the effectiveness of our approach by comparing its performance in speed and solution quality to other specialized heuristics and to a standard optimization package applied to a 0-1 integer programming formulation of the problem. [ABSTRACT FROM AUTHOR]

It is known that minimum cost flow problems can be solved by successive augmentations along shortest paths. In this paper the issues of implementing shortest path algorithms in this context are examined. Of particular interest is the dynamic topology that the flow networks exhibit. We develop a network generator capable of emulating such topology. Strategies for exploiting the special structures in such networks are discussed. A set of 9000 test problems is offered, from which a particular strategy/algorithm combination is shown to consistently produce superior results when compared to the other combinations. [ABSTRACT FROM AUTHOR]

The Linear Programming Problem is by far the most widely used optimization model. Its impact on economic and government modeling is immense. The Simplex Method for solving the Linear Programming (LP) Problem, due to George Dantzig, has been an extremely efficient computational tool for almost four decades. The method has been the subject of intense investigations for many years, but some major aspects of its behavior are not fully understood yet. The purpose of this paper is to survey the body of knowledge on the efficiency of the Simplex Method, from both practical and theoretical points of view. Adopting the number of iterations (pivot steps) as the yardstick for efficiency, we survey four aspects of the issue: 1. Reports on practical experience of the method's performance on real-life LP problems. 2. Results on controlled (Monte-Carlo) experiments solving LP problems which were randomly generated according to some predetermined distributions. 3. Complexity results, including theoretical analyses on both upper and lower bounds for the performance of the Simplex as well as non-Simplex algorithms for LP. 4. Results of recent theoretical studies using probabilistic analysis to derive bounds on the average behavior of the Simplex Method. We discuss the consequences and limitations of the various studies. Special emphasis is given to open questions. [ABSTRACT FROM AUTHOR]

Multiobjective mathematical programming has been one of the fastest growing areas of OR/MS during the last 15 years. This paper presents: 1. some reasons for the rapidly growing increase in interest in multiobjective mathematical programming. 2. a discussion of the advantages and disadvantages of the three general approaches (articulation of the decision maker's preference structure over the multiple objectives prior to, during, or after the optimization) towards multiobjective mathematical programming, 3. a nontechnical overview of many of the specific solution techniques for multiobjective mathematical programming, and 4. a discussion of important areas for further research. The overview concentrates on those techniques which require an articulation of the decision maker's preference structure either during or after the optimization, since these are the areas where most of the recent research has been conducted. It differs from previous overviews in that, in addition to the timing of the elicited preference information, the techniques are also classified according to the types of decision variables contained in the model (i.e., only continuous decision variables, or at least some discrete decision variables). In addition, the types of preference information (e.g., a ranking of outcomes) required of the various techniques are also discussed. [ABSTRACT FROM AUTHOR]

The conflict that naturally arises in a hierarchical system can often be modeled as a multistage optimization problem. This paper considers the sequential uncooperative problem in which two decision makers wish to maximize their own objective functions over a feasible region defined by interactive strategy sets. The resultant problem is known as the bilevel program. Such programs are inherently nonconvex and resistant to standard nonlinear programming solution techniques such as piecewise linearization and convex underestimating envelopes. Alternatively, a grid search algorithm is offered which exhibits the desirable property of monotonicity. The algorithm is based on two sets of necessary conditions previously developed and combined here to provide an operational check for stationarity and local optimality. Potential solutions are obtained from a parameterized master program whose feasible region approximates that of the original problem. As the one-dimensional parameter is varied over the unit interval and the master problem solved, a nondecreasing sequence of lower bounds to the first decision maker's objective function is produced. If the solution to the original problem is stable under small perturbations, the sequence is shown to converge to the global optimum. A discussion of the computational requirements follows the presentation of the algorithm. [ABSTRACT FROM AUTHOR]

The multiparametric linear programming (MLP) problem for the right-hand sides (RHS) is to maximize z = cT x subject to Ax = b (λ), x ≧ 0, where b(λ) can be expressed in the form b(λ) = b* + Fλ, where F is a matrix of constant coefficients, and λ is a vector-parameter. The multiparametric linear programming (MLP) problem for the prices or objective function coefficients (OFC) is to maximize z = cT (v)x subject to Ax = b, where x ≧ 0, where c(v) can be expressed in the form c(v) = c* + Hv, and where H is a matrix of constant coefficients, and v a vector-parameter. Let Bi be an optimal basis to the MLP-RHS problem and Ri be a region assigned to Bi such that for all λ Ri the basis, Bi is optimal. Let K denote a region such that K = ui Ri , provided that the Ri for various i do not overlap. The purpose of this paper is to present an effective method for finding all regions Ri that cover K and do not overlap. This method uses an algorithm that finds all nodes of a finite connected graph. An analogous method is presented for the MLP-OFC problem. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the solution of the knapsack problem. The method involves searching the nodes of a tree along a single branch at a time. The algorithm eliminates the computational drawbacks inherent in the usual branch and bound schemes. [ABSTRACT FROM AUTHOR]

A new concept is proposed for linking algebraic modeling languages with structure-exploiting solvers. SPI (Structure-Passing Interface) is a program that retrieves structure from an anonymous mathematical program built by an algebraic modeling language. SPI passes the special structure of the problem to an SES (Structure-Exploiting Solver). An integration of SPI and SES leads to SET (Structure-Exploiting Tool) and can be used with any algebraic modeling language. This approach relies on the idea that most exploitable block structures can be easily detected from the algebraic formulation of models. It should enable algebraic modeling languages to access the large body of algorithmic techniques which require problem structure. [ABSTRACT FROM AUTHOR]

We propose and test a new pricing procedure for solving large-scale structured linear programs. The procedure interactively solves a relaxed subproblem to identify potential entering basic columns. The subproblem is chosen to exploit special structure, rendering it easy to solve. The effect of the procedure is the reduction of the number of pivots needed to solve the problem. Our approach is motivated by the column-generation approach of Dantzig-Wolfe decomposition. We test our procedure on two sets of multicommodity flow problems. One group of test problems arises in routing telecommunications traffic and the second group is a set of logistics problem which have been widely used to test multicommodity flow algorithms. [ABSTRACT FROM AUTHOR]

Several types of large-sized 0-1 Knapsack Problems (KP) may be easily solved, but in such cases most of the computational effort is used for sorting and reduction. In order to avoid this problem it has been proposed to solve the so-called core of the problem: a Knapsack Problem defined on a small subset of the variables. The exact core cannot, however, be identified before KP is solved to optimality, thus, previous algorithms had to rely on approximate core sizes. In this paper we present an algorithm for KP where the enumerated core size is minimal, and the computational effort for sorting and reduction also is limited according to a hierarchy. The algorithm is based on a dynamic programming approach, where the core size is extended by need, and the sorting and reduction is performed in a similar "lazy" way. Computational experiments are presented for several commonly occurring types of data instances. Experience from these tests indicate that the presented approach outperforms any known algorithm for KP, having very stable solution times. [ABSTRACT FROM AUTHOR]

This paper gives the exact optimal solution to the problem of designing inspection schedules with fallible and time-consuming test procedures. The optimality criterion is designed to achieve a balance between the cost of inspections and the cost of undetected failure. The solution is derived in continuous time, with arbitrary failure distribution, and is based on infinite-horizon dynamic programming with time-dependent utilities, and with an additional optimization with respect to initial conditions. Results include uniqueness and monotonicity properties of the optimal solution, as well as computational algorithms. [ABSTRACT FROM AUTHOR]

It is a well observed fact that in minisum multifacility location problems the optimal locations of several facilities often tend to coincide Some sufficient conditions for this phenomenon, revolving only the weights and applicable to any metric, have been published previously The objective of this paper is to show how these conditions may be extended further and to obtain a more complete description of their implications, in particular, in the case of certain locational constraints [ABSTRACT FROM AUTHOR]

There is a need to develop user-oriented math programming techniques for resolution of decision problems in which several objectives must be considered. One approach, the Geoffrion-Dyer-Feinberg algorithm, allows interaction between the computer and the decision maker during the solution process. The interactive approach is adopted in this paper. However, our approach focuses on reducing the feasible region of the decision space rather than improving the stored image of the overall preference function. In so doing, the problem is reduced to a series of pairwise tradeoffs between the objectives. This obviates the need for any type of choice among vectors on the part of the decision maker and stays reasonably within his capability to supply necessary information for problem solution. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm for solving the assignment problem. The algorithm is based on a scheme of relaxing the given problem into a series of simple network flow (transportation) problems for each of which an optimal solution can be easily obtained The algorithm is thus seen to be able to take advantage of the nice properties in both the primal and the dual approaches for the assignment problem. The computational bound for the algorithm is shown to be O(n[sup 3]) and the average computation time is better than most of the specialized assignment algorithms. [ABSTRACT FROM AUTHOR]

In this paper we consider algorithms, duality and sensitivity analysis for optimization problems, called fractional, whose objective function is the ratio of two real-valued functions. We discuss a procedure suggested by Dinkelbach for solving the problem, its relation to certain approaches via variable transformations, and a variant of the procedure that has convenient convergence properties. The duality correspondences that are developed do not require either differentiability or the existence of an optimal solution. The sensitivity analysis applies to linear fractional problems, even when they 'solve' at on extreme ray, and includes a primal-dual algorithm for parametric right-hand-side analysis. [ABSTRACT FROM AUTHOR]

The problem of minimizing the total tardiness for a set of independent jobs on one machine is considered. Lawler has given a pseudo-polynomial-time algorithm to solve this problem. In spite of extensive research efforts for more than a decade, the question of whether it can be solved in polynomial time or it is NP-hard (in the ordinary sense) remained open. In this paper the problem is shown to be NP-hard (in the ordinary sense). [ABSTRACT FROM AUTHOR]

This paper describes a simple, easily-programmed method for solving discrete optimization problems with monotone objective functions and completely arbitrary (possibly nonconvex) constraints. The method is essentially one of partial enumeration, and is closely related to the 'lexicographic' algorithm of GILMORE AND GOMORY for the 'knapsack' problem and to the 'additive' algorithm of BALAS for the general integer linear programming problem. The results of a number of sample computations are reported. These indicate that the method is computationally feasible for problems in which the number of variables is fairly small. [ABSTRACT FROM AUTHOR]

The chromatic scheduling problem may be defined as any problem in which the solution is a partition of a set of objects. Since the partitions may not be distinct, redundant solutions can be generated when partial enumeration techniques are applied to chromatic scheduling problems. The necessary theory is developed to prevent redundant solutions in the application of partial enumeration techniques to chromatic scheduling problems with indistinguishable partitions and distinct objects. The chromatic number problem, which is the problem of finding the chromatic number of any graph, is a particular case of the chromatic scheduling problem. Two algorithms, basic and look-ahead, are developed for the chromatic number problem. Computational experience is given for each algorithm. [ABSTRACT FROM AUTHOR]

Problem-solving procedures based on the methods of combinatorial programming are presented for solving a class of integer programming problems in which all elements are zero or one. All of the procedures seek first a feasible solution and then successively better and better feasible solutions until ultimately one is discovered which is shown to be optimal. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problemsolving process, a number of problems involving several hundred integer variables have been solved in a matter of seconds. [ABSTRACT FROM AUTHOR]

We describe a framework and an algorithm for approximately solving a class of hybrid influence diagrams (IDs) containing discrete and continuous chance variables, discrete and continuous decision variables, and deterministic conditional distributions for chance variables. A conditional distribution for a chance variable is said to be deterministic if its variances, for each state of its parents, are all zeroes. The solution algorithm is an extension of Shenoy's fusion algorithm for discrete influence diagrams. To mitigate the integration and optimization problems associated with solving hybrid IDs, we propose using mixture of polynomials approximations of conditional probability density and utility functions and piecewise linear approximations of nonlinear deterministic conditional distributions for continuous chance variables. The class of hybrid IDs that can be solved by our framework are those that do not involve divisions. The framework and algorithm are illustrated by solving two small examples of hybrid IDs. [ABSTRACT FROM AUTHOR]

The well-known and established global optimality conditions based on the Lagrangian formulation of an optimization problem are consistent if and only if the duality gap is zero. We develop a set of global optimality conditions that are structurally similar but are consistent for any size of the duality gap. This system characterizes a primal-dual optimal solution by means of primal and dual feasibility, primal Lagrangian ε-optimality, and, in the presence of inequality constraints, a relaxed complementarity condition analogously called δ-complementarity. The total size ε + δ of those two perturbations equals the size of the duality gap at an optimal solution. Further, the characterization is equivalent to a near-saddle point condition which generalizes the classic saddle point characterization of a primal-dual optimal solution in convex programming. The system developed can be used to explain, to a large degree, when and why Lagrangian heuristics for discrete optimization are successful in reaching near-optimal solutions. Further, experiments on a set-covering problem illustrate how the new optimality conditions can be utilized as a foundation for the construction of new Lagrangian heuristics. Finally, we outline possible uses of the optimality conditions in column generation algorithms and in the construction of core problems. [ABSTRACT FROM AUTHOR]

Several combinatorial optimization problems can be formulated as large set-covering problems. In this work, we use the set-covering formulation to obtain a general heuristic algorithm for this type of problem, and describe our implementation of the algorithm for solving two variants of the well-known (one-dimensional) bin-packing problem: the two-constraint bin-packing problem and the basic version of the two-dimensional bin-packing problem, where the objects cannot be rotated and no additional requirements are imposed. In our approach, both the "column-generation" and the "column-optimization" phases are heuristically performed. In particular, in the first phase, we do not generate the entire set of columns, but only a small subset of it, by using greedy procedures and fast constructive heuristic algorithms from the literature. In the second phase, we solve the associated set-covering instance by means of a Lagrangian-based heuristic algorithm. Extensive computational results on test instances from the literature show that, for the two considered problems, this approach is competitive, with respect to both the quality of the solution and the computing time, with the best heuristic and metaheuristic algorithms proposed so far. [ABSTRACT FROM AUTHOR]

We consider the problem of maximizing an expected utility function of n assets, such as the mean-variance or power-utility function. Associated with a change in an asset's holdings from its current or target value is a transaction cost. This cost must be accounted for in practical problems. A straightforward way of doing so results in a 3n-dimensional optimization problem with 3n additional constraints. This higher dimensional problem is computationally expensive to solve. We present a method for solving the 3n-dimensional problem by solving a sequence of n-dimensional optimization problems, which accounts for the transaction costs implicitly rather than explicitly. The method is based on deriving the optimality conditions for the higher-dimensional problem solely in terms of lower-dimensional quantities. The new method is compared to the barrier method implemented in Cplex in a series of numerical experiments. With small but positive transaction costs, the barrier method and the new method solve problems in roughly the same amount of execution time. As the size of the transaction cost increases, the new method outperforms the barrier method by a larger and larger factor. [ABSTRACT FROM AUTHOR]

We introduce the notion of Limited Memory Influence Diagram (LIMID) to describe multistage decision problems in which the traditional assumption of no forgetting is relaxed. This can be relevant in situations with multiple decision makers or when decisions must be prescribed under memory constraints, such as in partially observed Markov decision processes (POMDPs). We give an algorithm for improving any given strategy by local computation of single policy updates and investigate conditions for the resulting strategy to be optimal. [ABSTRACT FROM AUTHOR]

We present an algorithm for a special class of nonlinear optimization problems with a nondifferentiable objective function and prove its convergence. The method does not use the notion of subgradient and no convexity assumption is made. We discuss the application of the method to an exact penalty function and to an environmental noise-management problem. [ABSTRACT FROM AUTHOR]

The set-covering problem is to minimize cx subject to [Multiple line equation(s) cannot be represented in ASCII text] over all binary n-vectors x. A is an mXn binary matrix and e[sub n] is an n-vector of l's. We develop a new implicit enumeration strategy to solve this problem. The branching strategy is similar to the row partitioning strategy used by other authors in the partitioning problem. Simple and sharp bounds are obtained by relaxing the constraints of the associated linear program by attaching nonnegative multipliers to them. Good multipliers are obtained by using the subgradient optimization technique. Computational experience shows that these bounds are at least one order of magnitude more efficient than the ones obtained by solving the associated linear program with the simplex method. Computational results with this new implicit enumeration algorithm are encouraging. Problems with as many as 50 constraints and 100 variables were solved in the order of 100 seconds of CPU time on an IBM 360-67. [ABSTRACT FROM AUTHOR]

Recently Kornbluth and Steuer have developed a simplex-based algorithm for finding all weakly-efficient vertices of an augmented feasible region of a multiple objective linear fractional programming problem. As part of this algorithm, they presented a method for detecting certain weakly-efficient vertices called break points. In this note we show that the procedure used by Kornbluth and Steuer in this method for computing the numbers needed to find these break points may sometimes fail. We also propose a fail-safe method for computing these numbers and give some computational results with this method. [ABSTRACT FROM AUTHOR]

This note develops properties of quasi-efficient solutions and explores interrelationships to the classical concept of efficiency. In particular, a point is a quasi-efficient solution to a multiple objective mathematical program if and only if it is an optimal solution to a scalar maximum problem for some set of nonnegative weights on the objectives. This result is then used to characterize the set of quasi-efficient solutions as the union of efficient solutions to a multiple objective problem over all nonempty subsets of the objectives. [ABSTRACT FROM AUTHOR]

For more than forty years, approximate solutions for the classical pipe network analysis problem have been obtained by direct solution of the nonlinear stationary point conditions. We propose a revolutionary new approach involving optimization techniques for solving this well-known engineering problem. It is shown that the pipe network analysis problem may be described mathematically in terms of a nonlinear convex cost network flow problem. Three mathematical programming algorithms for solving this problem have been coded and are computationally compared with a code using the traditional Newton-Raphson technique. The computational experience demonstrates that this new approach provides an attractive alternative for solving this important problem. [ABSTRACT FROM AUTHOR]

A new algorithm is developed for solving zero-one polynomial problems. The algorithm is a direct extension of the well-known Balasian algorithm for zero-one linear programs. The basic idea underlying the development is that every zero-one polynomial programming problem can be converted into an equivalent zero-one linear system with nonlinear secondary constraints representing the polynomial terms. Moreover, the optimal solution to the original polynomial problem must be a feasible solution to the converted linear problem. Thus, the optimal solution is determined by searching for the best solution among the feasible solutions to the linear problem such that the secondary constraints are satisfied. The important point is that the secondary constraints are considered implicitly so that the size of the problem is determined by its equivalent linear form. Computational experience indicates that the new algorithm compares favorably with the existing ones due to Lawler and Bell [12] and to Watters [20]. The application of the algorithm to a special class of nonlinear binary problems is also investigated. [ABSTRACT FROM AUTHOR]

In this report, twenty-nine integer linear programming problems, ranging from very simple to apparently rather difficult, are introduced. The results of running these problems on four different computer codes, involving five distinct algorithms, are presented as both time and iteration data. A brief description of the codes used is also included. [ABSTRACT FROM AUTHOR]