Einloggen

Thematische Bibliographien / Algorithmes Branch-And-Cut / Zeitschriftenartikel

Zeitschriftenartikel zum Thema „Algorithmes Branch-And-Cut“

Um die anderen Arten von Veröffentlichungen zu diesem Thema anzuzeigen, folgen Sie diesem Link: Algorithmes Branch-And-Cut.

Autor: Grafiati

Veröffentlicht am 7. September 2024

Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an

Wählen Sie eine Art der Quelle aus:

Machen Sie sich mit Top-50 Zeitschriftenartikel für die Forschung zum Thema "Algorithmes Branch-And-Cut" bekannt.

Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.

Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.

Sehen Sie die Zeitschriftenartikel für verschiedene Spezialgebieten durch und erstellen Sie Ihre Bibliographie auf korrekte Weise.

1

Fragoso, Felipe C., Gilberto F. de Sousa Filho und Fábio Protti. „Declawing a graph: polyhedra and Branch-and-Cut algorithms“. Journal of Combinatorial Optimization 42, Nr. 1 (19.04.2021): 85–124. http://dx.doi.org/10.1007/s10878-021-00736-y.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

2

Costa, Luciano, Claudio Contardo und Guy Desaulniers. „Exact Branch-Price-and-Cut Algorithms for Vehicle Routing“. Transportation Science 53, Nr. 4 (Juli 2019): 946–85. http://dx.doi.org/10.1287/trsc.2018.0878.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

3

Pereira, Dilson Lucas, Michel Gendreau und Alexandre Salles da Cunha. „Branch-and-cut and Branch-and-cut-and-price algorithms for the adjacent only quadratic minimum spanning tree problem“. Networks 65, Nr. 4 (02.02.2015): 367–79. http://dx.doi.org/10.1002/net.21580.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

4

Fouilhoux, Pierre, A. Ridha Mahjoub, Alain Quilliot und Hélène Toussaint. „Branch-and-Cut-and-Price algorithms for the preemptive RCPSP“. RAIRO - Operations Research 52, Nr. 2 (April 2018): 513–28. http://dx.doi.org/10.1051/ro/2018031.

Der volle Inhalt der Quelle

Annotation:

In this article, we address the preemptive Resource-Constrained Precedence Scheduling Problem. We propose two mixed integer formulations containing an exponential number of variables and inequalities. An antichain is a set of pairwise incomparable elements with respect to the precedence constraints. In the first formulation, the integer variables are associated with the antichains. For the second, the integer variables are limited to a particular subset of antichains. We propose two Branch-and-Cut-and-Price algorithms for each of these formulations. We introduce some valid inequalities in order to reinforce the second formulation. Finally, we give some computational results on instances of the PSPLIB and compare the formulations.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

5

Calvete, Herminia I., Concepción Domínguez, Carmen Galé, Martine Labbé und Alfredo Marín. „The rank pricing problem: Models and branch-and-cut algorithms“. Computers & Operations Research 105 (Mai 2019): 12–31. http://dx.doi.org/10.1016/j.cor.2018.12.011.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

6

Li, Xiangyong, und Y. P. Aneja. „Regenerator location problem: Polyhedral study and effective branch-and-cut algorithms“. European Journal of Operational Research 257, Nr. 1 (Februar 2017): 25–40. http://dx.doi.org/10.1016/j.ejor.2016.07.032.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

7

Duchenne, Éric, Gilbert Laporte und Frédéric Semet. „Branch-and-cut algorithms for the undirected m-Peripatetic Salesman Problem“. European Journal of Operational Research 162, Nr. 3 (Mai 2005): 700–712. http://dx.doi.org/10.1016/j.ejor.2003.09.024.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

8

Archetti, Claudia, Nicola Bianchessi und M. Grazia Speranza. „Branch-and-cut algorithms for the split delivery vehicle routing problem“. European Journal of Operational Research 238, Nr. 3 (November 2014): 685–98. http://dx.doi.org/10.1016/j.ejor.2014.04.026.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

9

Desaulniers, Guy, Diego Pecin und Claudio Contardo. „Selective pricing in branch-price-and-cut algorithms for vehicle routing“. EURO Journal on Transportation and Logistics 8, Nr. 2 (Juni 2019): 147–68. http://dx.doi.org/10.1007/s13676-017-0112-9.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

