1,159 results
Search Results
2. Extension of the Directed Search Domain algorithm for multi-objective optimization to higher dimensions.
- Author
-
Yu, Boxi and Utyuzhnikov, Sergey
- Subjects
- *
SEARCH algorithms , *ALGORITHMS - Abstract
This paper addresses the problem of generating an evenly distributed set of Pareto solutions. It appears in real-life applications related to multi-objective optimization when it is important to represent the entire Pareto front with a minimal cost. There exist only a few algorithms which are able to tackle this problem in a general formulation. The Directed Search Domain (DSD) algorithm has proved to be efficient and quite universal. It has successfully been applied to different challengeable test cases. In this paper for the first time the DSD approach is systematically extended and applied to problems with higher dimensions. The modified algorithm does not have any formal limitation on the number of objective functions that is important for practical applications. The efficacy of the algorithm is demonstrated on a number of test cases. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. Scheduling activities in project network with feeding precedence relations: an earliest start forward recursion algorithm.
- Author
-
Bianco, Lucio, Caramia, Massimiliano, Giordani, Stefano, and Salvatore, Alessio
- Subjects
SCHEDULING ,NETWORK analysis (Planning) ,JOB shops ,MANUFACTURING processes ,UNITS of time ,ALGORITHMS - Abstract
In some production processes, the effort associated with a certain activity for its execution can vary over time. In this case, the amount of work per time unit devoted to each activity, so as its duration, is not univocally determined. This kind of problem can be represented by an activity project network with the so-called feeding precedence relations, and activity variable execution intensity. In this paper, we propose a forward recursion algorithm able to find the earliest start and finish times of each activity, in O (m log n) time, with n and m being the number of activities and the number of precedence relations, respectively. In particular, this requires the calculation of the (optimal) execution intensity profile, for each activity, that warrants the earliest start schedule and the minimum completion time of the project. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
4. Algorithms to compute the energetic lower bounds of the cumulative scheduling problem
- Author
-
Carlier, Jacques, Jouglet, Antoine, and Sahli, Abderrahim
- Published
- 2024
- Full Text
- View/download PDF
5. Two phase algorithm for bi-objective relief distribution location problem.
- Author
-
Mishra, Mamta, Singh, Surya Prakash, and Gupta, Manmohan Prasad
- Subjects
BIG data ,ALGORITHMS ,NP-hard problems ,GENETIC algorithms ,METAHEURISTIC algorithms - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
6. An Annotated Bibliography of Personnel Scheduling and Rostering.
- Author
-
Ernst, A. T., Jiang, H., Krishnamoorthy, M., Owens, B., and Sier, D.
- Subjects
PRODUCTION scheduling ,PERSONNEL management ,BIBLIOGRAPHY ,ALGORITHMS ,LABOR supply ,WORKFORCE planning ,OPERATIONS research - Abstract
Computational methods for rostering and personnel scheduling has been a subject of continued research and commercial interest since the 1950s. This annotated bibliography puts together a comprehensive collection of some 700 references in this area, focusing mainly on algorithms for generating rosters and personnel schedules but also covering related areas such as workforce planning and estimating staffing requirements. We classify these papers according to the type of problem addressed, the application areas covered and the methods used. In addition, a short summary is provided for each paper. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
7. An algorithm to solve multi-objective integer quadratic programming problem.
- Author
-
Kushwah, Prerna and Sharma, Vikas
- Subjects
INTEGER programming ,QUADRATIC programming ,LINEAR programming ,ALGORITHMS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
8. Practices in timetabling in higher education institutions: a systematic review.
- Author
-
Oude Vrielink, R. A., Jansen, E. A., Hans, E. W., and van Hillegersberg, J.
- Subjects
HIGHER education ,COMMERCE ,COMPUTER software ,ALGORITHMS ,LITERATURE reviews - Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
9. Models and computational algorithms for maritime risk analysis: a review.
- Author
-
Lim, Gino J., Cho, Jaeyoung, Bora, Selim, Biobaku, Taofeek, and Parsaei, Hamid
- Subjects
RISK assessment ,MARINE accidents ,LITERATURE reviews ,SHIPS' safety regulations ,ALGORITHMS - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
10. Credit risk classification: an integrated predictive accuracy algorithm using artificial and deep neural networks.
- Author
-
Mahbobi, Mohammad, Kimiagari, Salman, and Vasudevan, Marriappan
- Subjects
CREDIT risk ,CREDIT analysis ,ALGORITHMS ,MACHINE learning - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
11. Simulation-based system reliability estimation of a multi-state flow network for all possible demand levels.
- Author
-
Chang, Ping-Chen, Huang, Ding-Hsiang, and Huang, Cheng-Fu
- Subjects
- *
RELIABILITY in engineering , *NP-hard problems , *COMPUTATIONAL complexity , *SIMULATION methods & models , *ALGORITHMS - Abstract
The multi-state flow network (MSFN) serves as a fundamental framework for real-life network-structured systems and various applications. The system reliability of the MSFN, denoted as Rd, is defined as the probability of successfully transmitting at least d units of demand from a source to a terminal. Current analytical algorithms are characterized by their computational complexity, specifically falling into the NP-hard problem to evaluate exact system reliability. Moreover, existing analytical algorithms for calculating Rd are basically designed for predetermined values of d. This limitation hinders the ability of decision-makers to flexibly choose the most appropriate based on the specific characteristics of the given scenarios or applications. This means that these methods are incapable of simultaneously calculating system reliability for various demand levels. Therefore, this paper develops a simulation-based algorithm to estimate system reliability for all possible demand levels simultaneously such that we can eliminate the need to rely on repeat procedures for each specified d. An experimental investigation was carried out on a benchmark network and a practical network to validate the effectiveness and performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
12. Enhanced branch-and-bound algorithm for chance constrained programs with Gaussian mixture models.
- Author
-
Wei, Jinxiang, Hu, Zhaolin, Luo, Jun, and Zhu, Shushang
- Subjects
- *
GAUSSIAN mixture models , *PROBLEM solving , *ALGORITHMS - Abstract
We study a class of chance constrained programs (CCPs) where the underlying distribution is modeled by a Gaussian mixture model. As the original work, Hu et al. (IISE Trans 54(12):1117–1130, 2022. https://doi.org/10.1080/24725854.2021.2001608) developed a spatial branch-and-bound (B &B) algorithm to solve the problems. In this paper, we propose an enhanced procedure to speed up the computation of B &B algorithm. We design an enhanced pruning strategy that explores high-potential domains and an augmented branching strategy that prevents redundant computations. We integrate the new strategies into original framework to develop an enhanced B &B algorithm, and illustrate how the enhanced algorithm improves on the original approach. Furthermore, we extend the enhanced B &B framework to handle the CCPs with multiple chance constraints, which is not considered in the previous work. We evaluate the performance of our new algorithm through extensive numerical experiments and apply it to solve a real-world portfolio selection problem. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
13. An efficient searching method for minimal path vectors in multi-state networks.
- Author
-
Lin, Yi-Kuei and Chen, Shin-Guang
- Subjects
ALGORITHMS ,PROBABILITY theory - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
14. A two-step stochastic approach for operating rooms scheduling in multi-resource environment.
- Author
-
Atighehchian, Arezoo, Sepehri, Mohammad Mehdi, Shadpour, Pejman, and Kianfar, Kamran
- Subjects
OPERATING rooms ,STOCHASTIC programming ,QUALITY of service ,ALGORITHMS ,STOCHASTIC models - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
15. KNN and adaptive comfort applied in decision making for HVAC systems.
- Author
-
Aparicio-Ruiz, Pablo, Barbadilla-Martín, Elena, Guadix, José, and Cortés, Pablo
- Subjects
THERMAL comfort ,DECISION making ,SUPPORT vector machines ,ALGORITHMS ,AIR conditioning ,HEATING & ventilation industry - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
16. Coercivity and generalized proximal algorithms: application—traveling around the world.
- Author
-
Quiroz, E. A. Papa, Soubeyran, A., and Oliveira, P. R.
- Subjects
DISTANCE education ,COERCIVE fields (Electronics) ,VOYAGES around the world ,ALGORITHMS ,APPROXIMATION error - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
17. New algorithm for checking Pareto optimality in bimatrix games.
- Author
-
Kicsiny, Richárd and Varga, Zoltán
- Subjects
PARETO optimum ,ALGORITHMS ,GAME theory ,GAMES - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
18. A convergence analysis for a convex version of Dikin's algorithm.
- Author
-
Jie Sun
- Subjects
STOCHASTIC convergence ,ALGORITHMS ,CONVEX programming ,LINEAR programming ,MATHEMATICAL programming - Abstract
This paper is concerned with the convergence property of Dikin's algorithm applied to linearly constrained smooth convex programs. We study a version of Dikin's algorithm in which a second-order approximation of the objective function is minimized at each iteration together with an affine transformation of the variables. We prove that the sequence generated by the algorithm globally converges to a limit point at a local linear rate if the objective function satisfies a Hessian similarity condition. The result is of a theoretical nature in the sense that in order to ensure that the limit point is an ε-optimal solution, one may have to restrict the steplength to the order of O(ε). The analysis does not depend on non-degeneracy assumptions. [ABSTRACT FROM AUTHOR]
- Published
- 1996
- Full Text
- View/download PDF
19. Improved multiobjective differential evolution with spherical pruning algorithm for optimizing 3D printing technology parametrization process.
- Author
-
Cruz, Luciano Ferreira, Pinto, Flavia Bernardo, Camilotti, Lucas, Santanna, Angelo Marcio Oliveira, Freire, Roberto Zanetti, and dos Santos Coelho, Leandro
- Subjects
DIFFERENTIAL evolution ,THREE-dimensional printing ,APPROXIMATION algorithms ,ALGORITHMS ,MANUFACTURING processes - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
20. An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot.
- Author
-
Yao, Baozhen, Yu, Bin, Hu, Ping, Gao, Junjie, and Zhang, Mingheng
- Subjects
PARTICLE swarm optimization ,VEHICLE routing problem ,SELF-adaptive software ,ALGORITHMS ,COMBINATORIAL optimization - Abstract
In this paper, a carton heterogeneous vehicle routing problem with a collection depot is presented, which can collaboratively pick the cartons from several carton factories to a collection depot and then from the depot to serve their corresponding customers by using of heterogeneous fleet. Since the carton heterogeneous vehicle routing problem with a collection depot is a very complex problem, particle swarm optimization (PSO) is used to solve the problem in this paper. To improve the performance of the PSO, a self-adaptive inertia weight and a local search strategy are used. At last, the model and the algorithm are illustrated with two test examples. The results show that the proposed PSO is an effective method to solve the multi-depot vehicle routing problem, and the carton heterogeneous vehicle routing problem with a collection depot. Moreover, the proposed model is feasible with a saving of about 28 % in total delivery cost and could obviously reduce the required number of vehicles when comparing to the actual instance. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
21. Randomized Progressive Hedging methods for multi-stage stochastic programming.
- Author
-
Bareilles, Gilles, Laguel, Yassine, Grishchenko, Dmitry, Iutzeler, Franck, and Malick, Jérôme
- Subjects
STOCHASTIC programming ,MONOTONE operators ,OPERATIONS research ,ALGORITHMS ,SCIENTIFIC community - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
22. Optimised solutions to the last-mile delivery problem in London using a combination of walking and driving.
- Author
-
Martinez-Sykora, Antonio, McLeod, Fraser, Lamas-Fernandez, Carlos, Bektaş, Tolga, Cherrett, Tom, and Allen, Julian
- Subjects
METROPOLITAN areas ,ALGORITHMS - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
23. A novel sustainable multi-objective optimization model for forward and reverse logistics system under demand uncertainty.
- Author
-
Zarbakhshnia, Navid, Kannan, Devika, Kiani Mavi, Reza, and Soleimani, Hamed
- Subjects
REVERSE logistics ,PARTICLE swarm optimization ,LINEAR programming ,GENETIC algorithms ,ALGORITHMS - Abstract
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 CO
2 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]- Published
- 2020
- Full Text
- View/download PDF
24. On the analytical derivation of efficient sets in quad-and-higher criterion portfolio selection.
- Author
-
Qi, Yue and Steuer, Ralph E.
- Subjects
DIVIDEND yield ,ALGORITHMS ,MATHEMATICS ,PARABOLOID ,SUSTAINABILITY - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
25. A Conic Trust-Region Method for Nonlinearly Constrained Optimization.
- Author
-
Wenyu Sun and Ya-Xiang Yuan
- Subjects
MATHEMATICAL optimization ,METHODOLOGY ,MATHEMATICAL functions ,DIFFERENTIAL equations ,ALGORITHMS ,LAGRANGE equations ,NONLINEAR functional analysis - Abstract
Trust-region methods are powerful optimization methods. The conic model method is a new type of method with more information available at each iteration than standard quadratic-based methods. Can we combine their advantages to form a more powerful method for constrained optimization? In this paper we give a positive answer and present a conic trust-region algorithm for non-linearly constrained optimization problems. The trust-region subproblem of our method is to minimize a conic function subject to the linearized constraints and the trust region bound. The use of conic functions allows the model to interpolate function values and gradient values of the Lagrange function at both the current point and previous iterate point. Since conic functions are the extension of quadratic functions, they approximate general nonlinear functions better than quadratic functions. At the same time, the new algorithm possesses robust global properties. In this paper we establish the global convergence of the new algorithm under standard conditions. [ABSTRACT FROM AUTHOR]
- Published
- 2001
- Full Text
- View/download PDF
26. Efficient algorithms for buffer space allocation.
- Author
-
Gershwin, Stanley B. and Schor, James E.
- Subjects
ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,MAXIMA & minima ,OPERATIONS research ,EXPERIMENTAL design - Abstract
This paper describes efficient algorithms for determining how buffer space should be allocated in a flow line. We analyze two problems: a primal problem, which minimizes total buffer space subject to a production rate constraint; and a dual problem, which maximizes production rate subject to a total buffer space constraint. The dual problem is solved by means of a gradient method, and the primal problem is solved using the dual solution. Numerical results are presented. Profit optimization problems are natural generalizations of the primal and dual problems, and we show how they can be solved using essentially the same algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
27. Pareto solutions as limits of collective traps: an inexact multiobjective proximal point algorithm.
- Author
-
Bento, G. C., Cruz Neto, J. X., Meireles, L. V., and Soubeyran, A.
- Subjects
RIEMANNIAN manifolds ,NONSMOOTH optimization ,ALGORITHMS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
28. An inexact scalarization proximal point method for multiobjective quasiconvex minimization.
- Author
-
Papa Quiroz, E. A. and Cruzado, S.
- Subjects
REGULARIZATION parameter ,ALGORITHMS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
29. A Lagrangian relaxation algorithm for optimizing a bi-objective agro-supply chain model considering CO2 emissions.
- Author
-
Keshavarz-Ghorbani, Fatemeh and Pasandideh, Seyed Hamid Reza
- Subjects
ROBUST optimization ,LINEAR programming ,ALGORITHMS ,PROBLEM solving ,SUPPLY chains - Abstract
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 CO
2 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]- Published
- 2022
- Full Text
- View/download PDF
30. On Cournot-Bertrand competition with differentiated products.
- Author
-
Askar, S.
- Subjects
GAMES ,NASH equilibrium ,BIFURCATION theory ,NONLINEAR analysis ,ALGORITHMS - Abstract
In this paper, we present a game theoretic framework for Cournot-Bertrand competition based on a nonlinear price function. The competition is between two firms and is assumed to take place in terms of pricing decision and quantity produced. However, the proposed objective function has not been used in literature before, yet the throughput obtained in this paper generalizes some of the existing results in literature. The competitive interaction between firms is described and analyzed using best-reply reaction, proposed adaptive adjustment and bounded rationality approach. The condition of stability of Nash equilibrium (NE) is induced by these approaches. Interestingly, we prove that there exists exactly a unique NE. Furthermore, it is noticed that when firms adopt best-reply and the proposed adaptive adjustment, the firms' strategic variables become asymptotically stable. On the contrary, when the bounded rationality is used both quantity and price behave chaotically due to bifurcation occurred. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
31. Preface.
- Author
-
Gervet, Carmen and Wallace, Mark
- Subjects
ARTIFICIAL intelligence ,OPERATIONS research ,INDUSTRIAL engineering ,ALGORITHMS ,INTELLIGENT agents - Abstract
Introduces several articles on artificial intelligence and operation research. Application of specialized algorithm in solving an optimization problem; Extensions of a technique called probe backtrack search used for combining linear and resource constrained problems; Methodology in performing constraint propagation.
- Published
- 2003
- Full Text
- View/download PDF
32. Weapon-target assignment problem: exact and approximate solution algorithms.
- Author
-
Andersen, Alexandre Colaers, Pavlikov, Konstantin, and Toffolo, Túlio A. M.
- Subjects
ASSIGNMENT problems (Programming) ,LINEAR programming ,COMBINATORIAL optimization ,INTEGER programming ,ALGORITHMS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
33. Multi-phase algorithm design for accurate and efficient model fitting.
- Author
-
Steakelum, Joshua, Aubertine, Jacob, Chen, Kenan, Nagaraju, Vidhyashree, and Fiondella, Lance
- Subjects
SOFTWARE reliability ,POISSON processes ,SOFT computing ,PARAMETER estimation ,ALGORITHMS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
34. Timetable construction: the algorithms and complexity perspective.
- Author
-
Kingston, Jeffrey
- Subjects
TIME management ,ALGORITHMS ,BIPARTITE graphs ,NP-complete problems ,COMPUTATIONAL complexity - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
35. Sets in excess demand in simple ascending auctions with unit-demand bidders.
- Author
-
Andersson, T., Andersson, C., and Talman, A. J. J.
- Subjects
AUCTIONS ,BIDDERS ,ITERATIVE methods (Mathematics) ,ALGORITHMS ,ECONOMIC demand ,ECONOMIC equilibrium - Abstract
This paper analyzes the problem of selecting a set of items whose prices are to be updated in the next iteration in so called simple ascending auctions with unit-demand bidders. A family of sets called “sets in excess demand” is introduced, and the main result demonstrates that a simple ascending auction always terminates at the minimum Walrasian equilibrium prices if and only if the selection belongs to this family. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
36. An inventory model under price and stock dependent demand for controllable deterioration rate with shortages and preservation technology investment.
- Author
-
Mishra, Umakanta, Cárdenas-Barrón, Leopoldo, Tiwari, Sunil, Shaikh, Ali, and Treviño-Garza, Gerardo
- Subjects
STOCKS (Finance) ,PEJORATION (Linguistics) ,INVESTMENTS ,ALGORITHMS ,SENSITIVITY analysis - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
37. The time-dependent orienteering problem with time windows: a fast ant colony system.
- Author
-
Verbeeck, Cédric, Vansteenwegen, Pieter, and Aghezzaf, El-Houssaine
- Subjects
ORIENTEERING ,LOGISTICS ,LOGISTICS managers ,MANAGEMENT ,ALGORITHMS - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
38. Dimensionality representation of linear discriminant function space for the multiple-group problem: An MIP approach.
- Author
-
Pavur, Robert
- Subjects
MATHEMATICAL programming ,DISCRIMINANT analysis ,ANALYSIS of covariance ,ALGORITHMS ,DIMENSIONS ,FUNCTION spaces - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 1997
- Full Text
- View/download PDF
39. A simplified global convergence proof of the affine scaling algorithm.
- Author
-
Monteiro, R. D. C., Tsuchiya, T., and Wang, Y.
- Subjects
AFFINE geometry ,LINEAR programming ,STOCHASTIC convergence ,ALGORITHMS ,FRACTIONS ,OPERATIONS research - Abstract
This paper presents a simplified and self-contained global convergence proof for the affine scaling algorithm applied to degenerate linear programming problems. Convergence of the sequence of dual estimates to the center of the optimal dual face is also proven. In addition, we give a sharp rate of convergence result for the sequence of objective function values. All these results are proved with respect to the long step version of the affine scaling algorithm in which we move a fraction λ, where λ ϵ (0,2/3], of the step to the boundary of the feasible region. [ABSTRACT FROM AUTHOR]
- Published
- 1993
- Full Text
- View/download PDF
40. PARAMETRIC METHODS IN INTEGER LINEAR PROGRAMMING.
- Author
-
Jenkins, Larry
- Subjects
LINEAR programming ,ALGORITHMS ,INTEGER programming ,MATHEMATICAL programming ,OPERATIONS research - Abstract
In contrast to methods of parametric linear programming which were developed soon after the invention of the simplex algorithm and are easily included as an extension of that method, techniques for parametric analysis on integer programs are not well known and require considerable effort to append them to an integer programming solution algorithm. The paper reviews some of the theory employed in parametric integer programming, then discusses algorithmic work in this area over the last 15 years when integer programs are solved by different methods. A summary of applications is included and the article concludes that parametric integer programming is a valuable tool of analysis awaiting further popularization. [ABSTRACT FROM AUTHOR]
- Published
- 1990
- Full Text
- View/download PDF
41. SCHEDULING FLEXIBLE MACHINING AND ASSEMBLY SYSTEMS.
- Author
-
Kusiak, Andrew
- Subjects
PRODUCTION scheduling ,PRODUCTION control ,FLEXIBLE manufacturing systems ,AUTOMATION ,PRODUCTION engineering ,OPERATIONS research ,INDUSTRIAL engineering - Abstract
Most scheduling papers consider flexible machining and assembly systems as being independent. In this paper, a heuristic two-level scheduling algorithm for a system consisting of a machining and an assembly subsystem is developed. It is shown that the upper level problem is equivalent to the two machine flow shop problem. The algorithm at the lower level schedules jobs according to the established product and part priorities. Related issues, such as batching, due dates, process planning and alternative routes, are discussed. The algorithm and associated concepts are illustrated on a number of numerical examples. [ABSTRACT FROM AUTHOR]
- Published
- 1988
- Full Text
- View/download PDF
42. Improved algorithms for proportionate flow shop scheduling with due-window assignment.
- Author
-
Qian, Jin and Han, Haiyan
- Subjects
FLOW shop scheduling ,ALGORITHMS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
43. Flow location (FlowLoc) problems: dynamic network flows and location models for evacuation planning.
- Author
-
Hamacher, Horst, Heller, Stephanie, and Rupp, Benjamin
- Subjects
COMPUTER simulation ,ALGORITHMS ,INTEGER programming ,PARAMETRIC modeling ,HEURISTIC programming ,MATROIDS - Abstract
In this paper we combine two modeling tools to predict and evaluate evacuation plans: (dynamic) network flows and locational analysis. We present three exact algorithms to solve the single facility version 1-FlowLoc of this problem and compare their running times. After proving the $\mathcal{NP}$-completeness of the multi facility q-FlowLoc problem, a mixed integer programming formulation and a heuristic for q-FlowLoc are proposed. The paper is concluded by discussing some generalizations of the FlowLoc problem, such as the multi-terminal problem, interdiction problem, the parametric problem and the generalization of the FlowLoc problem to matroids. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
44. Preface.
- Author
-
Sen, Suvrajeet and Higle, Julia
- Subjects
STOCHASTIC programming ,ALGORITHMS - Abstract
The article introduces reports published within the issue including one on the strategies of a risk-averse investor who maximizes the expected value of his/her wealth, one on solving a sequence of two-stage stochastic programs, and one on a branch-and-bound algorithm for probabilistically constrained problems.
- Published
- 2010
- Full Text
- View/download PDF
45. Analysis of multiserver retrial queueing system: A martingale approach and an algorithm of solution.
- Author
-
Abramov, Vyacheslav M.
- Subjects
QUEUING theory ,STOCHASTIC processes ,PROBABILITY theory ,RANDOM variables ,ALGORITHMS ,OPERATIONS research - Abstract
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 μ
1 . A time between retrials is exponentially distributed with parameter μ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 μ2 increases to infinity. As μ2 →∞, 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. [ABSTRACT FROM AUTHOR]- Published
- 2006
- Full Text
- View/download PDF
46. Matchings under distance constraints I.
- Author
-
Madarasi, Péter
- Subjects
ALGORITHMS ,POLYNOMIAL time algorithms ,APPROXIMATION algorithms ,NP-complete problems ,SEARCH algorithms - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
47. On solving cycle problems with Branch-and-Cut: extending shrinking and exact subcycle elimination separation algorithms.
- Author
-
Kobeaga, Gorka, Merino, María, and Lozano, Jose A.
- Subjects
PROBLEM solving ,ALGORITHMS ,GRAPH algorithms ,EMPLOYEE motivation ,ORIENTEERING - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
48. Multi-objective simulation optimization for complex urban mass rapid transit systems.
- Author
-
Schmaranzer, David, Braune, Roland, and Doerner, Karl F.
- Subjects
PUBLIC transit ,DISCRETE event simulation ,COVARIANCE matrices ,ALGORITHMS ,GENETIC algorithms - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
49. An exact algorithm for the resource constrained home health care vehicle routing problem.
- Author
-
Tanoumand, Neda and Ünlüyurt, Tonguç
- Subjects
VEHICLE routing problem ,HOME care services ,ALGORITHMS ,TEAMS in the workplace ,NURSES as patients ,MATHEMATICS students ,NURSES - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
50. An automatic clustering for interval data using the genetic algorithm.
- Author
-
Vovan, Tai, Phamtoan, Dinh, Tuan, Le Hoang, and Nguyentrang, Thao
- Subjects
GENETIC algorithms ,ALGORITHMS ,CLUSTER analysis (Statistics) - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.