Search

In order to study the financial management of the Guangdong-Hong Kong-Macao Greater Bay Area, this paper builds a financial analysis model based on the LS-SVM algorithm and analyzes the implementation process of the LS-SVM algorithm and its modeling process. Moreover, this paper conducts research on CUDA-based GPU high-performance computing methods, designs and implements the LS-SVM algorithm on the CUDA-based GPU platform, and compares and analyzes the performance before and after optimization. In addition, this paper combines the improved algorithm to construct the financial analysis model and verifies the effect of the method proposed in this paper through actual data analysis. The research results prove the effectiveness of this method. The Hausman test achieves the probability of 0.1005 and 9.60182558 chi-square statistics.

The paper investigates hyperparameter optimization problem. Hyperparameters are the parameters of model parameter distribution. The adequate choice of hyperparameter values prevents model overfit and allows it to obtain higher predictive performance. Neural network models with large amount of hyperparameters are analyzed. The hyperparameter optimization for models is computationally expensive. The paper proposes modifications of various gradient-based methods to simultaneously optimize many hyperparameters. The paper compares the experiment results with the random search. The main impact of the paper is hyperparameter optimization algorithms analysis for the models with high amount of parameters. To select precise and stable models the authors suggest to use two model selection criteria: cross-validation and evidence lower bound. The experiments show that the models optimized using the evidence lower bound give higher error rate than the models obtained using cross-validation. These models also show greater stability when data is noisy. The evidence lower bound usage is preferable when the model tends to overfit or when the cross-validation is computationally expensive. The algorithms are evaluated on regression and classification datasets.

Due to the undesirable implications of maritime mishaps such as ship collisions and the consequent damages to maritime property; the safety and security of waterways, ports and other maritime assets are of the utmost importance to authorities and researches. Terrorist attacks, piracy, accidents and environmental damages are some of the concerns. This paper provides a detailed literature review of over 180 papers about different threats, their consequences pertinent to the maritime industry, and a discussion on various risk assessment models and computational algorithms. The methods are then categorized into three main groups: statistical, simulation and optimization models. Corresponding statistics of papers based on year of publication, region of case studies and methodology are also presented.

In this paper we use the burst factor of a packet stream, which is defined in a general setting, to quantify the long-term variability, or burstiness, of such a stream. We briefly review some existing results to show that this parameter plays an important role in the performance assessment and dimensioning of buffers in network nodes, even in a non-Markovian setting. We then focus on the calculation of this parameter at the egress of a discrete-time GI / D / 1 queueing system, considering different routing scenarios, and show how it can be expressed in terms of the parameters that characterise the arrival process in such a queue. In addition, we demonstrate how these results can be applied to evaluate the buffer performance in the subsequent nodes of a network. The analytic results that are derived throughout this paper are supported by simulations.

In many fault detection problems, we want to identify all defective items from a sample set of items using the minimum number of tests. Group testing is for the scenario where each test is performed on a subset of items, and tells whether the subset contains at least one defective item or not. In practice, the number of defective items in the sample set is usually unknown. In this paper, we investigate new algorithms for the group testing problem with unknown number of defective items. We consider the scenario where the performance of a group testing algorithm is measured by two criteria: the primary criterion is the number of tests performed, which measures the total cost spent; and the secondary criterion is the number of stages the algorithm works in, which is referred to as the sequentiality of the algorithm in this paper and measures the minimum amount of time required by using the algorithm to identify all the defective items. We present a new algorithm Recursive Binary Splitting (RBS) for the above group testing problem with unknown number of defective items, and prove an upper bound on the number of tests required by RBS. The computational results show that RBS exhibits very good practical performance, measured in terms of both the above two criteria.

