Search

The aim of this paper is to propose efficient algorithms for computing the energetic lower bounds of the cumulative sheduling problem. So we have to schedule in a minimal makespan a set of non preemptive tasks on a resource with a given capacity. A task has a release date, a processing time and a tail and requires a given amount of the resource capacity during its processing. The energetic lower bound is the largest value of the makespan such that the energetic reasoning check cannot detect unfeasability. We report some algorithms to practically compute this lower bound with efficient complexity. These algorithms rely on iterative augmentations of C max until the cumulative constraint or the energetic constraint is satisfied. Our Computational results show their practical efficiencies. [ABSTRACT FROM AUTHOR]

The location planning of relief distribution centres (DCs) is crucial in humanitarian logistics as it directly influences the disaster response and service to the affected victims. In light of the critical role of facility location in humanitarian logistics planning, the study proposes a two-stage relief distribution location problem. The first stage of the model determines the minimum number of relief DCs, and the second stage find the optimal location of these DCs to minimize the total cost. To address a more realistic situation, restrictions are imposed on the coverage area and capacity of each DCs. In addition, for optimally solving this complex NP-hard problem, a novel two-phase algorithm with exploration and exploitation phase is developed in the paper. The first phase of the algorithm i.e., exploration phase identifies a near-optimal solution while the second phase i.e. exploitation phase enhances the solution quality through a close circular proximity investigation. Furthermore, the comparative analysis of the proposed algorithm with other well-known algorithms such as genetic algorithm, pattern search, fmincon, multistart and hybrid heuristics is also reported and computationally tested from small to large data sets. The results reveal that the proposed two-phase algorithm is more efficient and effective when compared to the conventional metaheuristic methods. [ABSTRACT FROM AUTHOR]

The multi-objective integer programming problem often occurs in multi-criteria decision-making situations, where the decision variables are integers. In the present paper, we have discussed an algorithm for finding all efficient solutions of a multi-objective integer quadratic programming problem. The proposed algorithm is based on the aspect that efficient solutions of a multi-objective integer quadratic programming problem can be obtained by enumerating ranked solutions of an integer quadratic programming problem. For determining ranked solutions of an integer quadratic programming problem, we have constructed a related integer linear programming problem and from ranked solutions of this integer linear programming problem, ranked solutions of the original integer quadratic programming problem are generated. Theoretically, we have shown that the developed method generates the set of all efficient solutions in a finite number of steps, and numerically we have elaborated the working of our algorithm and compared our results with existing algorithms. Further, we have analyzed that the developed method is efficient for solving a multi-objective integer quadratic programming problem with a large number of constraints, variables and objectives. [ABSTRACT FROM AUTHOR]

This study utilizes classification models to provide a robust algorithm for imbalanced data where the minority class is of the interest, that is, in the context of default payments. In developing an integrated predictive accuracy algorithm, this study proposes machine learning classifiers and applies DNN, SVM, KNN, and ANN. The proposed algorithm utilizes a 30,000 imbalanced dataset to improve the accuracy of the prediction of default payments by implementing oversampling and undersampling strategies, such as synthetic minority oversampling technique (SMOTE), SVM SMOTE, random undersampling, and ALL-KNN. The results indicate that the SVM under the ALL-KNN sampling technique is able to achieve an accuracy of 98.6%, with the lowest cross entropy loss measurement of 0.028. Through the accurate implementation of the neural networks and neurons used in the proposed algorithm, this paper presents better insights into the functioning of the neural networks when used in conjunction with the resampling techniques. Using the methodology and algorithm presented in this study, credit risk assessments can be more accurately predicted in practical applications where most of the clients are categorized as non-default payments. [ABSTRACT FROM AUTHOR]

Searching for minimal path vectors (MPVs) is an important topic in solving network related problems, especially for the evaluation of network reliability. One of the popular approaches, namely the three-stage method (TSM), is influenced deeply on the efficiency of searching for minimal path vectors in multi-state networks (MSN). TSM consists of three stages, i.e., searching for all minimal path sets, searching for all MPVs, and calculating union probability on MPVs. After reviewing previous works in the literaure, this paper proposes a more efficient method based on cyclic check on the candidates of MPVs, which can do an efficient searching for MPVs in MSNs and even reduce the three-step approach to two-step approach. Benchmarking with the well-known algorithms are made in this paper, and more complicated networks are also examined for verification of the proposed method. [ABSTRACT FROM AUTHOR]

We present an inexact proximal point algorithm using quasi distances to solve a minimization problem in the Euclidean space. This algorithm is motivated by the proximal methods introduced by Attouch et al., section 4, (Math Program Ser A, 137: 91–129, 2013) and Solodov and Svaiter (Set Valued Anal 7:323–345, 1999). In contrast, in this paper we consider quasi distances, arbitrary (non necessary smooth) objective functions, scalar errors in each objective regularized approximation and vectorial errors on the residual of the regularized critical point, that is, we have an error on the optimality condition of the proximal subproblem at the new point. We obtain, under a coercivity assumption of the objective function, that all accumulation points of the sequence generated by the algorithm are critical points (minimizer points in the convex case) of the minimization problem. As an application we consider a human location problem: How to travel around the world and prepare the trip of a lifetime. [ABSTRACT FROM AUTHOR]

