Detecting strong cliques

A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely on connections with matchings and relate to several graph properties studied in the literature, including well-covered graphs, localizable graphs, and general partition graphs.     

Stochastic dominance efficiency analysis of diversified portfolios: classification, comparison and refinements

For more than three decades, empirical analysis of stochastic dominance was restricted to settings with mutually exclusive choice alternatives. In recent years, a number of methods for testing efficiency of diversified portfolios have emerged, which can be classified into three main categories: (1)?majorization, (2)?revealed preference and (3)?distribution-based approaches. Unfortunately, some of these schools of thought are developing independently, with little interaction or cross-referencing among them. Moreover, the methods differ in terms of their objectives, the information content of the results and their computational complexity. As a result, the relative merits of alternative approaches are difficult to compare. This paper presents the first systematic review of all three approaches in a unified methodological framework. We examine the main developments in this emerging literature, critically evaluating the advantages and disadvantages of the alternative approaches. We also point out some misleading arguments and propose corrections and improvements to some of the methods considered.     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

Hybrid Rollout Approaches for the Job Shop Scheduling Problem

In this paper, we focus on heuristic approaches for solving the deterministic job shop scheduling problem. More specifically, a new priority dispatch rule and hybrid rollout algorithms are developed for approaching the problem under consideration. The proposed solution algorithms are tested on a set of instances taken from the literature and compared with other methods. The computational results validate the effectiveness of the developed solution approaches and show that the proposed rollout algorithms are competitive with respect to several state-of-art heuristics for solving the job shop scheduling problem. The author thanks Dr. Marco Mancini and Dr. Alessandro Tarasio for valuable suggestions about computational issues.     

Measurement of returns to scale using non-radial DEA models

There are some specific features of the non-radial data envelopment analysis (DEA) models which cause some problems for the returns to scale measurement. In the scientific literature on DEA, some methods were suggested to deal with the returns to scale measurement in the non-radial DEA models. These methods are based on using Strong Complementary Slackness Conditions from optimization theory. However, our investigation and computational experiments show that such methods increase computational complexity significantly and may generate as optimal, solutions contradicting optimization theory. In this paper, we propose and substantiate a direct method for the returns to scale measurement in the non-radial DEA models. Our computational experiments documented that the proposed method works reliably and efficiently on the real-life data sets.     

Iterative Thresholding for Sparse Approximations

Sparse signal expansions represent or approximate a signal using a small number of elements from a large collection of elementary waveforms. Finding the optimal sparse expansion is known to be NP hard in general and non-optimal strategies such as Matching Pursuit, Orthogonal Matching Pursuit, Basis Pursuit and Basis Pursuit De-noising are often called upon. These methods show good performance in practical situations, however, they do not operate on the ? ₀ penalised cost functions that are often at the heart of the problem. In this paper we study two iterative algorithms that are minimising the cost functions of interest. Furthermore, each iteration of these strategies has computational complexity similar to a Matching Pursuit iteration, making the methods applicable to many real world problems. However, the optimisation problem is non-convex and the strategies are only guaranteed to find local solutions, so good initialisation becomes paramount. We here study two approaches. The first approach uses the proposed algorithms to refine the solutions found with other methods, replacing the typically used conjugate gradient solver. The second strategy adapts the algorithms and we show on one example that this adaptation can be used to achieve results that lie between those obtained with Matching Pursuit and those found with Orthogonal Matching Pursuit, while retaining the computational complexity of the Matching Pursuit algorithm.     

Orthogonal similarity transformation of a symmetric matrix into a diagonal-plus-semiseparable one with free choice of the diagonal

In this paper we describe an orthogonal similarity transformation for transforming arbitrary symmetric matrices into a diagonal-plus-semiseparable matrix, where we can freely choose the diagonal. Very recently an algorithm was proposed for transforming arbitrary symmetric matrices into similar semiseparable ones. This reduction is strongly connected to the reduction to tridiagonal form. The class of semiseparable matrices can be considered as a subclass of the diagonalplus- semiseparable matrices. Therefore we can interpret the proposed algorithm here as an extension of the reduction to semiseparable form. A numerical experiment is performed comparing thereby the accuracy of this reduction algorithm with respect to the accuracy of the traditional reduction to tridiagonal form, and the reduction to semiseparable form. The experiment indicates that all three reduction algorithms are equally accurate. Moreover it is shown in the experiments that asymptotically all the three approaches have the same complexity, i.e. that they have the same factor preceding the n³ term in the computational complexity. Finally we illustrate that special choices of the diagonal create a specific convergence behavior. The research was partially supported by the Research Council K.U.Leuven, project OT/05/40 (Large rank structured matrix computations), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann-Hilbert problems, random matrices and Padé-Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). The scientific responsibility rests with the authors.     

