Page 1 Next

Displaying 1 – 20 of 167

Showing per page

A branch&bound algorithm for solving one-dimensional cutting stock problems exactly

Guntram Scheithauer, Johannes Terno (1995)

Applicationes Mathematicae

Many numerical computations reported in the literature show only a small difference between the optimal value of the one-dimensional cutting stock problem (1CSP) and that of the corresponding linear programming relaxation. Moreover, theoretical investigations have proven that this difference is smaller than 2 for a wide range of subproblems of the general 1CSP.

A branch-and-cut algorithm for a resource-constrained scheduling problem

Renaud Sirdey, Hervé L. M. Kerivin (2007)

RAIRO - Operations Research

This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high-availability real-time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process move programs, we present a branch-and-cut algorithm along with extensive computational results demonstrating its practical relevance,...

A branch-and-cut for the Non-Disjoint m-Ring-Star Problem

Pierre Fouilhoux, Aurélien Questel (2014)

RAIRO - Operations Research - Recherche Opérationnelle

In this article we study the realistic network topology of Synchronous Digital Hierarchy (SDH) networks. We describe how providers fulfill customer connectivity requirements. We show that SDH Network design reduces to the Non-Disjoint m-Ring-Star Problem (NDRSP). We first show that there is no two-index integer formulation for this problem. We then present a natural 3-index formulation for the NDRSP together with some classes of valid inequalities that are used as cutting planes in a Branch-and-Cut...

A branch-and-price algorithm for the windy rural postman problem

Hasan Murat Afsar, Nicolas Jozefowiez, Pierre Lopez (2012)

RAIRO - Operations Research

In this paper, we propose an exact solution method for the windy rural postman problem (WRPP). The motivation to study this problem comes from some real-life applications, such as garbage collecting in a predefined sector with hills, where the traversing or the servicing speed can change following the direction. We present a Dantzig-Wolfe decomposition and a branch-and-price algorithm to solve the WRPP. To the best of our knowledge, Dantzig-Wolfe decomposition has never been used to solve that problem....

A branch-and-price-and-cut algorithm for the pattern minimization problem

Cláudio Alves, J. M. Valério de Carvalho (2008)

RAIRO - Operations Research - Recherche Opérationnelle

In cutting stock problems, after an optimal (minimal stock usage) cutting plan has been devised, one might want to further reduce the operational costs by minimizing the number of setups. A setup operation occurs each time a different cutting pattern begins to be produced. The related optimization problem is known as the Pattern Minimization Problem, and it is particularly hard to solve exactly. In this paper, we present different techniques to strengthen a formulation proposed in the literature....

A branch-and-price-and-cut algorithm for the pattern minimization problem

Cláudio Alves, J.M. Valério de Carvalho (2009)

RAIRO - Operations Research

In cutting stock problems, after an optimal (minimal stock usage) cutting plan has been devised, one might want to further reduce the operational costs by minimizing the number of setups. A setup operation occurs each time a different cutting pattern begins to be produced. The related optimization problem is known as the Pattern Minimization Problem, and it is particularly hard to solve exactly. In this paper, we present different techniques to strengthen a formulation proposed in the literature....

A geometrical method in combinatorial complexity

Jaroslav Morávek (1981)

Aplikace matematiky

A lower bound for the number of comparisons is obtained, required by a computational problem of classification of an arbitrarily chosen point of the Euclidean space with respect to a given finite family of polyhedral (non-convex, in general) sets, covering the space. This lower bound depends, roughly speaking, on the minimum number of convex parts, into which one can decompose these polyhedral sets. The lower bound is then applied to the knapsack problem.

A Hybrid Approach Combining Local Search and Constraint Programming for a Large Scale Energy Management Problem

Haris Gavranović, Mirsad Buljubašić (2013)

RAIRO - Operations Research - Recherche Opérationnelle

This paper presents a heuristic approach combining constraint satisfaction, local search and a constructive optimization algorithm for a large-scale energy management and maintenance scheduling problem. The methodology shows how to successfully combine and orchestrate different types of algorithms and to produce competitive results. We also propose an efficient way to scale the method for huge instances. A large part of the presented work was done to compete in the ROADEF/EURO Challenge 2010, organized...

A note on the Chvátal-rank of clique family inequalities

Arnaud Pêcher, Annegret K. Wagler (2007)

RAIRO - Operations Research


Clique family inequalities a∑v∈W xv + (a - 1)∈v∈W, xv ≤ aδ form an intriguing class of valid inequalities for the stable set polytopes of all graphs. We prove firstly that their Chvátal-rank is at most a, which provides an alternative proof for the validity of clique family inequalities, involving only standard rounding arguments. Secondly, we strengthen the upper bound further and discuss consequences regarding the Chvátal-rank of subclasses of claw-free graphs.


Currently displaying 1 – 20 of 167

Page 1 Next