Displaying similar documents to “A branch-and-price algorithm for the windy rural postman problem”

Variable Neighborhood Search for Solving the Capacitated Single Allocation Hub Location Problem

Maric, Miroslav (2013)

Serdica Journal of Computing

Similarity:

In this paper a Variable Neighborhood Search (VNS) algorithm for solving the Capacitated Single Allocation Hub Location Problem (CSAHLP) is presented. CSAHLP consists of two subproblems; the first is choosing a set of hubs from all nodes in a network, while the other comprises finding the optimal allocation of non-hubs to hubs when a set of hubs is already known. The VNS algorithm was used for the first subproblem, while the CPLEX solver was used for the second. Computational results...

Warm-start cuts for Generalized Benders Decomposition

Jakub Kůdela, Pavel Popela (2017)

Kybernetika

Similarity:

In this paper, we describe a decomposition algorithm suitable for two-stage convex stochastic programs known as Generalized Benders Decomposition. For this algorithm we propose a new reformulation that incorporates a lower bound cut that serves as a warm-start, decreasing the overall computation time. Additionally, we test the performance of the proposed reformulation on two modifications of the algorithm (bunching and multicut) using numerical examples. The numerical part is programmed...

Close-to-optimal algorithm for rectangular decomposition of 3D shapes

Cyril Höschl IV, Jan Flusser (2019)

Kybernetika

Similarity:

In this paper, we propose a novel algorithm for a decomposition of 3D binary shapes to rectangular blocks. The aim is to minimize the number of blocks. Theoretically optimal brute-force algorithm is known to be NP-hard and practically infeasible. We introduce its sub-optimal polynomial heuristic approximation, which transforms the decomposition problem onto a graph-theoretical problem. We compare its performance with the state of the art Octree and Delta methods. We show by extensive...

A new algorithm for optimal solution of fixed charge transportation problem

Nermin Kartli, Erkan Bostanci, Mehmet Serdar Guzel (2023)

Kybernetika

Similarity:

Fixed charge transportation problem (FCTP) is a supply chain problem. In this problem, in addition to the cost per unit for each transported product, a fixed cost is also required. The aim is to carry out the transportation process at the lowest possible cost. As with all supply chain problems, this problem may have one, two, or three stages. An algorithm that can find the optimal solution for the problem in polynomial time is not known, even if it is a single-stage problem. For this...

Evaluating the Kernighan-Lin heuristic for hardware/software partitioning

Zoltán Mann, András Orbán, Viktor Farkas (2007)

International Journal of Applied Mathematics and Computer Science

Similarity:

In recent years, several heuristics have been proposed for the hardware/software partitioning problem. One of the most promising directions is the adaptation of the Kernighan-Lin algorithm. The Kernighan-Lin heuristic was originally developed for circuit partitioning, but it has been adapted to other domains as well. Moreover, numerous improvements have been suggested so that now several variants of the original algorithm exist. The aim of this paper is to systematically evaluate the...

An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem

Peng Wuliang, Huang Min, Hao Yongping (2014)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Many real-world scheduling problems can be modeled as Multi-mode Resource Constrained Project Scheduling Problems (MRCPSP). However, the MRCPSP is a strong NP-hard problem and very difficult to be solved. The purpose of this research is to investigate a more efficient alternative based on ant algorithm to solve MRCPSP. To enhance the generality along with efficiency of the algorithm, the rule pool is designed to manage numerous priority rules for MRCPSP. Each ant is provided with an...