Wyniki wyszukiwania - BazTech

Ograniczanie wyników

4 Annals of Computer Science and Information Systems

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: programowanie liczb całkowitych

Sortuj według:

Ogranicz wyniki do:

Pipe-lining Dynamic Programming Processes in Order to Synchronize Energy Production and Consumption

Bendali Fariha, Quilliot Alain, Mole Kamga Eloise, Mailfert Jean, Toussaint Hélène

Annals of Computer Science and Information Systems

2020

Vol. 21

303--306

Synchronizing heterogeneous processes remains a difficult issue in Scheduling area. Related ILP models are in trouble, because of large gaps induced by rational relaxation. We propose here a pipe-line decomposition of a dynamic programming process for energy production and consumption scheduling, and describe the way related sub-processes interact in order to achieve efficient synchronization.

An Experimental Study on Symmetry Breaking Constraints Impact for the One Dimensional Bin-Packing Problem

Hadj Salem Khadija, Kieffer Yann

Annals of Computer Science and Information Systems

2020

Vol. 21

317--326

We consider the classical One-Dimensional Bin Packing Problem (1D-BPP), an NP-hard optimization problem, where, a set of weighted items has to be packed into one or more identical capacitated bins. We give an experimental study on using symmetry breaking constraints for strengthening the classical integer linear programming proposed to optimally solve this problem. Our computational experiments are conducted on the data-set found in BPPLib and the results have confirmed the theoretical results.

A novel integer linear programming model for routing and spectrum assignment in optical networks

Hadhbi Youssouf, Kerivin Hervé, Wagler Annegret

Annals of Computer Science and Information Systems

2019

Vol. 18

127--134

The routing and spectrum assignment problem is an NP-hard problem that receives increasing attention during the last years. Existing integer linear programming models for the problem are either very complex and suffer from tractability issues or are simplified and incomplete so that they can optimize only some objective functions. The majority of models uses edge-path formulations where variables are associated with all possible routing paths so that the number of variables grows exponentially with the size of the instance. An alternative is to use edge-node formulations that allow to devise compact models where the number of variables grows only polynomially with the size of the instance. However, all known edge-node formulations are incomplete as their feasible region is a superset of all feasible solutions of the problem and can, thus, handle only some objective functions. Our contribution is to provide the first complete edge-node formulation for the routing and spectrum assignment problem which leads to a tractable integer linear programming model. Indeed, computational results show that our complete model is competitive with incomplete models as we can solve instances of the RSA problem larger than instances known in the literature to optimality within reasonable time and w.r.t. several objective functions. We further devise some directions of future research.

A Minimum set-cover problem with several constraints

Dörpinghaus Jens, Düing Carsten, Weil Vera

Annals of Computer Science and Information Systems

2019

Vol. 18

115--122

A lot of problems in natural language processing can be interpreted using structures from discrete mathematics. In this paper we will discuss the search query and topic finding problem using a generic context-based approach. This problem can be described as a a Minimum Set Cover Problem with several constraints. The goal is to find a minimum covering of documents with the given context for a fixed weight function. The aim of this problem reformulation is a deeper understanding of both the hierarchical problem using union and cut as well as the non-hierarchical problem using the union. We thus choose a modeling using bipartite graphs and suggest a novel reformulation using an integer linear program as well as novel graph-theoretic approaches.