Bimatrix games have had theoretical importance and important applications since the very beginning of game theory to date. Pareto optimal strategy vectors represent a reasonable and frequently applied solution concept (basically in the cooperative approach). Particularly, it often arises whether a non-cooperative solution can be improved in cooperative sense, i.e. it is Pareto optimal or not. However, in concrete cases it may be hard to determine the Pareto optimal strategy vectors or at least check the Pareto optimality of a given strategy vector. In the present paper, the Pareto optimality of the strategy pairs in general n × m ( n = 2 , 3 , ... ; m = 2 , 3 , ... ) bimatrix games is studied. First of all an elementary proof is provided for a theorem, which makes the proposed Pareto optimality checking algorithm simpler. Then a nonlinear transform is proposed, which makes the algorithm even more convenient in the important case of 2 × 2 bimatrix games (and for certain other cases). Two numerical examples present the practical applicability of the checking algorithm. The problem of 2 × 2 bimatrix games can be solved even by hand. For larger games, numerous computational tools are available in the practice to apply the checking algorithm in exact or at least approximate way. [ABSTRACT FROM AUTHOR]

Multiobjective optimization approaches have allowed the improvement of technical features in industrial processes, focusing on more accurate approaches for solving complex engineering problems and support decision-making. This paper proposes a hybrid approach to optimize the 3D printing technology parameters, integrating the design of experiments and multiobjective optimization methods, as an alternative to classical parametrization design used in machining processes. Alongside the approach, a multiobjective differential evolution with uniform spherical pruning (usp-MODE) algorithm is proposed to serve as an optimization tool. The parametrization design problem considered in this research has the following three objectives: to minimize both surface roughness and dimensional accuracy while maximizing the mechanical resistance of the prototype. A benchmark with non-dominated sorting genetic algorithm II (NSGA-II) and with the classical sp-MODE is used to evaluate the performance of the proposed algorithm. With the increasing complexity of engineering problems and advances in 3D printing technology, this study demonstrates the applicability of the proposed hybrid approach, finding optimal combinations for the machining process among conflicting objectives regardless of the number of decision variables and goals involved. To measure the performance and to compare the results of metaheuristics used in this study, three Pareto comparison metrics have been utilized to evaluate both the convergence and diversity of the obtained Pareto approximations for each algorithm: hyper-volume (H), g-Indicator (G), and inverted generational distance. To all of them, ups-MODE outperformed, with significant figures, the results reached by NSGA-II and sp-MODE algorithms. [ABSTRACT FROM AUTHOR]

In this paper we introduce a definition of approximate Pareto efficient solution as well as a necessary condition for such solutions in the multiobjective setting on Riemannian manifolds. We also propose an inexact proximal point method for nonsmooth multiobjective optimization in the Riemannian context by using the notion of approximate solution. The main convergence result ensures that each cluster point (if any) of any sequence generated by the method is a Pareto critical point. Furthermore, when the problem is convex on a Hadamard manifold, full convergence of the method for a weak Pareto efficient solution is obtained. As an application, we show how a Pareto critical point can be reached as a limit of traps in the context of the variational rationality approach of stay and change human dynamics. [ABSTRACT FROM AUTHOR]

In this paper we present an inexact scalarization proximal point algorithm to solve unconstrained multiobjective minimization problems where the objective functions are quasiconvex and locally Lipschitz. Under some natural assumptions on the problem, we prove that the sequence generated by the algorithm is well defined and converges. Then providing two error criteria we obtain two versions of the algorithm and it is proved that each sequence converges to a Pareto–Clarke critical point of the problem; furthermore, it is also proved that assuming an extra condition, the convergence rate of one of these versions is linear when the regularization parameters are bounded and superlinear when these parameters converge to zero. [ABSTRACT FROM AUTHOR]

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, ε -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. [ABSTRACT FROM AUTHOR]

This paper considers the problem of scheduling independent jobs with release dates and tails on m identical machines to minimize the makespan. The three main bounds are the preemptive bound, the energetic bound and the Jackson Pseudo Preemptive bound. It is known that they are very close in practice. The aim of this paper is to provide worst case instances where the slack between them is maximal and to prove tight bounds on the slack. We show that the slack is smaller than the maximal processing time. [ABSTRACT FROM AUTHOR]

