A decision-theoretic approach to robust optimization in multivalued graphs

This paper is devoted to the search of robust solutions in finite graphs when costs depend on scenarios. We first point out similarities between robust optimization and multiobjective optimization. Then, we present axiomatic requirements for preference compatibility with the intuitive idea of robustness in a multiple scenarios decision context. This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of Lorenz optima, we show how the search can be embedded in algorithms designed to enumerate k best solutions. Then, we apply it in order to enumerate Lorenz optimal spanning trees and paths. We investigate possible refinements of Lorenz dominance and we propose an axiomatic justification of OWA operators in this context. Finally, the results of numerical experiments on randomly generated graphs are provided. They show the numerical efficiency of the suggested approach.     

Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints

Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of the associated feasible regions. In this paper we consider a mixed 0–1 linear programming formulation of a discrete first order constrained optimization model and present a relaxation based on second order constraints. We derive some valid inequalities and restrictions by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure. We describe three heuristic algorithms to construct feasible solutions, based on conditional second order constraints, variable fixing, and conditional value at risk. Finally, we present numerical results for several instances of a real world portfolio optimization problem. This research was supported by the NSF awards DMS-0603728 and DMI-0354678.     

Comparison of selection rules for ordinal optimization

The evaluation of performance of a design for complex discrete event systems through simulation is usually very time consuming. Optimizing the system performance becomes even more computationally infeasible. Ordinal optimization (OO) is a technique introduced to attack this difficulty in system design by looking at “order” in performances among designs instead of “value” and providing a probability guarantee for a good enough solution instead of the best for sure. The selection rule, known as the rule to decide which subset of designs to select as the OO solution, is a key step in applying the OO method. Pairwise elimination and round robin comparison are two selection rule examples. Many other selection rules are also frequently used in the ordinal optimization literature. To compare selection rules, we first identify some general facts about selection rules. Then we use regression functions to quantify the efficiency of a group of selection rules, including some frequently used rules. A procedure to predict good selection rules is proposed and verified by simulation and by examples. Selection rules that work well most of the time are recommended.     

Bi-criteria optimization problems for decision rules

We consider bi-criteria optimization problems for decision rules and rule systems relative to length and coverage. We study decision tables with many-valued decisions in which each row is associated with a set of decisions as well as single-valued decisions where each row has a single decision. Short rules are more understandable; rules covering more rows are more general. Both of these problems—minimization of length and maximization of coverage of rules are NP-hard. We create dynamic programming algorithms which can find the minimum length and the maximum coverage of rules, and can construct the set of Pareto optimal points for the corresponding bi-criteria optimization problem. This approach is applicable for medium-sized decision tables. However, the considered approach allows us to evaluate the quality of various heuristics for decision rule construction which are applicable for relatively big datasets. We can evaluate these heuristics from the point of view of (i) single-criterion—we can compare the length or coverage of rules constructed by heuristics; and (ii) bi-criteria—we can measure the distance of a point (length, coverage) corresponding to a heuristic from the set of Pareto optimal points. The presented results show that the best heuristics from the point of view of bi-criteria optimization are not always the best ones from the point of view of single-criterion optimization.     

A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem

The multiple-choice multidimensional knapsack problem (MMKP) is a well-known NP-hard combinatorial optimization problem with a number of important applications. In this paper, we present a “reduce and solve” heuristic approach which combines problem reduction techniques with an Integer Linear Programming (ILP) solver (CPLEX). The key ingredient of the proposed approach is a set of group fixing and variable fixing rules. These fixing rules rely mainly on information from the linear relaxation of the given problem and aim to generate reduced critical subproblem to be solved by the ILP solver. Additional strategies are used to explore the space of the reduced problems. Extensive experimental studies over two sets of 37 MMKP benchmark instances in the literature show that our approach competes favorably with the most recent state-of-the-art algorithms. In particular, for the set of 27 conventional benchmarks, the proposed approach finds an improved best lower bound for 11 instances and as a by-product improves all the previous best upper bounds. For the 10 additional instances with irregular structures, the method improves 7 best known results.     

A new dominance procedure for combinatorial optimization problems

It is known that the effectiveness of the branch and bound algorithms for combinatorial optimization problems can be improved through dominance criteria which allow fathomings of large solution subsets. We describe a new dominance procedure which overcomes some of the drawbacks of the commonly used dominance criteria. An application to the Multiple Knapsack Problem and some computational results are also reported.     

Dominance-based heuristics for one-machine total cost scheduling problems