In this paper, Markov models of repairable systems with repair time omission are considered whose finite state space is grouped into two sets, the set of working states, W, and the set of failed states, F. If the system enters failed states from a working state at any instance, and sojourns at the failed states F less than a given nonnegative critical value τ, then the repair interval can be omitted from downtime records. Otherwise, If the system enters failed states from a working state at any instance, and sojourns at the failed states F more than the given nonnegative critical value τ, then the repair interval cannot be omitted from downtime records. In terms of the assumption, a new model is developed. The focus of attention is the new model’s availability, interval reliability and interval unreliability. Several results are derived for these reliability indexes for the new model. Some special cases and numerical examples are given to illustrate the results obtained by using Maple software in the paper.

This paper advocates approaching timetable construction from the algorithms and complexity perspective, in which analysis of the specific problem under study is used to find efficient algorithms for some of its aspects, or to relate it to other problems. Examples are given of problem analyses leading to relaxations, phased approaches, very large-scale neighbourhood searches, bipartite matchings, ejection chains, and connections with standard NP-complete problems. Although a thorough treatment is not possible in a paper of this length, it is hoped that the examples will encourage timetabling researchers to explore further with a view to utilising some of the techniques in their own work.

The Quadratic Assignment Problem (QAP) is known as one of the most difficult problems within combinatorial optimization. It is used to model many practical problems including different layout problems. The main topic of this paper is to provide methods to check whether a particular instance of the QAP is a layout problem. An instance is a layout problem if the distances of the objects can be reconstructed on the plane and/or in the 3-dimensional space. A new mixed integer programming model is suggested for the case if the distances of the objects are supposed to be rectilinear distances. If the distances are Euclidean distances then the use of the well-known Multi-Dimensional Scaling (MDS) method of statistics is suggested for reconstruction purposes. The well-known difficulty of QAP makes it a popular and suitable experimental field for many algorithmic ideas including artificial intelligence methods. These types of results are published sometimes as layout problems. The methods of reconstruction can be used to decide whether the topic of a paper is layout or only general QAP. The issue what the OR community should expect from AI based algorithms, is also addressed.

Stochastic programming usually represents uncertainty discretely by means of a scenario tree. This representation leads to an exponential growth of the size of stochastic mathematical problems when better accuracy is needed. Trying to solve the problem as a whole, considering all scenarios together, yields to huge memory requirements that surpass the capabilities of current computers. Thus, decomposition algorithms are employed to divide the problem into several smaller subproblems and to coordinate their solution in order to obtain the global optimum. This paper analyzes several decomposition strategies based on the classical Benders decomposition algorithm, and applies them in the emerging computational grid environments. Most decomposition algorithms are not able to take full advantage of all the computing power available in a grid system because of unavoidable dependencies inherent to the algorithms. However, a special decomposition method presented in this paper aims at reducing dependency among subproblems, to the point where all the subproblems can be sent simultaneously to the grid. All algorithms have been tested in a grid system, measuring execution times required to solve standard optimization problems and a real-size hydrothermal coordination problem. Numerical results are shown to confirm that this new method outperforms the classical ones when used in grid computing environments.

In this paper we consider Weber-like location problems. The objective function is a sum of terms, each a function of the Euclidean distance from a demand point. We prove that a Weiszfeld-like iterative procedure for the solution of such problems converges to a local minimum (or a saddle point) when three conditions are met. Many location problems can be solved by the generalized Weiszfeld algorithm. There are many problem instances for which convergence is observed empirically. The proof in this paper shows that many of these algorithms indeed converge.

The Car Sequencing Problem (CSP) is a feasibility problem that has attracted the attention of the Constraint Programming community for a number of years now. In this paper, a new version (opt-CSP) that extends the original problem is defined, converting this into an optimization problem in which the goal is to satisfy the typical hard constraints. This paper presents a solution procedure for opt-CSP using Beam Search. Computational results are presented using public instances that verify the goodness of the procedure and demonstrate its excellent performance in obtaining feasible solutions for the majority of instances while satisfying the new constraints.