The Weapon-Target Assignment (WTA) problem aims to assign a set of weapons to a number of assets (targets), such that the expected value of survived targets is minimized. The WTA problem is a nonlinear combinatorial optimization problem known to be NP-hard. This paper applies several existing techniques to linearize the WTA problem. One linearization technique (Camm et al. in Oper Res 50(6):946–955, 2002) approximates the nonlinear terms of the WTA problem via convex piecewise linear functions and provides heuristic solutions to the WTA problem. Such approximation problems are, though, relatively easy to solve from the computational point of view even for large-scale problem instances. Another approach proposed by O'Hanley et al. (Eur J Oper Res 230(1):63–75, 2013) linearizes the WTA problem exactly at the expense of incorporating a significant number of additional variables and constraints, which makes many large-scale problem instances intractable. Motivated by the results of computational experiments with these existing solution approaches, a specialized new exact solution approach is developed, which is called branch-and-adjust. The proposed solution approach involves the compact piecewise linear convex under-approximation of the WTA objective function and solves the WTA problem exactly. The algorithm builds on top of any existing branch-and-cut or branch-and-bound algorithm and can be implemented using the tools provided by state-of-the-art mixed integer linear programming solvers. Numerical experiments demonstrate that the proposed specialized algorithm is capable of handling very large scale problem instances with up to 1500 weapons and 1000 targets, obtaining solutions with optimality gaps of up to 2.0 % within 2 h of computational runtime. [ABSTRACT FROM AUTHOR]

Recent research applies soft computing techniques to fit software reliability growth models. However, runtime performance and the distribution of the distance from an optimal solution over multiple runs must be explicitly considered to justify the practical utility of these approaches, promote comparison, and support reproducible research. This paper presents a meta-optimization framework to design stable and efficient multi-phase algorithms for fitting software reliability growth models. The approach combines initial parameter estimation techniques from statistical algorithms, the global search properties of soft computing, and the rapid convergence of numerical methods. Designs that exhibit the best balance between runtime performance and accuracy are identified. The approach is illustrated through nonhomogeneous Poisson process and covariate software reliability growth models, including a cross-validation step on data sets not used to identify designs. The results indicate the nonhomogeneous Poisson process model considered is too simple to benefit from soft computing because it incurs additional runtime with no increase in accuracy attained. However, a multi-phase design for the covariate software reliability growth model consisting of the bat algorithm followed by a numerical method achieves better performance and converges consistently, compared to a numerical method only. The proposed approach supports higher-dimensional covariate software reliability growth model fitting suitable for implementation in a tool. [ABSTRACT FROM AUTHOR]

Progressive Hedging is a popular decomposition algorithm for solving multi-stage stochastic optimization problems. A computational bottleneck of this algorithm is that all scenario subproblems have to be solved at each iteration. In this paper, we introduce randomized versions of the Progressive Hedging algorithm able to produce new iterates as soon as a single scenario subproblem is solved. Building on the relation between Progressive Hedging and monotone operators, we leverage recent results on randomized fixed point methods to derive and analyze the proposed methods. Finally, we release the corresponding code as an easy-to-use Julia toolbox and report computational experiments showing the practical interest of randomized algorithms, notably in a parallel context. Throughout the paper, we pay a special attention to presentation, stressing main ideas, avoiding extra-technicalities, in order to make the randomized methods accessible to a broad audience in the Operations Research community. [ABSTRACT FROM AUTHOR]

Inspired by actual parcel delivery operations in London, this paper describes a two-echelon distribution system that combines the use of driving and walking as part of last-mile deliveries in urban areas for a single driver. The paper presents an optimisation model that explicitly treats and integrates the driving and walking elements, and describes a branch-and-cut algorithm that uses new valid inequalities specifically tailored for the problem at hand. Computational results based on real instances obtained from a courier operating in London are presented to show the performance of the algorithm. [ABSTRACT FROM AUTHOR]

The paper aims to present a multi-product, multi-stage, multi-period, and multi-objective, probabilistic mixed-integer linear programming model for a sustainable forward and reverse logistics network problem. It looks at original and return products to determine both flows in the supply chain—forward and reverse—simultaneously. Besides, to establish centres of forward and reverse logistics activities and make a decision for transportation strategy in a more close-to-real manner, the demand is considered uncertain. We attempt to represent all major dimensions in the objective functions: First objective function is minimizing the processing, transportation, fixed establishing cost and costs of CO2 emission as environmental impacts. Furthermore, the processing time of reverse logistics activities is developed as the second objective function. Finally, in the third objective function, it is tried to maximize social responsibility. Indeed, a complete sustainable approach is developed in this paper. In addition, this model provides novel environmental constraint and social matters in the objective functions as its innovation and contribution. Another contribution of this paper is using probabilistic programming to manage uncertain parameters. Moreover, a non-dominated sorting genetic algorithm (NSGA-II) is configured to achieve Pareto front solutions. The performance of the NSGA-II is compared with a multi-objective particle swarm optimization (MOPSO) by proposing 10 appropriate test problems according to five comparison metrics using analysis of variance (ANOVA) to validate the modeling approach. Overall, according to the results of ANOVA and the comparison metrics, the performance of NSGA-II algorithm is more satisfying compared with that of MOPSO algorithm. [ABSTRACT FROM AUTHOR]