10

Di Summa, Marco, Andrea Grosso und Marco Locatelli. „Branch and cut algorithms for detecting critical nodes in undirected graphs“. Computational Optimization and Applications 53, Nr. 3 (09.02.2012): 649–80. http://dx.doi.org/10.1007/s10589-012-9458-y.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

11

Bektaş, Tolga, Güneş Erdoğan und Stefan Røpke. „Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem“. Transportation Science 45, Nr. 3 (August 2011): 299–316. http://dx.doi.org/10.1287/trsc.1100.0352.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

12

Hintsch, Timo, Stefan Irnich und Lone Kiilerich. „Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem“. Transportation Science 55, Nr. 3 (Mai 2021): 687–705. http://dx.doi.org/10.1287/trsc.2020.1036.

Der volle Inhalt der Quelle

Annotation:

The soft-clustered capacitated arc-routing problem (SoftCluCARP) is a variant of the classical capacitated arc-routing problem. The only additional constraint is that the set of required edges, that is, the streets to be serviced, is partitioned into clusters, and feasible routes must respect the soft-cluster constraint, that is, all required edges of the same cluster must be served by the same vehicle. In this article, we design an effective branch-price-and-cut algorithm for the exact solution of the SoftCluCARP. Its new components are a metaheuristic and branch-and-cut-based solvers for the solution of the column-generation subproblem, which is a profitable rural clustered postman tour problem. Although postman problems with these characteristics have been studied before, there is one fundamental difference here: clusters are not necessarily vertex-disjoint, which prohibits many preprocessing and modeling approaches for clustered postman problems from the literature. We present an undirected and a windy formulation for the pricing subproblem and develop and computationally compare two corresponding branch-and-cut algorithms. Cutting is also performed at the master-program level using subset-row inequalities for subsets of size up to five. For the first time, these nonrobust cuts are incorporated into MIP-based routing subproblem solvers using two different modeling approaches. In several computational studies, we calibrate the individual algorithmic components. The final computational experiments prove that the branch-price-and-cut algorithm equipped with these problem-tailored components is effective: The largest SoftCluCARP instances solved to optimality have more than 150 required edges or more than 50 clusters.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

13

Munapo, Elias, Joshua Chukwuere und Trust Tawanda. „Solving Linear Integer Models with Variable Bounding“. Forecasting 5, Nr. 2 (05.05.2023): 443–52. http://dx.doi.org/10.3390/forecast5020024.

Der volle Inhalt der Quelle

Annotation:

We present a technique to solve the linear integer model with variable bounding. By using the continuous optimal solution of the linear integer model, the variable bounds for the basic variables are approximated and then used to calculate the optimal integer solution. With the variable bounds of the basic variables known, solving a linear integer model is easier by using either the branch and bound, branch and cut, branch and price, branch cut and price, or branch cut and free algorithms. Thus, the search for large numbers of subproblems, which are unnecessary and common for NP Complete linear integer models, is avoided.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

14

Adulyasak, Yossiri, Jean-François Cordeau und Raf Jans. „Formulations and Branch-and-Cut Algorithms for Multivehicle Production and Inventory Routing Problems“. INFORMS Journal on Computing 26, Nr. 1 (Februar 2014): 103–20. http://dx.doi.org/10.1287/ijoc.2013.0550.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

15

Qiu, Yuzhuo, Liang Wang, Xuanjing Fang, Panos M. Pardalos und Boris Goldengorin. „Formulations and branch-and-cut algorithms for production routing problems with time windows“. Transportmetrica A: Transport Science 14, Nr. 8 (26.01.2018): 669–90. http://dx.doi.org/10.1080/23249935.2018.1427157.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

16

Gadegaard, Sune Lauth, Lars Relund Nielsen und Matthias Ehrgott. „Bi-objective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets“. INFORMS Journal on Computing 31, Nr. 4 (Oktober 2019): 790–804. http://dx.doi.org/10.1287/ijoc.2018.0846.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

17

Andreas, April K., J. Cole Smith und Simge Küçükyavuz. „Branch-and-price-and-cut algorithms for solving the reliable h-paths problem“. Journal of Global Optimization 42, Nr. 4 (30.10.2007): 443–66. http://dx.doi.org/10.1007/s10898-007-9254-x.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