This paper addresses the problem of scheduling cascaded ‘blocked out’ continuous processing units separated by finite capacity storage tanks. The raw materials for the product lines arrive simultaneously on the input side of the first unit. But every unit can process only one product line at a time, thus giving rise to the possibility of spillage of raw material due to limited storage capacity. The need to process multiple product lines and the added constraint of multiple intermediate upliftment dates aggravate the problem. This problem is quite common in petrochemical industry. The paper provides a MINLP (Mixed Integer Non-Linear Programming) formulation of the problem. However, for any realistic scheduling horizon, the size of the problem is too large to be solved by standard packages. We have proposed a depth first branch and bound algorithm, guided by heuristics, to help planners in tackling the problem. The suggested algorithm could output near optimal solutions for scheduling horizons of 30 time periods when applied to real life situations involving 3 units and 3 product lines.

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.

This paper discusses choice set generation and route choice model estimation for large-scale urban networks. Evaluating the effectiveness of Advanced Traveler Information Systems (ATIS) requires accurate models of how drivers choose routes based on their aware- ness of the roadway network and their perceptions of travel time. Many of the route choice models presented in the literature pay little attention to empirical estimation and validation procedures. In this paper, a route choice data set collected in Boston is described and the ability of several different route generation algorithms to produce paths similar to those ob- served in the survey is analyzed. The paper also presents estimation results of some route choice models recently developed using the data set collected.

This paper develops a mathematical model for project time compression problems in CPM/PERT type networks. It is noted this formulation of the problem will be an adequate approximation for solving the time compression problem with any continuous and non-increasing time-cost curve. The kind of this model is Mixed Integer Linear Program (MILP) with zero-one variables, and the Benders' decomposition procedure for analyzing this model has been developed. Then this paper proposes a new approach based on the surrogating method for solving these problems. In addition, the required computer programs have been prepared by the author to execute the algorithm. An illustrative example solved by the new algorithm, and two methods are compared by several numerical examples. Computational experience with these data shows the superiority of the new approach.

Optimum Communication Spanning Tree Problem is a special case of the Network Design Problem. In this problem given a graph, a set of requirements r ij and a set of distances d ij for all pair of nodes (i,j), the cost of communication for a pair of nodes (i,j), with respect to a spanning tree T is defined as r ij times the length of the unique path in T, that connects nodes i and j. Total cost of communication for a spanning tree is the sum of costs for all pairs of nodes of G. The problem is to construct a spanning tree for which the total cost of communication is the smallest among all the spanning trees of G. The problem is known to be NP-hard. Hu (1974) solved two special cases of the problem in polynomial time. In this paper, using Hu’s result the first algorithm begins with a cut-tree by keeping all d ij equal to the smallest d ij . For arcs (i,j) which are part of this cut-tree the corresponding d ij value is increased to obtain a near optimal communication spanning tree in pseudo-polynomial time. In case the distances d ij satisfy a generalised triangle inequality the second algorithm in the paper constructs a near optimum tree in polynomial time by parametrising on the r ij .