This paper provides results in the area of the analytical derivation of the efficient set of a mean-variance portfolio selection problem that has more than three criteria. By "analytical" we mean derived by formula as opposed to being computed by algorithm. By "more than three criteria", we mean that beyond the mean and variance of regular portfolio selection, the problems addressed have two or more additional linear objectives. The additional objectives might include sustainability, dividend yield, liquidity, and R&D as extra objectives like these are being seen with greater frequency. While not all multiple criteria portfolio selection problems lend themselves to an analytical derivation, a certain class does and the problems in this class are covered by the mathematics of this paper. [ABSTRACT FROM AUTHOR]

Planning and scheduling of operating rooms (ORs) is important for hospitals to improve efficiency and achieve high quality of service. Due to significant uncertainty in surgery durations, scheduling of ORs can be very challenging. In this paper, surgical case scheduling problem with uncertain duration of surgeries in multi resource environment is investigated. We present a two-stage stochastic mixed-integer programming model, named SOS, with the objective of total ORs idle time and overtime. Also, in this paper a two-step approach is proposed for solving the model based on the L-shaped algorithm. Proposing the model in a multi resources environment with considering real-life limitations in academic hospitals and developing an approach for solving this stochastic model efficiently form the main contributions of this paper. The model is evaluated through several numerical experiments based on real data from Hasheminejad Kidney Center (HKC) in Iran. The solutions of SOS are compared with the deterministic solutions in several real instances. Numerical results show that SOS enjoys a better performance in 97% of the cases. Furthermore, the results of comparing with actual schedules applied in HKC reveal a notable reduction of OR idle time and over time which illustrate the efficiency of the proposed model in practice. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper, we extend techniques developed in the context of the Travelling Salesperson Problem for cycle problems. Particularly, we study the shrinking of support graphs and the exact algorithms for subcycle elimination separation problems. The efficient application of the considered techniques has proved to be essential in the Travelling Salesperson Problem when solving large size problems by Branch-and-Cut, and this has been the motivation behind this work. Regarding the shrinking of support graphs, we prove the validity of the Padberg–Rinaldi general shrinking rules and the Crowder–Padberg subcycle-safe shrinking rules. Concerning the subcycle separation problems, we extend two exact separation algorithms, the Dynamic Hong and the Extended Padberg–Grötschel algorithms, which are shown to be superior to the ones used so far in the literature of cycle problems. The proposed techniques are empirically tested in 24 subcycle elimination problem instances generated by solving the Orienteering Problem (involving up to 15,112 vertices) with Branch-and-Cut. The experiments suggest the relevance of the proposed techniques for cycle problems. The obtained average speedup for the subcycle separation problems in the Orienteering Problem when the proposed techniques are used together is around 50 times in medium-sized instances and around 250 times in large-sized instances. [ABSTRACT FROM AUTHOR]

This paper introduces the d-distance matching problem, in which we are given a bipartite graph G = (S , T ; E) with S = { s 1 , ⋯ , s n } , a weight function on the edges and an integer d ∈ Z + . The goal is to find a maximum-weight subset M ⊆ E of the edges satisfying the following two conditions: (i) the degree of every node of S is at most one in M, (ii) if s i t , s j t ∈ M , then | j - i | ≥ d . This question arises naturally, for example, in various scheduling problems. We show that the problem is NP-complete in general and admits a simple 3-approximation. We give an FPT algorithm parameterized by d and also show that the case when the size of T is constant can be solved in polynomial time. From an approximability point of view, we show that the integrality gap of the natural integer programming model is at most 2 - 1 2 d - 1 , and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial (2 - 1 d) -approximation algorithm is also presented. Several greedy approaches are considered, and a local search algorithm is described that achieves an approximation ratio of 3 / 2 + ϵ for any constant ϵ > 0 in the unweighted case. The novel approaches used in the analysis of the integrality gap and the approximation ratio of locally optimal solutions might be of independent combinatorial interest. [ABSTRACT FROM AUTHOR]

In this paper, we present a multi-objective simulation-based headway optimization for complex urban mass rapid transit systems. Real-world applications often confront conflicting goals of cost versus service level. We propose a two-phase algorithm that combines the single-objective covariance matrix adaptation evolution strategy with a problem-specific multi-directional local search. With a computational study, we compare our proposed method against both a multi-objective covariance matrix adaptation evolution strategy and a non-dominated sorting genetic algorithm. The integrated discrete event simulation model has several stochastic elements. Fluctuating demand (i.e., creation of passengers) is driven by hourly origin-destination-matrices based on mobile phone and infrared count data. We also consider the passenger distribution along waiting platforms and within vehicles. Our two-phase optimization scheme outperforms the comparative approaches, in terms of both spread and the accuracy of the resulting Pareto front approximation. [ABSTRACT FROM AUTHOR]