18

Drexl, Michael. „Branch-and-cut algorithms for the vehicle routing problem with trailers and transshipments“. Networks 63, Nr. 1 (20.09.2013): 119–33. http://dx.doi.org/10.1002/net.21526.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

19

Saharidis, Georgios K. D. „Review of Solution Approaches for the Symmetric Traveling Salesman Problem“. International Journal of Information Systems and Supply Chain Management 7, Nr. 1 (Januar 2014): 73–87. http://dx.doi.org/10.4018/ijisscm.2014010105.

Der volle Inhalt der Quelle

Annotation:

In this paper, the main known exact and heuristic solution approaches and algorithms for the symmetric Traveling Salesman Problem (TSP), published after 1992, are surveyed. The paper categorize the most important existing algorithm to 6 main groups: i) Genetic algorithms, ii) Ant colony methods, iii) Neural Methods, iv) Local search algorithms and Tabu search, v) Lagrangian methods and vi) Branch and bound and branch & cut algorithms.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

20

Christof, T., und G. Reinelt. „Algorithmic Aspects of Using Small Instance Relaxations in Parallel Branch-and-Cut“. Algorithmica 30, Nr. 4 (01.10.2001): 597–629. http://dx.doi.org/10.1007/s00453-001-0029-3.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

21

Rebennack, Steffen, Gerhard Reinelt und Panos M. Pardalos. „A tutorial on branch and cut algorithms for the maximum stable set problem“. International Transactions in Operational Research 19, Nr. 1-2 (Januar 2012): 161–99. http://dx.doi.org/10.1111/j.1475-3995.2011.00805.x.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

22

Ropke, Stefan, Jean-François Cordeau und Gilbert Laporte. „Models and branch-and-cut algorithms for pickup and delivery problems with time windows“. Networks 49, Nr. 4 (2007): 258–72. http://dx.doi.org/10.1002/net.20177.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

23

Guimarães, Dilson Almeida, und Alexandre Salles da Cunha. „The minimum area spanning tree problem: Formulations, Benders decomposition and branch-and-cut algorithms“. Computational Geometry 97 (August 2021): 101771. http://dx.doi.org/10.1016/j.comgeo.2021.101771.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

24

Bicalho, Luis Henrique, Alexandre Salles da Cunha und Abilio Lucena. „Branch-and-cut-and-price algorithms for the Degree Constrained Minimum Spanning Tree Problem“. Computational Optimization and Applications 63, Nr. 3 (14.09.2015): 755–92. http://dx.doi.org/10.1007/s10589-015-9788-7.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

25

Wu, Hao, Hao Wen und Yushan Zhu. „Branch-and-Cut Algorithmic Framework for 0−1 Mixed-Integer Convex Nonlinear Programs“. Industrial & Engineering Chemistry Research 48, Nr. 20 (21.10.2009): 9119–27. http://dx.doi.org/10.1021/ie9001074.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

26

Gouveia, Luis, Markus Leitner und Mario Ruthmair. „Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman Problem“. European Journal of Operational Research 262, Nr. 3 (November 2017): 908–28. http://dx.doi.org/10.1016/j.ejor.2017.04.061.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

27

Ibrahim, Abdullahi, Jeremiah Ishaya, Rabiat Abdulaziz und Sowole Samuel. „Solving some variants of vehicle routing problem with Branch-and-cut and Column generation algorithms“. Open Journal of Mathematical Sciences 4, Nr. 1 (08.03.2020): 63–73. http://dx.doi.org/10.30538/oms2020.0095.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

28

Gendron, Bernard, Abilio Lucena, Alexandre Salles da Cunha und Luidi Simonetti. „Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem“. INFORMS Journal on Computing 26, Nr. 4 (November 2014): 645–57. http://dx.doi.org/10.1287/ijoc.2013.0589.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

29

Pessoa, Artur Alves, Michael Poss, Ruslan Sadykov und François Vanderbeck. „Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty“. Operations Research 69, Nr. 3 (Mai 2021): 739–54. http://dx.doi.org/10.1287/opre.2020.2035.