We study the one-machine scheduling problem with release dates and we look at several objective functions including total (weighted) tardiness and total (weighted) completion time. We describe dominance rules for these criteria, as well as techniques for using these dominance rules to build heuristic solutions. We use them to improve certain well-known greedy heuristic algorithms from the literature. Finally, we introduce a Tabu Search method with a neighborhood based on our dominance rules. Experiments show the effectiveness of our techniques in obtaining very good solutions for all studied criteria.     

Combinatorial flexibility problems and their computational complexity

The concept of flexibility—originated in the context of heat exchanger networks—is associated with a substructure which guarantees the performance of the original structure, in a given range of possible states. We extend this concept to combinatorial optimization problems, and prove several computational complexity results in this new framework.Under some monotonicity conditions, we prove that a combinatorial optimization problem polynomially transforms to its associated flexibility problem, but that the converse need not be true.In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids. We also prove that, when relaxing in different ways the matroid structure, the flexibility problems become NP-complete. This fact is shown by proving the NP-completeness of the flexibility problems associated with the Shortest Path, Minimum Cut and Weighted Matching problems.     

An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

In this paper, we consider combinatorial optimization problems with additional cardinality constraints. In k-cardinality combinatorial optimization problems, a cardinality constraint requires feasible solutions to contain exactly k elements of a finite set E. Problems of this type have applications in many areas, e.g. in the mining and oil industry, telecommunications, circuit layout, and location planning. We formally define the problem, mention some examples and summarize general results. We provide an annotated bibliography of combinatorial optimization problems of which versions with cardinality constraint have been considered in the literature.     

A primer of substitution tilings of the Euclidean plane

This paper is intended to provide an introduction to the theory of substitution tilings. For our purposes, tiling substitution rules are divided into two broad classes: geometric and combinatorial. Geometric substitution tilings include self-similar tilings such as the well-known Penrose tilings; for this class there is a substantial body of research in the literature. Combinatorial substitutions are just beginning to be examined, and some of what we present here is new. We give numerous examples, mention selected major results, discuss connections between the two classes of substitutions, include current research perspectives and questions, and provide an extensive bibliography. Although the author attempts to represent the field as a whole, the paper is not an exhaustive survey, and she apologizes for any important omissions.     

A combinatorial abstraction of linear programming

In the context of oriented matroids we establish and elaborate upon an abstraction of linear programming duality foreseen by Rockafellar in his work on elementary vectors. We describe a pivoting operation for oriented matroids and a finite pivoting method, which elucidate the combinatorial nature of Dantzig's simplex method. The pivoting method specializes, when the oriented matroids arise from real vector spaces, to the simplex method with a new pivot selection rule. A very simple pivot selection rule for which finiteness has been established in the linear programming context, but not in the broader setting of oriented matroids, is also described.     

Combinatorial optimization with interaction costs: Complexity and solvable cases

We introduce and study the combinatorial optimization problem with interaction costs (COPIC). COPIC is the problem of finding two combinatorial structures, one from each of two given families, such that the sum of their independent linear costs and the interaction costs between elements of the two selected structures is minimized. COPIC generalizes the quadratic assignment problem and many other well studied combinatorial optimization problems, and hence covers many real world applications. We show how various topics from different areas in the literature can be formulated as special cases of COPIC. The main contributions of this paper are results on the computational complexity and approximability of COPIC for different families of combinatorial structures (e.g. spanning trees, paths, matroids), and special structures of the interaction costs. More specifically, we analyze the complexity if the interaction cost matrix is parameterized by its rank and if it is a diagonal matrix. Also, we determine the structure of the intersection cost matrix, such that COPIC is equivalent to independently solving linear optimization problems for the two given families of combinatorial structures.     

Ant colony optimization for continuous domains

In this paper we present an extension of ant colony optimization (ACO) to continuous domains. We show how ACO, which was initially developed to be a metaheuristic for combinatorial optimization, can be adapted to continuous optimization without any major conceptual change to its structure. We present the general idea, implementation, and results obtained. We compare the results with those reported in the literature for other continuous optimization methods: other ant-related approaches and other metaheuristics initially developed for combinatorial optimization and later adapted to handle the continuous case. We discuss how our extended ACO compares to those algorithms, and we present some analysis of its efficiency and robustness.     

A Dual-Objective Evolutionary Algorithm for Rules Extraction in Data Mining

This paper presents a dual-objective evolutionary algorithm (DOEA) for extracting multiple decision rule lists in data mining, which aims at satisfying the classification criteria of high accuracy and ease of user comprehension. Unlike existing approaches, the algorithm incorporates the concept of Pareto dominance to evolve a set of non-dominated decision rule lists each having different classification accuracy and number of rules over a specified range. The classification results of DOEA are analyzed and compared with existing rule-based and non-rule based classifiers based upon 8 test problems obtained from UCI Machine Learning Repository. It is shown that the DOEA produces comprehensible rules with competitive classification accuracy as compared to many methods in literature. Results obtained from box plots and t-tests further examine its invariance to random partition of datasets. An erratum to this article is available at .     