We consider a home health care routing problem with scarce resources which is a variation of the vehicle routing problem with resource constraints. In this problem, the services are provided by nurses and aids at patients' homes. There are different types of patients that are categorized based on the services they demand and should be serviced by appropriate staff teams or single personnel where the teams are transported by rental vehicles. In this problem, the objective is to minimize the total transportation cost, by considering the patients' requirements and the qualification of the staff, as well as the resource limitations. In this paper, we present a mathematical formulation of the problem that is modeled similar to a vehicle routing problem and propose a branch-and-price algorithm to solve it. Our proposed algorithm utilizes speed up techniques from the literature to enhance the effectiveness of the proposed solution method. A comprehensive computational study is conducted on Solomon based instances and the results illustrate the efficiency of the algorithm and the effective use of available resources. [ABSTRACT FROM AUTHOR]

This paper proposes an Automatic Clustering algorithm for Interval data using the Genetic algorithm (ACIG). In this algorithm, the overlapped distance between intervals is applied to determining the suitable number of clusters. Moreover, to optimize in clustering, we modify the Davies & Bouldin index, and to improve the crossover, mutation, and selection operators of the original genetic algorithm. The convergence of ACIG is theoretically proved and illustrated by the numerical examples. ACIG can be implemented effectively by the established Matlab procedure. Through the experiments on data sets with different characteristics, the proposed algorithm has shown the outstanding advantages in comparison to the existing ones. Recognizing the images by the proposed algorithm gives the potential in real applications of this research. [ABSTRACT FROM AUTHOR]

The decision making of a suitable heating, ventilating and air conditioning system's set-point temperature is an energy and environmental challenge in our society. In the present paper, a general framework to define such temperature based on a dynamic adaptive comfort algorithm is proposed. Due to the fact that the thermal comfort of the occupants of a building has different ranges of acceptability, this method is applied to learn such comfort temperature with respect to the running mean temperature and therefore to decide the suitable range of indoor temperature. It is demonstrated that this solution allows to dynamically build an adaptive comfort algorithm, an algorithm based on the human being's thermal adaptability, without applying the traditional theory. The proposed methodology based on the K-Nearest-Neighbour algorithm was tested and compared with data from an experimental thermal comfort field study carried out in a mixed mode building in the south-western area of Spain and with the Support Vector Machine method. The results show that K-Nearest-Neighbour algorithm represents the pattern of thermal comfort data better than the traditional solution and that it is a suitable method to learn the thermal comfort area of a building and to define the set-point temperature for a heating, ventilating and air-conditioning system. [ABSTRACT FROM AUTHOR]

The study of differences between timetabling research presented in conferences like PATAT or published in Annals of OR and commercial timetabling software used in Higher Education Institutions (HEIs) is essential for the discussion about innovation in both higher education and in commerce. In the field of planning and scheduling, a lot of developments are made and it is important to recognise that these developments are of influence on HEIs through their use of timetabling software. A main objective of the work presented here is to provide up-to-date information about timetabling in HEIs and see to what extent they adopt and implement timetabling developments. This is crucial because of budgets of institutions being strictly limited and remaining resources like rooms having to be shared more and more. Developments in HEIs have caused planning processes in higher education to deal with more limitations than ever, while at the same time the demand towards flexibility and availability is increasing. This paper gives the results of a systematic literature review in which differences and similarities in theory and practice of timetabling in higher education are described and discussed. We looked at state-of-the-art timetabling research for HEIs, at innovations in the field of timetabling and at changing requirements in Higher Education. The aim of this paper is to motivate the discussion about both the differences and similarities and bring timetabling application development closer to educational requirements. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper we study the classical single machine scheduling problem where the objective is to minimize the weighted number of tardy jobs. Our analysis focuses on the case where one or more of three natural parameters is either constant or is taken as a parameter in the sense of parameterized complexity. These three parameters are the number of different due dates, processing times, and weights in our set of input jobs. We show that the problem belongs to the class of fixed parameter tractable (FPT) problems when combining any two of these three parameters. We also show that the problem is polynomial-time solvable when either one of the latter two parameters are constant, complementing Karp's result who showed that the problem is NP-hard already for a single due date. [ABSTRACT FROM AUTHOR]

In this paper, we show a branch-and-cut approach to solve the minimum spanning tree problem with conflicting edge pairs. This is a NP-hard variant of the classical minimum spanning tree problem, in which there are mutually exclusive edges. We introduce a new set of valid inequalities for the problem, based on the properties of its feasible solutions, and we develop a branch-and-cut algorithm based on them. Computational tests are performed both on benchmark instances coming from the literature and on some newly proposed ones. Results show that our approach outperforms a previous branch-and-cut algorithm proposed for the same problem. [ABSTRACT FROM AUTHOR]