Der volle Inhalt der Quelle

Annotation:

Capacitated vehicle routing problems are widely studied combinatorial optimization problems, and branch-and-cut-and-price algorithms can solve instances harder than ever before. These models, however, neglect that demands volumes are often not known with precision when planning the vehicle routes, thus incentivizing decision makers to significantly overestimate the volumes for avoiding coping with infeasible routes. A robust formulation that models demand uncertainty through a knapsack polytope is considered. A new branch-and-cut-and-price algorithm for the problem is provided, which combines efficient algorithms for the problem with no uncertainty with profound results in robust combinatorial optimization and includes novel heuristics and new valid inequalities. The numerical results illustrate that the resulting approach is two orders of magnitude faster that the best algorithm from the literature, solving twice as many instances to optimality.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

30

He, Wei, Yiyuan Cheng, Ling Xia und Feng Liu. „A New Particle Swarm Optimization-Based Method for Phase Unwrapping of MRI Data“. Computational and Mathematical Methods in Medicine 2012 (2012): 1–9. http://dx.doi.org/10.1155/2012/475745.

Der volle Inhalt der Quelle

Annotation:

A new method based on discrete particle swarm optimization (dPSO) algorithm is proposed to solve the branch-cut phase unwrapping problem of MRI data. In this method, the optimal order of matching the positive residues with the negative residues is first identified by the dPSO algorithm, then the branch cuts are placed to join each pair of the opposite polarity residues, and in the last step phases are unwrapped by flood-fill algorithm. The performance of the proposed algorithm was tested on both simulated phase image and MRI wrapped phase data sets. The results demonstrated that, compared with conventionally used branch-cut phase unwrapping algorithms, the dPSO algorithm is rather robust and effective.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

31

J�nger, Michael, und Stefan Thienel. „The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization“. Software: Practice and Experience 30, Nr. 11 (2000): 1325–52. http://dx.doi.org/10.1002/1097-024x(200009)30:11<1325::aid-spe342>3.0.co;2-t.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

32

Chwatal, Andreas M., und Günther R. Raidl. „Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques“. Advances in Operations Research 2011 (2011): 1–38. http://dx.doi.org/10.1155/2011/143732.

Der volle Inhalt der Quelle

Annotation:

We present exact mixed integer programming approaches including branch-and-cut and branch-and-cut-and-price for the minimum label spanning tree problem as well as a variant of it having multiple labels assigned to each edge. We compare formulations based on network flows and directed connectivity cuts. Further, we show how to use odd-hole inequalities and additional inequalities to strengthen the formulation. Label variables can be added dynamically to the model in the pricing step. Primal heuristics are incorporated into the framework to speed up the overall solution process. After a polyhedral comparison of the involved formulations, comprehensive computational experiments are presented in order to compare and evaluate the underlying formulations and the particular algorithmic building blocks of the overall branch-and-cut- (and-price) framework.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

33

Timofeeva, A. Yu, und Yu A. Mezentsev. „Forecasting using predictor selection from a large set of highly correlated variables“. Information Technology and Nanotechnology, Nr. 2416 (2019): 10–18. http://dx.doi.org/10.18287/1613-0073-2019-2416-10-18.

Der volle Inhalt der Quelle

Annotation:

The potential of correlation-based feature selection has been explored in selecting an optimal subset from a set of highly correlated predictors. This problem occurs, for example, in time series forecasting of economic indicators using regression models on multiple lags of a large number of candidate leading indicators. Greedy algorithms (forward selection and backward elimination) in such cases fail. To obtain the globally optimal solution, the feature selection problem is formulated as a mixed integer programming problem. To solve it, we use the binary cut-and-branch method. The results of simulation studies demonstrate the advantage of using the binary cut-and-branch method in comparison with heuristic search algorithms. The real example of the selection of leading indicators of consumer price index growth shows the acceptability of using the correlation-based feature selection method.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

34

Rostami, Borzou, Guy Desaulniers, Fausto Errico und Andrea Lodi. „Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times“. Operations Research 69, Nr. 2 (März 2021): 436–55. http://dx.doi.org/10.1287/opre.2020.2037.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

35