Strong detectability and observers

Conditions are given for the existence of observers that estimate unmeasured outputs on the basis of partial information on the input and the state. The concepts of strong detectability and strong observability, introduced before in the literature for discrete-time systems only, are defined and studied for continuous-time systems. It is shown that there are two different concepts of strong detectability, which coincide for discrete-time systems. Algebraic conditions for either concept are given. It is shown that these concepts are intimately related to the existence of strong observers, i.e. observers that only use the output of the plant.     

Stability criteria with less LMI variables for linear system with additive time-delays

In this technical note, equivalent stability criterion with minimal number of variables for three recently reported stability criteria is proposed for a class of linear systems with additive time-varying delays. The existing delay-dependent stability criteria for additive time-delay systems have more number of matrix variables in the LMI; and hence, they require more computational cost. The proposed equivalent criteria, unlike the original ones, encompass only the matrix variables that are associated in the Lyapunov-Krasovskii functional, making the criteria mathematically less complex and computationally more attractive. The complexity involved in the existing stability criteria is attributed to the fact the cross-terms that emanate from the time-derivative of the Lyapunov-Krasovskii functional are dealt with free-weighting matrices. Hence, apart from the matrix variables that are associated in the corresponding Lyapunov-Krasovskii functional, the existing criteria also have additional matrix variables in them. In this paper, we have devised techniques to eliminate the free-weighting matrices in the existing stability criteria without sacrificing the conservatism. The resulting equivalent stability criteria, therefore, have least possible number of variables in the LMI; and hence, have minimum computational burden. The effectiveness of the proposed equivalent criteria is validated on a numerical example.     

Mixed Integer Linear Programming in Process Scheduling: Modeling,Algorithms, and Applications

This paper reviews the advances of mixed-integer linear programming (MILP) based approaches for the scheduling of chemical processing systems. We focus on the short-term scheduling of general network represented processes. First, the various mathematical models that have been proposed in the literature are classified mainly based on the time representation. Discrete-time and continuous-time models are presented along with their strengths and limitations. Several classes of approaches for improving the computational efficiency in the solution of MILP problems are discussed. Furthermore, a summary of computational experiences and applications is provided. The paper concludes with perspectives on future research directions for MILP based process scheduling technologies.     

2DCPackGen: A problem generator for two-dimensional rectangular cutting and packing problems

Cutting and packing problems have been extensively studied in the literature in recent decades, mainly due to their numerous real-world applications while at the same time exhibiting intrinsic computational complexity. However, a major limitation has been the lack of problem generators that can be widely and commonly used by all researchers in their computational experiments. In this paper, a problem generator for every type of two-dimensional rectangular cutting and packing problems is proposed. The problems are defined according to the recent typology for cutting and packing problems proposed by Wäscher, Haußner, and Schumann (2007) and the relevant problem parameters are identified. The proposed problem generator can significantly contribute to the quality of the computational experiments run with cutting and packing problems and therefore will help improve the quality of the papers published in this field.     

Modelling of linguistic variables in multicriteria energy policy support

The climate change and the increasing complexity of the energy sector along with the prerequisite for sustainability have broadened the energy policy shaping field by bringing out new challenges. Decision support tools and methods, such as Multicriteria Decision Aid (MCDA), are necessary for energy policy, in the pursuit of appropriate approaches necessary to support the restructuring of the energy sector, concerning patterns of energy extraction, generation, transformation and use, from unsustainable to sustainable forms of development. Papers devoted to the investigation of MCDA models using linguistic variables for energy policy support seem to be not available in the international literature. The scope of this paper is to explore different linguistic representation and computational models in MCDA that are or can be applied to energy policy support and to establish a clear linkage between them. This paper argues that MCDA methodologies with direct computation on linguistic variables can support energy policy frameworks, bridging the gap between energy policy makers thinking, reasoning, representation and computing. Finally, current trends, open questions and prospects in this topic are pointed out.     