Accumulating Jacobians as chained sparse matrix products

 The chain rule – fundamental to any kind of analytical differentiation - can be applied in various ways to computational graphs representing vector functions. These variants result in different operations counts for the calculation of the corresponding Jacobian matrices. The minimization of the number of arithmetic operations required for the calculation of the complete Jacobian leads to a hard combinatorial optimization problem. We will describe an approach to the solution of this problem that builds on the idea of optimizing chained matrix products using dynamic programming techniques. Reductions by a factor of 3 and more are possible regarding the operations count for the Jacobian accumulation. After discussing the mathematical basics of Automatic Differentiation we will show how to compute Jacobians by chained sparse matrix products. These matrix chains can be reordered, must be pruned, and are finally subject to a dynamic programming algorithm to reduce the number of scalar multiplications performed. Received: January 17, 2002 / Accepted: May 29, 2002 Published online: February 14, 2003 Key words. chained matrix product – combinatorial optimization – dynamic programming – edge elimination in computational graphs     

离散优化问题最优值函数的连续性质

对优化问题的最优值研究是有意义的, 尽管有时并不知道怎样寻求最优值. 研究了几个重要的组合最优化问题的目标值随着输入值变化的连续化性质, 重点研究几个经典的、有代表性的离散优化问题：极小化最大完工时间的排序问题、背包问题、旅行商问题等, 以连续的数学分析思维模式审视离散问题. 最后, 研究了一些近似算法对应的目标函数的性质.     

Generalized evaluation in decision analysis

The paper presents a discussion on evaluation methods in decision analysis. The presentation begins with the discussion of the expected value rule for selection amongst a number of available courses of action. Then a number of other evaluation rules to either replace or supplement the expected value are presented. They are discussed from a choice rather than preference view. To improve the expected value rule (or any other similar rule), it is suggested that it should be supplemented with other, qualitative rules rather than engaging in further modifications in pursuit of the perfect rule. A characteristic of qualitative rules is that they do not rely on multiplying probabilities and values but treat them as separate numeric entities. Once a rule has been agreed upon, it can be applied to all the alternatives, provided there is a computational procedure for evaluating the alternatives under that rule. Delta dominance is introduced as a unifying concept for many of the dominance rules in current use. Dominance and threshold methods are discussed and the kinship between them is pointed out.     

On the Hardness of the Quadratic Assignment Problem with Metaheuristics

Meta-heuristics are a powerful way to approximately solve hard combinatorial optimization problems. However, for a problem, the quality of results can vary considerably from one instance to another. Understanding such a behaviour is important from a theoretical point of view, but also has practical applications such as for the generation of instances during the evaluation stage of a heuristic.In this paper we propose a new complexity measure for the Quadratic Assignment Problem in the context of metaheuristics based on local search, e.g. simulated annealing. We show how the ruggedness coefficient previously introduced by the authors, in conjunction with the well known concept of dominance, provides important features of the search space explored during a local search algorithm, and gives a rather precise idea of the complexity of an instance for these heuristics. We comment previous experimental studies concerning tabu search methods and genetic algorithms with local search in the light of our complexity measure. New computational results with simulated annealing and taboo search are presented.     

Pivot rules for linear programming: A survey on recent theoretical developments

The purpose of this paper is to discuss the various pivot rules of the simplex method and its variants that have been developed in the last two decades, starting from the appearance of the minimal index rule of Bland. We are mainly concerned with finiteness properties of simplex type pivot rules. Well known classical results concerning the simplex method are not considered in this survey, but the connection between the new pivot methods and the classical ones, if there is any, is discussed.In this paper we discuss three classes of recently developed pivot rules for linear programming. The first and largest class is the class of essentially combinatorial pivot rules including minimal index type rules and recursive rules. These rules only use labeling and signs of the variables. The second class contains those pivot rules which can actually be considered as variants or generalizations or specializations of Lemke's method, and so they are closely related to parametric programming. The last class has the common feature that the rules all have close connections to certain interior point methods. Finally, we mention some open problems for future research.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2115.     

Integrating partial optimization with scatter search for solving bi-criteria {0, 1}-knapsack problems

This paper deals with the problem of inaccuracy of the solutions generated by metaheuristic approaches for combinatorial optimization bi-criteria {0, 1}-knapsack problems. A hybrid approach which combines systematic and heuristic searches is proposed to reduce that inaccuracy in the context of a scatter search method. The components of this method are used to determine regions in the decision space to be systematically searched.