Kobeaga, Gorka, María Merino und Jose A. Lozano. „On solving cycle problems with Branch-and-Cut: extending shrinking and exact subcycle elimination separation algorithms“. Annals of Operations Research 305, Nr. 1-2 (03.08.2021): 107–36. http://dx.doi.org/10.1007/s10479-021-04210-0.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

36

Armbruster, Michael, Marzena Fügenschuh, Christoph Helmberg und Alexander Martin. „LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison“. Mathematical Programming Computation 4, Nr. 3 (15.04.2012): 275–306. http://dx.doi.org/10.1007/s12532-012-0040-5.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

37

Cherkesly, Marilène, Guy Desaulniers, Stefan Irnich und Gilbert Laporte. „Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks“. European Journal of Operational Research 250, Nr. 3 (Mai 2016): 782–93. http://dx.doi.org/10.1016/j.ejor.2015.10.046.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

38

Costa, Alysson M., Jean-François Cordeau und Gilbert Laporte. „Models and branch-and-cut algorithms for the Steiner tree problem with revenues, budget and hop constraints“. Networks 53, Nr. 2 (17.12.2008): 141–59. http://dx.doi.org/10.1002/net.20274.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

39

Desaulniers, Guy, Timo Gschwind und Stefan Irnich. „Variable Fixing for Two-Arc Sequences in Branch-Price-and-Cut Algorithms on Path-Based Models“. Transportation Science 54, Nr. 5 (September 2020): 1170–88. http://dx.doi.org/10.1287/trsc.2020.0988.

Der volle Inhalt der Quelle

Annotation:

Variable fixing by reduced costs is a popular technique for accelerating the solution process of mixed-integer linear programs. For vehicle-routing problems solved by branch-price-and-cut algorithms, it is possible to fix to zero the variables associated with all routes containing at least one arc from a subset of arcs determined according to the dual solution of a linear relaxation. This is equivalent to removing these arcs from the network used to generate the routes. In this paper, we extend this technique to routes containing sequences of two arcs. Such sequences or their arcs cannot be removed directly from the network because routes traversing only one arc of a sequence might still be allowed. For some of the most common vehicle-routing problems, we show how this issue can be overcome by modifying the route-generation labeling algorithm in order to remove indirectly these sequences from the network. The proposed acceleration strategy is tested on benchmark instances of the vehicle-routing problem with time windows (VRPTW) and four variants of the electric VRPTW. The computational results show that it yields a significant speedup, especially for the most difficult instances.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

40

Ishida, Yusuke, Yuki Kato, Liang Zhao, Hiroshi Nagamochi und Tatsuya Akutsu. „Branch-and-Bound Algorithms for Enumerating Treelike Chemical Graphs with Given Path Frequency Using Detachment-Cut“. Journal of Chemical Information and Modeling 50, Nr. 5 (26.04.2010): 934–46. http://dx.doi.org/10.1021/ci900447z.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

41

Rahmani, Arsalan, und Majid Yousefikhoshbakht. „An Effective Branch-and-cut algorithm in Order to Solve the Mixed Integer Bi-level Programming“. International Journal of Production Management and Engineering 5, Nr. 1 (31.01.2017): 1. http://dx.doi.org/10.4995/ijpme.2017.6512.

Der volle Inhalt der Quelle

Annotation:

<p>In this paper, a new branch-and-cut algorithm for mixed integer bi-level programming is proposed. For achieving this purpose, a historical perspective of the development of enumeration methods in the field of bi-level linear programming is considered. Then, we present some obstacles for using branch and bound method based on them, and an algorithm is developed to solve for mixed integer bi-level problem. Finally, we use a preference function to determine the choice of branching and specialized cuts in a branch and cut tree. Computational results are reported and compared favorably to those of previous methods and then implications discussed. The results show that not only the proposed algorithm can find high quality solutions for solving a number of the problems, but also it is competitive with other famous published algorithms.</p>

APA, Harvard, Vancouver, ISO und andere Zitierweisen

42

De Oliveira, Willy Alves, und Maristela Oliveira dos Santos. „A New Branching Rule to Solve the Capacitated Lot Sizing and Scheduling Problem with Sequence Dependent Setups“. TEMA (São Carlos) 18, Nr. 3 (10.01.2018): 515. http://dx.doi.org/10.5540/tema.2017.018.03.515.

