This paper presents a novel hybrid approach for solving the Container Loading (CL) problem based on the combination of integer linear programming (lLP) and Genetic Algorithms (GAs). More precisely, a GA engine works a...
详细信息
ISBN:
(纸本)9783540716143
This paper presents a novel hybrid approach for solving the Container Loading (CL) problem based on the combination of integer linear programming (lLP) and Genetic Algorithms (GAs). More precisely, a GA engine works as a generator of reduced instances for the original CL problem, which are formulated as ILP models. These instances, in turn, are solved by an exact optimization technique (solver), and the performance measures accomplished by the respective models are interpreted as fitness values by the genetic algorithm, thus guiding its evolutionary process. Computational experiments performed on standard benchmark problems, as well as a practical case study developed in a metallurgic factory, are also reported and discussed here in a manner as to testify the potentialities behind the novel approach.
The explosive growth of Internet traffic driven by the rise and popularity of bandwidth-intensive services such as virtual realities, big data exchanges and artificial intelligence necessitates for a re-consideration ...
详细信息
ISBN:
(纸本)9781728123929
The explosive growth of Internet traffic driven by the rise and popularity of bandwidth-intensive services such as virtual realities, big data exchanges and artificial intelligence necessitates for a re-consideration of optical transport networks toward greater capital and operational efficiency from both designing, planning and management perspectives. Thanks to mainly the significant advances in transmission technologies and reconfigurable optical add/drop multiplexers, transparent (all-optical) core networks with wavelength-division multiplexing (WDM) technologies have been well-adopted by network operators as costly optical-electrical-optical interfaces are eliminated together with the merit of scalable upgrade. Efficient designing of such transparent networks therefore has been of ever-growing importance as the spectrum capacity has to be optimized while maintaining the efficiency of operations. Conventional approaches based on integer linear programming formulations and/or heuristic algorithms have nevertheless been focused on optimizing a single metric, i.e., wavelength count or wavelength link usage, and doing so possibly poses penalties to the remaining objectives. In addressing this issue, this paper presents a new integer linear programming formulation incorporating both two performance metrics into consideration with an integrated objective function. We then introduce a framework for analyzing and properly setting up the weight coefficients of integrated objective function so as to guarantee the order of optimization. Extensive numerical studies on realistic topologies highlight the effectiveness of our proposal compared to conventional designs based on single objective formulation in the literature.
Multiplier is an important arithmetic circuit. State-of-the-art designs consist of a partial product generator (PPG), a compressor tree (CT), and a carry propagation adder (CPA), with the last two components dominatin...
详细信息
ISBN:
(纸本)9783981926354
Multiplier is an important arithmetic circuit. State-of-the-art designs consist of a partial product generator (PPG), a compressor tree (CT), and a carry propagation adder (CPA), with the last two components dominating the area and delay. Existing representative works optimize the CT and the CPA separately, adding a rigid boundary between these two components. In this paper, we break the boundary by proposing GOMIL, a global optimization for multiplier by integer linear programming. Two ILP sub-problems are first formulated to optimize the CT and the prefix structure in the CPA, respectively. Then, they are unified to provide a global optimization to the multiplier. The proposed method is applicable to not only multipliers with the AND gate-based PPG, but also those with Booth encoding-based PPG. The experimental results showed that the multipliers optimized by GOMIL can reduce the power-delay product by up to 71%, compared to the state-of-the-art multipliers developed in industry. The code of GOMIL is made open-source.
The trend toward server-side computing and the exploding popularity of Internet services due to the increasing of demand for networking, storage and computation has created a world-wild energetic problem and a signifi...
详细信息
ISBN:
(纸本)9781728154169
The trend toward server-side computing and the exploding popularity of Internet services due to the increasing of demand for networking, storage and computation has created a world-wild energetic problem and a significant carbon footprint. These environmental concerns prompt to several green energy initiative aiming either to increase data center efficiency and/or to the use of green energy supply. In this regard, As part of the ANR DATAZERO project, many researchers are working to define main concepts of an autonomous green data center only powered by renewable energies. Thus, the present paper proposes a mixed integerlinear program to optimize the commitment of a hybrid energy system composed of wind turbines, solar panels, batteries and hydrogen storage systems. The approach is used to supply a data center demand and takes the weather forecasts into account at the time of optimization. Different time window resolution are applied in order to verify the best time window for decision making.
Triple Graph Grammars (TGGs) are a declarative and rulebased approach to bidirectional model transformation. The key feature of TGGs is the automatic derivation of various operations such as unidirectional transformat...
详细信息
ISBN:
(纸本)9783030452346;9783030452339
Triple Graph Grammars (TGGs) are a declarative and rulebased approach to bidirectional model transformation. The key feature of TGGs is the automatic derivation of various operations such as unidirectional transformation, model synchronisation, and consistency checking. Application conditions can be used to increase the expressiveness of TGGs by guaranteeing schema compliance, i.e., that domain constraints are respected by the TGG. In recent years, a series of new TGG-based operations has been introduced leveraging integer linear programming (ILP) solvers to flexible consistency maintenance even in cases where no strict solution exists. Schema compliance is not guaranteed, however, as application conditions from the original TGG cannot be directly transferred to these ILP-based operations. In this paper, we extend ILP-based TGG operations so as to guarantee schema compliance. We implement and evaluate the practical feasibility of our approach.
Automatic single-document summarization is a process that receives a single input document and outputs a condensed version with only the most relevant information. This paper proposes an unsupervised concept-based app...
详细信息
ISBN:
(纸本)9781509035663
Automatic single-document summarization is a process that receives a single input document and outputs a condensed version with only the most relevant information. This paper proposes an unsupervised concept-based approach for single-document summarization using integer linear programming (ILP). Such an approach maximizes the coverage of the important concepts in the summary, avoiding redundancy, and taking into consideration some readability aspects of the generated summary as well. A new weighting method that combines both coverage and position of the sentences is proposed to estimate the importance of a concept. Moreover, a weighted distribution strategy that prioritizes sentences at the beginning of the document if they have relevant concepts is investigated. The readability of the generated summaries is improved by the inclusion of constraints into the ILP model to avoid dangling coreferences and breaks in the normal discourse flow of the document. Experimental results on the DUC 2001-2002 and the CNN corpora demonstrated that the proposed approach is competitive with state-of-the-art summarizers evaluated regarding the traditional ROUGE scores.
Dedicated machine constraint is one of the new challenges introduced in photolithography machinery of the semiconductor manufacturing system due to natural bias. Previous researches either did not take the constraint ...
详细信息
ISBN:
(纸本)9780769531311
Dedicated machine constraint is one of the new challenges introduced in photolithography machinery of the semiconductor manufacturing system due to natural bias. Previous researches either did not take the constraint into account or the proposed heuristic approach might not fit the fast-changing market of semiconductor manufacturing. In this paper, we propose a new framework for the issue of the dedicated machine constraint in semiconductor manufacturing based on an integerlinear Program (ILP) framework. The ILP framework provides an efficient approach to minimize the producing cost and obtain a global optimal solution in an efficient time. We also present the experiments to validate the proposed approach.
We transform join ordering into a mixed integerlinear program (MILP). This allows to address query optimization by mature MILP solver implementations that have evolved over decades and steadily improved their perform...
详细信息
ISBN:
(纸本)9781450341974
We transform join ordering into a mixed integerlinear program (MILP). This allows to address query optimization by mature MILP solver implementations that have evolved over decades and steadily improved their performance. They offer features such as anytime optimization and parallel search that are highly relevant for query optimization. We present a MILP formulation for searching left-deep query plans. We use sets of binary variables to represent join operands and intermediate results, operator implementation choices or the presence of interesting orders. linear constraints restrict value assignments to the ones representing valid query plans. We approximate the cost of scan and join operations via linear functions, allowing to increase approximation precision up to arbitrary degrees. We integrated a prototypical implementation of our approach into the Postgres optimizer and compare against the original optimizer and several variants. Our experimental results are encouraging: we are able to optimize queries joining 40 tables within less than one minute of optimization time. Such query sizes are far beyond the capabilities of traditional query optimization algorithms with worst case guarantees on plan quality. Furthermore, as we use an existing solver, our optimizer implementation is small and can be integrated with low overhead.
This paper describes a parallel branch‐and‐bound algorithm for general integer linear programming problems and its implementation on a distributed memory multiprocessor nCUBE2. With a branch‐and‐bound algorithm, t...
详细信息
暂无评论