Heterogeneous multiscale methods for stiff ordinary differential equations

The heterogeneous multiscale methods (HMM) is a general framework for the numerical approximation of multiscale problems. It is here developed for ordinary differential equations containing different time scales. Stability and convergence results for the proposed HMM methods are presented together with numerical tests. The analysis covers some existing methods and the new algorithms that are based on higher-order estimates of the effective force by kernels satisfying certain moment conditions and regularity properties. These new methods have superior computational complexity compared to traditional methods for stiff problems with oscillatory solutions.

     

A comparison of the monomial method and the S-system method for solving systems of algebraic equations

Two numerical methods for solving systems of equations have recently been proposed: a method based on monomial approximations (the “monomial method”) and a technique based on S-system methodology (the “S-system method”). The two methods have been shown to be fundamentally identical, that is, they are both equivalent to Newton's method operating on a transformed version of the system of equations. Yet, when applied specifically to algebraic systems of equations, they have significant computational differences that may impact the relative computational efficiency of the two methods. These computational differences are described. A combinatorial strategy for locating many, and sometimes all, solutions to a system of nonlinear equations has also been suggested previously. This paper further investigates the effectiveness of this strategy when applied to either of the two methods.     

A class of explicit two-step hybrid methods for second-order IVPs

A class of explicit two-step hybrid methods for the numerical solution of second-order IVPs is presented. These methods require a reduced number of stages per step in comparison with other hybrid methods proposed in the scientific literature. New explicit hybrid methods which reach up to order five and six with only three and four stages per step, respectively, and which have optimized the error constants, are constructed. The numerical experiments carried out show the efficiency of our explicit hybrid methods when they are compared with classical Runge–Kutta–Nyström methods and other explicit hybrid codes proposed in the scientific literature.     

Computation of general correlation coefficients for interval data

This paper provides a comprehensive analysis of computational problems concerning calculation of general correlation coefficients for interval data. Exact algorithms solving this task have unacceptable computational complexity for larger samples, therefore we concentrate on computational problems arising in approximate algorithms. General correlation coefficients for interval data are also given by intervals. We derive bounds on their lower and upper endpoints. Moreover, we propose a set of heuristic solutions and optimization methods for approximate computation. Extensive simulation experiments show that the heuristics yield very good solutions for strong dependencies. In other cases, global optimization using evolutionary algorithm performs best. A real data example of autocorrelation of cloud cover data confirms the applicability of the approach.     

Existence results for strong vector equilibrium problems and their applications

New existence results for the strong vector equilibrium problem are presented, relying on a well-known separation theorem in infinite-dimensional spaces. The main results are applied to strong cone saddle-points and strong vector variational inequalities providing new existence results, and furthermore they allow recovery of an earlier result from the literature.     

Multi-tier binary solution method for multi-product newsvendor problem with multiple constraints

This paper considers a multi-product newsvendor problem with multiple constraints. Multiple constraints in the problem make it more challenging to solve. Previous research has attempted to solve the problem by considering two-constraint case or/and using approximation techniques or active sets methods. The solution methods in literature for solving multi-constraint problem are limited or cumbersome. In this paper, by analyzing structural properties of the multi-constraint multi-product newsvendor problem, we develop a multi-tier binary solution method for yielding the optimal solution to the problem. The proposed method is applicable to the problem with any continuous demand distribution and more than two constraints, and its computational complexity is polynomial in the number of products. Numerical results are presented for showing the effectiveness of our method.     

Gradient methods with regularization for constrained optimization problems and their complexity estimates

We suggest simple implementable modifications of conditional gradient and gradient projection methods for smooth convex optimization problems in Hilbert spaces. Usually, the custom methods attain only weak convergence. We prove strong convergence of the new versions and establish their complexity estimates, which appear similar to the convergence rate of the weakly convergent versions. Preliminary results of computational tests confirm efficiency of the proposed modification.