Der volle Inhalt der Quelle

Annotation:

In this paper, we deal with the Capacitated Lot Sizing and Scheduling Problem with sequencedependent setup times and costs - CLSD model. More specifically, we propose a simple reformulation for the CLSD model that enables us to define a new branching rule to be used in Branch-and-Bound (or Branch-and-Cut) algorithms to solve this NP-hard problem. Our branching rule can be easily implemented in commercial solvers. Computational tests performed in 240 test instances from the literature show that our approach can significantly reduce the running time to solve this problem using a Branch-and-Cut algorithm of a commercial MIP solver.Therefore, our approach can also improve the performance of other approaches that need to solve partial sub problems of the CLSD model in each iteration, such as Lagrangian approaches and heuristics based on the mathematical formulation of the problem.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

43

Qiu, Yuzhuo, Liang Wang, Xiaoling Xu, Xuanjing Fang und Panos M. Pardalos. „Formulations and branch-and-cut algorithms for multi-product multi-vehicle production routing problems with startup cost“. Expert Systems with Applications 98 (Mai 2018): 1–10. http://dx.doi.org/10.1016/j.eswa.2018.01.006.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

44

Pereira, Dilson Lucas, und Alexandre Salles da Cunha. „Polyhedral results, branch-and-cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem“. Networks 71, Nr. 1 (31.10.2017): 31–50. http://dx.doi.org/10.1002/net.21787.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

45

Vakhania, Nodari, und Frank Werner. „Branch Less, Cut More and Schedule Jobs with Release and Delivery Times on Uniform Machines“. Mathematics 9, Nr. 6 (16.03.2021): 633. http://dx.doi.org/10.3390/math9060633.

Der volle Inhalt der Quelle

Annotation:

We consider the problem of scheduling n jobs with identical processing times and given release as well as delivery times on m uniform machines. The goal is to minimize the makespan, i.e., the maximum full completion time of any job. This problem is well-known to have an open complexity status even if the number of jobs is fixed. We present a polynomial-time algorithm for the problem which is based on the earlier introduced algorithmic framework blesscmore (“branch less and cut more”). We extend the analysis of the so-called behavior alternatives developed earlier for the version of the problem with identical parallel machines and show how the earlier used technique for identical machines can be extended to the uniform machine environment if a special condition on the job parameters is imposed. The time complexity of the proposed algorithm is O(γm2nlogn), where γ can be either n or the maximum job delivery time qmax. This complexity can even be reduced further by using a smaller number κ<n in the estimation describing the number of jobs of particular types. However, this number κ becomes only known when the algorithm has terminated.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

46

Hashemi Doulabi, Hossein, Gilles Pesant und Louis-Martin Rousseau. „Vehicle Routing Problems with Synchronized Visits and Stochastic Travel and Service Times: Applications in Healthcare“. Transportation Science 54, Nr. 4 (Juli 2020): 1053–72. http://dx.doi.org/10.1287/trsc.2019.0956.

Der volle Inhalt der Quelle

Annotation:

This paper, for the first time, studies vehicle routing problems with synchronized visits (VRPS) and stochastic travel and service times. In addition to considering a home healthcare scheduling problem, we introduce an operating room scheduling problem with stochastic durations as a novel application of VRPS. We formulate VRPS with stochastic times as a two-stage stochastic integer programming model that, unlike the deterministic models in the VRPS literature, does not have any big-M constraints. This advantage comes at the cost of a large number of second-stage integer variables. We prove that the integrality constraints on second-stage variables can be relaxed, and therefore, we can apply the L-shaped algorithm and its branch-and-cut implementation to solve the problem. We enhance the model by developing valid inequalities and a lower bounding functional. We analyze the subproblems of the L-shaped algorithm and devise a specialized algorithm for them that is significantly faster than standard linear programming algorithms. Computational results show that the branch-and-cut algorithm optimally solves stochastic home healthcare scheduling instances with 15 patients and 10%–30% of synchronized visits. It also finds solutions with an average optimality gap of 3.57% for instances with 20 patients. Furthermore, the branch-and-cut algorithm optimally solves stochastic operating room scheduling problems with 20 surgeries.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

47