Operation management of automated storage and retrieval system (AS/RS) has a great impact on system performance and is a hot research topic. Most existing works for AS/RS operation management address determining storage and retrieval (S/R) machine sequence and minimizing its travel time. In the paper, we study a new bi-objective S/R machine sequencing problem with task release time and due date in a two-depot AS/RS. The objective is to minimize the total travel time of the S/R machine and the total tardiness simultaneously. For the problem, a new bi-objective mixed integer linear programming model is established. Based on problem property analysis, an exact ϵ -constraint method, a non-dominated sorting genetic algorithm II and a promising heuristic are devised for the problem. Especially, the computational results show the efficiency and effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Optimizing over the efficient set of a multi-objective optimization problem is among the difficult problems in global optimization because of its nonconvexity, even in the linear case. In this paper, we consider only properly efficient solutions which are characterized through weighted sum scalarization. We propose a numerical method to tackle this problem when the objective functions and the feasible set of the multi-objective optimization problem are convex. This algorithm penalizes progressively iterates that are not properly efficient and uses a sequence of convex nonlinear subproblems that can be solved efficiently. The proposed algorithm is shown to perform well on a set of standard problems from the literature, as it allows to obtain optimal solutions in all cases. [ABSTRACT FROM AUTHOR]

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 O (1 / 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 O (1 / N) . [ABSTRACT FROM AUTHOR]

Build Hull is currently one of the most efficient methods to address the large-scale data envelopment analysis problem. In this paper, the computational complexity of Build Hull is established, implying that the dimension of the data set has a strong influence on computational efficiency. Based on the complexity result, we find that the "worst density" of Build Hull monotonically increases with respect to dimension. In addition, a two-phase parallel Build Hull algorithm is proposed to enhance the computational efficiency of Build Hull. The parallel procedure is based on the minimum volume enclosing ellipsoid technique, which enables the exclusion of a large number of DMUs in the first phase. A sensitivity analysis-based technique is also proposed to substantially reduce computational time in the second phase. Numerical tests support our theoretical results. [ABSTRACT FROM AUTHOR]

This paper investigates a competitive two-agent parallel-batching scheduling problem with aging effect on parallel machines. The objective is to minimize the makespan of agent A with the constraint that the makespan of agent B is no more than a given threshold. Some key structural properties are first identified in two different cases, and based on these structural properties a novel decision tree of scheduling rules is constructed and a heuristic algorithm is designed. Then, an effective hybrid BF-VNS algorithm combining Bacterial Foraging (BF) with variable neighborhood search (VNS) is developed to tackle the studied problem. Computational experiments are conducted to evaluate the performance of the proposed hybrid algorithm and some other well-known algorithms. The experimental results indicate that the hybrid BF-VNS algorithm performs quite better than the compared algorithms. [ABSTRACT FROM AUTHOR]

Sustainability is the major issue of small and medium sized enterprises (SMEs) all across the globe. Although SMEs contribute to GDP of any country their negative contribution to environment is also significant. Prior studies on SMEs' sustainability mainly classified into three categories—the correlation between environmental and social practices with economic performance, sustainable supply chain performance measurement, and empirical research on sustainability practices. There is no study that objectively derives the sustainable structure of SMEs through optimal combination of sustainability practices (inputs) and performance (outputs). Therefore, the main objective of this paper is to generate optimal structure of sustainable SMEs by combining neural network and particle swarm algorithm while considering Multi-Objective framework. The study uses data from 54 SMEs of Normandy in France and 30 SMEs of Midlands in the UK. The data was gathered through questionnaire survey. As we do not have the explicit expression of our objective functions, we train a neural network on our databases in order to enable the generation of value of the different objectives for any profile. We design and run a multi-objective version of particle swarm optimization (MPSO) to generate efficient companies' structures. The weighted sum method is then used for different weights. The comparison of observed data and the results of the PSO analysis facilitates to derive improvement measures for each individual SME. [ABSTRACT FROM AUTHOR]

This paper proposes a fast ant colony system based solution method to solve realistic instances of the time-dependent orienteering problem with time windows within a few seconds of computation time. Orienteering problems occur in logistic situations where an optimal combination of locations needs to be selected and the routing between these selected locations needs to be optimized. For the time-dependent problem, the travel time between two locations depends on the departure time at the first location. The main contribution of this paper is the design of a fast and effective algorithm for this problem. Numerous experiments on realistic benchmark instances with varying size confirm the state-of-the-art performance and practical relevance of the algorithm. [ABSTRACT FROM AUTHOR]

This paper develops an EOQ inventory model that considers the demand rate as a function of stock and selling price. Shortages are permitted and two cases are studied: (i) complete backordering and (ii) partial backordering. The inventory model is for a deteriorating seasonal product. The product's deterioration rate is controlled by investing in the preservation technology. The main purpose of the inventory model is to determine the optimum selling price, ordering frequency and preservation technology investment that maximizes the total profit. Additionally, the paper proves that the total profit is a concave function of selling price, ordering frequency and preservation technology investment. Therefore, a simple algorithm is proposed to obtain the optimal values for the decision variables. Several numerical examples are solved and studied along with a sensitivity analysis. [ABSTRACT FROM AUTHOR]

Power generation planning in hydrothermal systems is a complex optimization task, specially due to the high uncertainty in the inflows to hydro plants. Since it is impossible to traverse the huge scenario tree of the multistage problem, stochastic dual dynamic programming (SDDP) is the leading technique to solve it, originally from an expected-cost minimization perspective. However, there is a growing need to apply risk-averse/robust formulations to protect the system from critical hydrological scenarios. This is particularly important for predominantly hydro systems, because environmental issues prevent the construction of large reservoirs, thus reducing their water regulating capability. This paper proposes a two-level SDDP/Benders decomposition approach to include a new risk averse surface (RAS) concept for reservoir operation in power generation planning. The upper level problem is a SDDP solving strategy with expected-cost minimization criterion, where recourse functions for each time step are built through forward/backward passes. The second level consists in multi-period deterministic optimization subproblems for each node of the scenario tree, which are solved to ensure a desired level of protection from a set of given critical scenario several months ahead. An inner iterative procedure for each SDDP stage/scenario is applied, where feasibility cuts are included in the upper level subproblems to derive the RAS surface, which are multidimensional rule curves for reservoir operation. Such curves ensure that the policy provided by the SDDP algorithm yields storage levels in the reservoirs that are high enough to protect the system against such critical scenarios. A "max-type" time-linking penalization scheme for violation of RAS constraints is also proposed, which avoids the multiple application of the penalty value for the same violation in consecutive time steps, which may result in large marginal costs. Results are presented for the large-scale Brazilian system. [ABSTRACT FROM AUTHOR]

Global financial investors have been confronted in recent years with an increasing frequency of market shocks and returns' outliers, until the unprecedented surge of financial risk observed in 2008. From a statistical viewpoint, those market dynamics have shown not only asymmetric returns and fat tails but also a time-varying tail dependence, stimulating the formulation of portfolio selection models based on such assumptions. The concept of tail dependence on upper or lower tails, roughly speaking, focuses on the risk that tail events may occur jointly in different markets. This notion can be given a rigorous probabilistic definition, and it turns out that a distinction between upper and lower tails is relevant in portfolio management. In this paper, relying on a discrete modeling framework, we present a scenario generation algorithm able to capture this time-varying asymmetric tail dependence, and evaluate resulting optimal investment policies based on 4-stages 1-month planning horizons. The scenario tree aims at approximating a stochastic process combining an ARMA-GARCH model and a dynamic Student-t-Clayton copula. From a methodological viewpoint, scenario trees are generated from this model by stage-wisely sampling and clustering and to improve tail fitting with original data, the scenarios' nodal probabilities are calibrated on the returns' lower tails for a set of equity indices. The resulting scenario trees are then applied to solve a multiperiod portfolio selection problem. We present a set of empirical results to validate the adopted statistical approach and the optimal portfolio strategies able to capture asymmetric tail returns. [ABSTRACT FROM AUTHOR]

In this paper, we consider due-window assignment scheduling in the proportionate flow shop setting with position-dependent weights where the weights depend on the position in which a job is scheduled. Under the common due-window (CONW) and slack due-window (SLKW) assignment methods, the location of the window and its properties are established. The objective is to determine the sequence of all jobs to minimize the total weighted cost function where the total weighted cost function must also consider the window start time and size. Based on these considerations, the corresponding algorithm and algorithm complexity are proposed. [ABSTRACT FROM AUTHOR]

The multiperiod vehicle routing problem with profit (mVRPP) is a selective vehicle routing problem where the planning horizon of each vehicle is divided into several periods. The aim of solving mVRPP is to design service itineraries so that the total amount of collected profit is maximized and the travel time limit of each period is respected. This problem arises in many real life applications, as the one encountered in cash-in-transit industry. In this paper, we present a metaheuristic approach based on the particle swarm optimization algorithm (PSO) to solve the mVRPP. Our approach incorporates an efficient optimal split procedure and dedicated local search operators proposed to guarantee high search intensification. Experiments conducted on an mVRPP benchmark show that our algorithm outperforms the state of the art metaheuristic approaches in terms of performance and robustness. Our PSO algorithm determines all the already known optimal solutions within a negligible computational time and finds 88 strict improvements among the 177 instances of the benchmark. [ABSTRACT FROM AUTHOR]

This paper considers a real case problem of supply chain network design inspired from a wheat distribution network in Iran. It generates a network with capacity acquisition and fleet management. The problem first is formulated as a mixed integer linear programming model. Then, a logic-based Benders decomposition algorithm is appropriately developed as the solution methodology. In the presented algorithm, the problem is decomposed into two models of master and subproblem. The master problem is improved by means of the preprocessing and valid inequalities. Moreover, three Benders cuts, one optimality and two feasibility cuts, are developed for the algorithm. The general and relative performance of the model and algorithm is experimentally evaluated. The wheat distribution system of Iran is considered here as the case study of this research. The model is developed based on Iran's wheat distribution system. All the results show that the algorithm significantly outperforms the mathematical model of the case study. For example, the algorithm solves 95% of the tested instances to optimality, yet the model solves 29%. [ABSTRACT FROM AUTHOR]

Disasters such as earthquake or tsunami can easily take the lives of thousands of people and millions worth of property in a fleeting moment. A successful emergency evacuation plan is critical in response to disasters. In this paper, we seek to investigate the multi-source, multi-destination evacuation problem. First, we construct a mixed integer linear programming model. Second, based on K shortest paths and user equilibrium, we propose a novel algorithm (hereafter KPUE), whose complexity is polynomial in the numbers of nodes and evacuees. Finally, we demonstrate the effectiveness of algorithm KPUE by a real evacuation network in Shanghai, China. The numerical examples show that the average computation time of the proposed algorithm is 95% less than that of IBM ILOG CPLEX solver and the optimality gap is no more than 5%. [ABSTRACT FROM AUTHOR]

The purpose of this paper is twofold. First, we examine convergence properties of an inexact proximal point method with a quasi distance as a regularization term in order to find a critical point (in the sense of Toland) of a DC function (difference of two convex functions). Global convergence of the sequence and some convergence rates are obtained with additional assumptions. Second, as an application and its inspiration, we study in a dynamic setting, the very important and difficult problem of the limit of the firm and the time it takes to reach it (maturation time), when increasing returns matter in the short run. Both the formalization of the critical size of the firm in term of a recent variational rationality approach of human dynamics and the speed of convergence results are new in Behavioral Sciences. [ABSTRACT FROM AUTHOR]

The alternate direction method of multipliers (ADMM) has received significant attention recently as a powerful algorithm to solve convex problems with a block structure. The vast majority of applications focus on deterministic problems. In this paper we show that ADMM can be applied to solve two-stage stochastic programming problems, and we propose an implementation in three blocks with or without proximal terms. We present numerical results for large scale instances, and extend our findings for risk averse formulations using utility functions. [ABSTRACT FROM AUTHOR]

This paper addresses the edge coloring by total labeling graph problem. This is a labeling of the vertices and edges of a graph such that the weights (colors) of the edges, defined by the sum of its label and the labels of its two endpoints, determine a proper edge coloring of the graph. We propose two integer programming formulations and derive valid inequalities which are added as cutting planes on a Branch-and-Cut framework. In order to improve the efficiency of the algorithm, we also develop initial and primal heuristics. The algorithm is tested on random instances and the computational results show that it is very effective in comparison with CPLEX. It is displayed that it reduces both the CPU time (for solved instances) and the final percentage gap (for unsolved instances), and that it is capable of solving instances that are out of the reach of CPLEX. [ABSTRACT FROM AUTHOR]

Complexity and uncertainty associated with commodity resource valuation and extraction requires stochastic control methods suitable for high dimensional states. Recent progress in duality and trajectory-wise techniques has introduced a variety of fresh ideas to this field with surprising results. This paper presents a concept which implements this promising development and illustrates it on a selection of traditional commodity extraction problems. We describe efficient algorithms for obtaining approximate solutions along with a diagnostic technique, which provides a quantitative measure for solution performance in terms of the distance between the approximate and the optimal control policy. All quantitative tools are efficiently implemented and are publicly available within a user friendly package in the statistical language R, which can help practitioners in a broad range of decision optimization problems. [ABSTRACT FROM AUTHOR]

Income tax systems with "pass-through" entities transfer a firm's income to shareholders, which are taxed individually. In 2014, a Chilean tax reform introduced this type of entity and changed to an accrual basis that distributes incomes (but not losses) to shareholders. A crucial step for the Chilean taxation authority is to compute the final income of each individual given the complex network of corporations and companies, usually including cycles between them. In this paper, we show the mathematical conceptualization and the solution to the problem, proving that there is only one way to distribute income to taxpayers. Using the theory of absorbing Markov chains, we define a mathematical model for computing the taxable income of each taxpayer, and we propose a decomposition algorithm for this problem. This approach allows us to compute the solution accurately and to efficiently use computational resources. Finally, we present some characteristics of Chilean taxpayers' network and the computational results of the algorithm using this network. [ABSTRACT FROM AUTHOR]

In this paper, we propose partition-based decomposition algorithms for solving two-stage stochastic integer program with continuous recourse. The partition-based decomposition method enhance the classical decomposition methods (such as Benders decomposition) by utilizing the inexact cuts (coarse cuts) induced by a scenario partition. Coarse cut generation can be much less expensive than the standard Benders cuts, when the partition size is relatively small compared to the total number of scenarios. We conduct an extensive computational study to illustrate the advantage of the proposed partition-based decomposition algorithms compared with the state-of-the-art approaches. [ABSTRACT FROM AUTHOR]