The paper studies a multiserver retrial queueing system with $m$ servers. Arrival process is a point process with strictly stationary and ergodic increments. A customer arriving to the system occupies one of the free servers. If upon arrival all servers are busy, then the customer goes to the secondary queue, orbit, and after some random time retries more and more to occupy a server. A service time of each customer is exponentially distributed random variable with parameter $\mu_1$. A time between retrials is exponentially distributed with parameter $\mu_2$ for each customer. Using a martingale approach the paper provides an analysis of this system. The paper establishes the stability condition and studies a behavior of the limiting queue-length distributions as $\mu_2$ increases to infinity. As $\mu_2\to\infty$, the paper also proves the convergence of appropriate queue-length distributions to those of the associated `usual' multiserver queueing system without retrials. An algorithm for numerical solution of the equations, associated with the limiting queue-length distribution of retrial systems, is provided., Comment: To appear in "Annals of Operations Research" 141 (2006) 19-52. Replacement corrects a small number of misprints

This paper presents the Local Search with SubProblem Exact Resolution (LSSPER) method based on large neighbourhood search for solving the resource-constrained project scheduling problem (RCPSP). At each step of the method, a subpart of the current solution is fixed while the other part defines a subproblem solved externally by a heuristic or an exact solution approach (using either constraint programming techniques or mathematical programming techniques). Hence, the method can be seen as a hybrid scheme. The key point of the method deals with the choice of the subproblem to be optimized. In this paper, we investigate the application of the method to the RCPSP. Several strategies for generating the subproblem are proposed. In order to evaluate these strategies, and, also, to compare the whole method with current state-of-the-art heuristics, extensive numerical experiments have been performed. The proposed method appears to be very efficient.

Some nonsystematic search algorithms can deal with partial assignments of variables, and then can use constraint propagation techniques. Let us call them NSPA algorithms (Nonsystematic Search with Partial Assignments). For satisfiability or optimization problems, such NSPA algorithms scale a lot better than systematic algorithms. We show in this paper that naive NSPA algorithms have to pay a severe overhead due to the way they visit partial assignments. Amortizing the visits of partial assignments is an important feature which we introduce and analyze in this paper. We also propose a new NSPA algorithm that is amortized: it is called Amortized Random Backtracking, and performs a probabilistic exploration of the search space. It can be seen as an amortized version of iterative sampling and has given very good experimental results on a real life time tabling problem.

In a recent study, Sun et al. (AOR 292:113–131, 2020) studied due-window proportionate flow shop scheduling problems with position-dependent weights. For common due-window (denoted by CONW) and slack due-window (denoted by SLKW) assignment methods, they proved that these two problems can be solved in $$O(n^2\log n)$$ time respectively, where n is the number of jobs. In this paper, we consider the same problems, and our contribution is that the CONW problem can be optimally solved by a lower-order algorithm, which runs in $$O(n\log n)$$ time, implying an improvement of a factor of n.

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\((\sqrt n \)log (1/e)) steps. In the end of this paper, we discuss how to compute search direction (ΔX,ΔS) using the conjugate gradient method.

We consider production lines consisting of a series of machines separated by finite buffers. The processing time of each machine is deterministic and all the machines have the same processing time. All machines are subject to failures. As usually the case for production systems we assume that the failures are operation dependent. Moreover, we assume that the time to failure and the time to repair are exponentially distributed. To analyze such systems, an efficient decomposition procedure has been proposed by Gershwin and al. In general, this method provides fairly accurate results. There are however cases for which the accuracy of this decomposition method may not be so good. This is the case when the reliability parameters (mean times to failure and mean times to repair) of the different machines have different order of magnitudes. Such a situation may be encountered in real production lines. The purpose of this paper is to propose an improvement of Gershwin's original decomposition method that provides accurate results even in the above mentioned situation. The basic difference between the decomposition method presented in this paper with that of Gershwin is that the times to repair of the equivalent machines are modeled as generalized exponential distributions instead of exponential distributions. This allows us to use a two-moment approximation instead of a one-moment approximation of the repair time distributions of these equivalent machines. The new method is presented in the context of the continuous flow model. However, it is readily applicable to the synchronous model.

This paper explores the use of simulated annealing (SA) for solving arbitrary combinatorialoptimisation problems. It reviews an existing code called GPSIMAN for solving0‐1 problems, and evaluates it against a commercial branch‐and‐bound code, OSL. Theproblems tested include travelling salesman, graph colouring, bin packing, quadratic assignmentand generalised assignment. The paper then describes a technique for representingthese problems using arbitrary integer variables, and shows how a general simulated annealingalgorithm can also be applied. This new code, INTSA, outperforms GPSIMAN andOSL on almost all of the problems tested.

We suggest a heuristic solution procedure for Partially Observable Markov DecisionProcesses with finite action space and finite state space with infinite horizon. The algorithmis a fast, very simple general heuristic; it is applicable for multiple states (not necessarilyordered) multiple actions and various distribution functions. The quality of the algorithm ischecked in this paper against existing analytical and empirical results for two specific modelsof machine replacement. One model refers to the case of two‐action and two‐system stateswith uniform observations (Grosfeld‐Nir [4]), and the other model refers to a case of manyordered states with binomial observations (Sinuany‐Stern et al. [11]). The paper also presentsthe model realization for various probability distribution functions applied to maintenanceand quality control.

This special volume is focused upon a selection of the papers that were presented at the 9th International Conference on the Practice and Theory of Automated Timetabling (PATAT) in Son, Norway, between 28th and 31st August, 2012. The PATAT conferences are held biennially. This is the third occasion that we have employed the Annals of Operations Research as the forum for a revised and selected collection of papers. The first and second PATAT special volumes of this journal (Volumes 194 and 218) represented the 7th and 8th conferences, held in Montreal in 2008 and in Belfast in 2010, respectively. The PATAT series has been running since 1995. It has been held in Scotland, Canada (twice), Germany, Belgium, USA, Czech Republic, Northern Ireland, Norway, and England. The series acts as a bridge between disciplines and as a bridge between science and practice. Its focus is on all aspects of timetabling research and practice across personnel rostering, educational timetabling, sports scheduling and transportation timetabling. The conference in Son had over 90 delegates from all over the world. We had 4 plenary presentations, 49 standard talks, and 11 practitioner presentations. All the presenters were invited to submit revised papers to this special volume. Additionally, a public announcement was circulated

In this paper, a mathematical model and a solution algorithm are developed for solving a robot acquisition and cell formation problem (RACFP). Our model considers purchasing a proper mix of robots and assigning all given workstations to purchased robots such that each robot cell satisfies its workstations' resource demands while minimizing the total system (acquisition) cost. Specifically, each robot has two capacity constraints - available work envelope and effective machine time. RACFP is formulated as a multi-type two-dimensional bin packing problem, a pure 0-1 integer program which is known to be NP-hard. In this paper, a very efficient (polynomial time bound) heuristic algorithm is developed and implemented. The algorithm consists of two major stages. The first stage employs an LP-based bounding procedure to produce a tight solution bound, whereas the second stage repetitively invokes a random search heuristic using a greedy evaluation function. The algorithm is tested by solving 450 randomly generated problems based on realistic parameter values. Computational results show that the heuristic algorithm has outperformed algorithms using general optimization techniques such as Simulated Annealing and Column Generation. All test problems are solved within an order of magnitude of 10 seconds, with a gap of less than 1% from the optimum. More importantly, over 70% of all solutions are optimal (334 out of 450). The algorithm can be easily modified for other applications such as file placement for a multi-device storage system and job scheduling for a multi-processing system.

This paper proposes a new mathematical programming approach to represent the dimensions of the discriminant space for the multiple-group classification problem. Few papers have investigated generalizations of two-group mathematical programming approaches for the classification of multiple groups. While several papers have proposed mathematical programming models for separating groups of observations, the issue of considering the classification problem by finding discriminant linear functions to describe the groups in fewer dimensions has not been addressed. The new mathematical programming approach proposed in this paper first solves the multiple-group problem using a single discriminant function, which essentially represents the separation of the groups in one dimension. Then the multiple-group problem is successively solved using single discriminant functions with the requirement that successive linear discriminant functions have a sample covariance equal to zero. An algorithm is proposed to classify observations from multiple groups using the linear discriminant functions from the mathematical programming approach in a reduced number of dimensions.

We consider the objective function of a simple integer recourse problem with fixed technology matrix and discretely distributed right-hand sides. Exploiting the special structure of this problem, we devise an algorithm that determines the convex hull of this function efficiently. The results are improvements over those in a previous paper. In the first place, the convex hull of many objective functions in the class is covered, instead of only one-dimensional versions. In the second place, the algorithm is faster than the one in the previous paper. Moreover, some new results on the structure of the objective function are presented.

This paper addresses a supply chain situation, in which a company distributes commodities over a selected subset of customers while a manufacturer produces the commodities demanded by the customers. The distributor company has two objectives: the maximization of the profit gained by the distribution process and the minimization of $${\textit{CO}}_2$$ emissions. The latter is important due to the regulations imposed by the government. A compromise between both objectives exists, since profit maximization only will attempt to include as many customers as possible. But, longer routes will be needed, causing more $${\textit{CO}}_2$$ emissions. The manufacturer aims to minimize its manufacturing and shipping costs. Since a predefined hierarchy between both companies exists in the supply chain, a bi-level programming approach is employed. This problem is modelled as a bi-level programming problem with two objectives in the upper level and a single objective in the lower level. The upper level is associated with the distributor, while the lower level is associated with the manufacturer. Due to the inherent complexity to optimally solve this problem, a heuristic scheme is proposed. A nested bi-objective tabu search algorithm is designed to obtain non-dominated bi-level feasible solutions regarding the upper level. Considering simultaneously both objectives of the distributor allow us to focus on the minimization of $${\textit{CO}}_2$$ emissions caused by the supply chain, but bearing in mind the distributor’s profit. Numerical experimentation shows that the Pareto frontiers obtained by the proposed algorithm provide good alternatives for the decision-making process and also, some managerial insights are given.

In this paper we propose a two-phase approach to solve the shift and break design problem using integer linear programming. In the first phase we create the shifts, while heuristically taking the breaks into account. In the second phase we assign breaks to each occurrence of any shift, one by one, repeating this until no improvement is found. On a set of benchmark instances, composed by both randomly-generated and real-life ones, this approach obtains better results than the current best known method for shift and break design problem.

In this paper fluid models for heterogeneous multiplexed traffic are considered. First, some extensions to the general theory applicable to superposed, time-reversible Markovian Rate Processes are given. These refer to the connection between performance metrics, the consideration for singular systems and the continuity of the solution, with respect to the system parameters. The general framework is then carried over to the heterogeneous multiplexing of ON/OFF sources. By combining the general theory with the special structure of the ON/OFF sources several important facets of this structure are highlighted. As a result, more powerful methods that improve computation speed, stability and ease of implementation are produced. More specifically, the numerical part of the method is reduced to a solution of a nonlinear equation per system eigenvalue. The solution is obtainable through a variant of the (locally quadratically convergent) Newton method. For this method, easily computable starting values that guarantee convergence are given. In addition, explicit expressions for the eigenvectors are provided with the potentially unstable quantities factored-out. The paper also provides explicit and stably computable formulae for upper bounds to the coefficients of the spectral components, present in the expressions for the performance measures of interest. Moreover, the paper proves a partial ordering property for the system eigenvalues and presents an algorithm that performs full ordering on-line. This, in many cases, results in a great reduction to the amount of computation, without any significant loss of precision. Lastly, the particular case of heterogeneity where the differences are only identified in the rates within bursts is seen to have features resembling homogeneous systems. The possibility to substitute an “equivalent” homogeneous system of reduced order, for the original heterogeneous one is addressed.

In typical stochastic simulations, randomness is produced by generating a sequence of independent uniform variates (usually real-valued between 0 and 1, or integer-valued in some interval) and transforming them in an appropriate way. In this paper, we examine practical ways of generating (deterministic approximations to) such uniform variates on a computer. We compare them in terms of ease of implementation, efficiency, theoretical support, and statistical robustness. We look in particular at several classes of generators, such as linear congruential, multiple recursive, digital multistep, Tausworthe, lagged-Fibonacci, generalized feedback shift register, matrix, linear congruential over fields of formal series, and combined generators, and show how all of them can be analyzed in terms of their lattice structure. We also mention other classes of generators, like non-linear generators, discuss other kinds of theoretical and empirical statistical tests, and give a bibliographic survey of recent papers on the subject.

The general mean-semivariance portfolio optimization problem seeks to determine the efficient frontier by solving a parametric non-quadratic programming problem. In this paper it is shown how to transform this problem into a general mean-variance optimization problem, hence the Critical Line Algorithm is applicable. This paper also discusses how to implement the critical line algorithm to save storage and reduce execution time.

This paper is concerned with the set covering problem (SCP), and in particular with the development of a new algorithm capable of solving large-scale SCPs of the size found in real-life situations. The set covering problem has a wide variety of practical applications which, in general, yield large and sparse instances, normally with hundreds of rows and thousands of columns. In this paper, we present an algorithm capable of solving problems of this size and test problems up to 400 rows and 4000 columns are solved. The method developed in this paper consists of a tree-search procedure based on a combination of decomposition and state space relaxation which is a technique developed for obtaining lower bounds on the dynamic program associated with a combinatorial optimization problem. The large size SCPs are decomposed into many smaller SCPs which are then solved or bounded by state space relaxation (SSR). Before using the decomposition and SSR, reductions both in the number of columns and the number of rows of the problem are made by applying Lagrangian relaxation, linear programming and heuristic methods.

This special volumecomprises revisedversions of a selectionof the papers thatwere presented at the 9th International Conference on the Practice and Theory of Automated Timetabling (PATAT) in Belfast between 10th and 13th August 2010. The PATAT conferences are held biennially and this is the second time that the Annals of Operations Research has provided the venue for such a special collection of papers. The first PATAT special volume of this journal (Volume 194) contains papers associated with the 8th conference which was held in Montreal in 2008. PATAT acts as an international forum for all aspects of timetabling, including educational timetabling, personnel rostering, sports timetabling, and transport scheduling. The conference series is particularly concerned both with closing the gap between timetabling theory and practice and with supporting multidisciplinary interactions. The collection of papers in this special volume reflect these aims. The conference in Belfast brought together approximately 100 participants from around the world. There were five plenary presentations, 74 standard talks, and 16 practitioner presentations. All the delegates were invited to submit their revised papers to this special volume. The papers have been through a rigorous and thorough review process, and we are delighted to be able to present the community with such an interesting and diverse selection of articles that reflect the latest thinking in timetabling research. We would like to take this opportunity to thank all those who were responsible for the success of the conference. We would particularly like to thank Brian Fleming and all those within the School of Electronics, Electrical Engineering andComputer Science at theQueen’s University of Belfast who worked so hard before and during the conference.

This paper focuses on Benders decomposition techniques and Monte Carlo sampling (importance sampling) for solving two-stage stochastic linear programs with recourse, a method first introduced by Dantzig and Glynn [7]. The algorithm is discussed and further developed. The paper gives a complete presentation of the method as it is currently implemented. Numerical results from test problems of different areas are presented. Using small test problems, we compare the solutions obtained by the algorithm with universe solutions. We present the solutions of large-scale problems with numerous stochastic parameters, which in the deterministic formulation would have billions of constraints. The problems concern expansion planning of electric utilities with uncertainty in the availabilities of generators and transmission lines and portfolio management with uncertainty in the future returns.

The bilevel programming problem (BLPP) is a two-person nonzero sum game in which play is sequential and cooperation is not permitted. In this paper, we examine a class of BLPPs where the leader controls a set of continuous and discrete variables and tries to minimize a convex nonlinear objective function. The follower's objective function is a convex quadratic in a continuous decision space. All constraints are assumed to be linear. A branch and bound algorithm is developed that finds global optima. The main purpose of this paper is to identify efficient branching rules, and to determine the computational burden of the numeric procedures. Extensive test results are reported. We close by showing that it is not readily possible to extend the algorithm to the more general case involving integer follower variables.

The problem tackled in this paper is as follows: consider a set ofn interacting points in a two-dimensional space. The levels of interactions between the observations are given exogenously. It is required to cluster then observations intop groups, so that the sum of squared deviations from the cluster means is as small as possible. Further, assume that the cluster means are adjusted to reflect the interaction between the entities. (It is this latter consideration which makes the problem interesting.) A useful property of the problem is that the use of a squared distance term yields a linear system of equations for the coordinates of the cluster centroids. These equations are derived and solved repeatedly for a given set of cluster allocations. A sequential reallocation of the observations between the clusters is then performed. One possible application of this problem is to the planar hub location problem, where the interacting observations are a system of cities and the interaction effects represent the levels of flow or movement between the entities. The planar hub location problem has been limited so far to problems with fewer than 100 nodes. The use of the squared distance formulation, and a powerful supercomputer (Cray Y-MP) has enabled quick solution of large systems with 250 points and four groups. The paper includes both small illustrative examples and computational results using systems with up to 500 observations and 9 clusters.

This paper presents the novel method variable neighbourhood strategy adaptive search (VaNSAS) for solving the special case of assembly line balancing problems type 2 (SALBP-2S), which considers a limitation of a multi-skill worker. The objective is to minimize the cycle time while considering the limited number of types of machine in a particular workstation. VaNSAS is composed of two steps, as follows: (1) generating a set of tracks and (2) performing the track touring process (TTP). During TTP the tracks select and use a black box with neighborhood strategy in order to improve the solution obtained from step (1). Three modified neighborhood strategies are designed to be used as the black boxes: (1) modified differential evolution algorithm (MDE), (2) large neighborhood search (LNS) and (3) shortest processing time-swap (SPT-SWAP). The proposed method has been tested with two datasets which are (1) 128 standard test instances of SALBP-2 and (2) 21 random datasets of SALBP-2S. The computational result of the first dataset show that VaNSAS outperforms the best known method (iterative beam search (IBS)) and all other standard methods. VaNSAS can find 98.4% optimal solution out of all test instances while IBS can find 95.3% optimal solution. MDE, LNS and SPT-SWAP can find optimal solutions at 85.9%, 83.6% and 82.8% respectively. In the second group of test instances, we found that VaNSAS can find 100% of the minimum solution among all methods while MDE, LNS and SPT-SWAP can find 76.19%, 61.90% and 52.38% of the minimum solution.

In this research, an agro-supply chain in the context of both economic and environmental issues has been investigated. To this end, a bi-objective model is formulated as a mixed-integer linear programming that aims to minimize the total costs and CO2 emissions. It generates the integration between purchasing, transporting, and storing decisions, considering specific characteristics of agro-products such as seasonality, perishability, and uncertainty. This study provides a different set of temperature conditions for preserving products from spoilage. In addition, a robust optimization approach is used to tackle the uncertainty in this paper. Then, $$\varepsilon$$ -constraint method is used to convert the bi-objective model to a single one. To solve the problem, Lagrangian relaxation algorithm is applied as an efficient approach giving lower bounds for the original problem and used for estimating upper bounds. At the end, a real case study is presented to give valuable insight via assessing the impacts of uncertainty in system costs.

The CoMirror algorithm, by Beck et al. (Oper Res Lett 38(6):493–498, 2010), is designed to solve convex optimization problems with one functional constraint. At each iteration, it performs a mirror-descent update using either the subgradient of the objective function or the subgradient of the constraint function, depending on whether or not the constraint violation is below some tolerance. In this paper, we combine the CoMirror algorithm with inexact cut generation to create the SIP-CoM algorithm for solving semi-infinite programming (SIP) problems. First, we provide general error bounds for SIP-CoM. Then, we propose two specific random constraint sampling schemes to approximately solve the cut generation problem for generic SIP. When the objective and constraint functions are generally convex, randomized SIP-CoM achieves an $${\mathcal {O}}(1/\sqrt{N})$$ convergence rate in expectation (in terms of the optimality gap and SIP constraint violation). When the objective and constraint functions are all strongly convex, this rate can be improved to $${\mathcal {O}}(1/N)$$ .