Bouzarth, Elizabeth L., Richard J. Forrester, Kevin R. Hutson, Rahul Isaac, James Midkiff, Danny Rivers und Leonard J. Testa. „A Comparison of Algorithms for Finding an Efficient Theme Park Tour“. Journal of Applied Mathematics 2018 (16.10.2018): 1–14. http://dx.doi.org/10.1155/2018/2453185.

Der volle Inhalt der Quelle

Annotation:

The problem of efficiently touring a theme park so as to minimize the amount of time spent in queues is an instance of the Traveling Salesman Problem with Time-Dependent Service Times (TSP-TS). In this paper, we present a mixed-integer linear programming formulation of the TSP-TS and describe a branch-and-cut algorithm based on this model. In addition, we develop a lower bound for the TSP-TS and describe two metaheuristic approaches for obtaining good quality solutions: a genetic algorithm and a tabu search algorithm. Using test instances motivated by actual theme park data, we conduct a computational study to compare the effectiveness of our algorithms.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

48

Cherkesly, Marilène, Guy Desaulniers und Gilbert Laporte. „Branch-Price-and-Cut Algorithms for the Pickup and Delivery Problem with Time Windows and Last-in-First-Out Loading“. Transportation Science 49, Nr. 4 (November 2015): 752–66. http://dx.doi.org/10.1287/trsc.2014.0535.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

49

Przybylski, Maciej. „AD*-Cut: A Search-Tree Cutting Anytime Dynamic A* Algorithm“. Proceedings of the International Conference on Automated Planning and Scheduling 28 (15.06.2018): 494–99. http://dx.doi.org/10.1609/icaps.v28i1.13925.

Der volle Inhalt der Quelle

Annotation:

This paper presents a new anytime incremental search algorithm, AD*-Cut. AD*-Cut is based on two algorithms, namely, Anytime Repairing A* (ARA*) and the novel incremental search algorithm, D* Extra Lite. D* Extra Lite reinitializes (cuts) entire search-tree branches that have been affected by changes in an environment, and D* Extra Lite appears to be quicker than the reinitialization during the search utilized by the popular incremental search algorithm, D* Lite. The search-tree branch cutting is a simple and robust technique that can be easily applied to ARA*. Consequently, AD*-Cut extends D* Extra Lite in the same manner, as the state-of-the-art Anytime D* (AD*) algorithm extends D* Lite. The benchmark results suggest that AD*-Cut is quicker and achieves shorter paths than AD* when used for path planning on 3D state-lattices (a 2D position with rotation).

APA, Harvard, Vancouver, ISO und andere Zitierweisen

50

Jin, Mingming, Jiongzhi Zheng und Kun He. „KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem“. Proceedings of the AAAI Conference on Artificial Intelligence 38, Nr. 18 (24.03.2024): 20735–42. http://dx.doi.org/10.1609/aaai.v38i18.30061.

Der volle Inhalt der Quelle

Annotation:

The Maximum k-Defective Clique Problem (MDCP) aims to find a maximum k-defective clique in a given graph, where a k-defective clique is a relaxation clique missing at most k edges. MDCP is NP-hard and finds many real-world applications in analyzing dense but not necessarily complete subgraphs. Exact algorithms for MDCP mainly follow the Branch-and-bound (BnB) framework, whose performance heavily depends on the quality of the upper bound on the cardinality of a maximum k-defective clique. The state-of-the-art BnB MDCP algorithms calculate the upper bound quickly but conservatively as they ignore many possible missing edges. In this paper, we propose a novel CoLoring-based Upper Bound (CLUB) that uses graph coloring techniques to detect independent sets so as to detect missing edges ignored by the previous methods. We then develop a new BnB algorithm for MDCP, called KD-Club, using CLUB in both the preprocessing stage for graph reduction and the BnB searching process for branch pruning. Extensive experiments show that KD-Club significantly outperforms state-of-the-art BnB MDCP algorithms on the number of solved instances within the cut-off time, having much smaller search tree and shorter solving time on various benchmarks.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Wir bieten Rabatte auf alle Premium-Pläne für Autoren, deren Werke in thematische Literatursammlungen aufgenommen wurden. Kontaktieren Sie uns, um einen einzigartigen Promo-Code zu erhalten!