检索结果-内蒙古大学图书馆

integer linear programming models for 2-staged two-dimensional Knapsack problems

MATHEMATICAL programming 2003年第2-3期94卷 257-278页

作者： Lodi, A Monaci, M Univ Bologna Dipartimento Elettron Informat & Sistemist I-40136 Bologna Italy

We are given a unique rectangular piece of stock material S, with height H and width W, and a list of in rectangular shapes to be cut from S. Each shape's type i (i = l,....,in) is characterized by a height (h) over bar (i), a width (w) over bar (i), a profit (p) over bar (i), and an upper bound ub(i) indicating the maximum number of items of type i which can be cut. We refer to the Two-Dimensional Knapsack (TDK) as the problem of determining a cutting pattern of S maximizing the sum of the profits of the cut items. In particular, we consider the classical variant of TDK in which the maximum number of cuts allowed to obtain each item is fixed to 2. and we refer to this problem as 2-staged TDK (2TDK). For the 2TDK problem we present two new integer linear programming models, we discuss their properties, and we compare them with other formulations in terms of the LP bound they provide. Finally, both models are computationally tested within a standard branch-and-bound framework on a large set of instances from the literature by reinforcing them with the addition of linear inequalities to eliminate symmetries.

关键词： packing cutting integer linear programming

来源：评论

学校读者我要写书评

暂无评论

integer linear programming model for multidimensional two-way number partitioning problem

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2010年第8期60卷 2302-2308页

作者： Kojic, Jelena Univ Belgrade Fac Math Belgrade 11000 Serbia

This paper introduces a multidimensional generalization of the two-way number partitioning problem, as well as an integer linear programming formulation of the problem. There are n binary variables and 2p constraints. The numerical experiments are made on a randomly generated set. In view of its integer linear programming formulation, tests are run in CPLEX. This NP-hard problem uses a set of vectors rather than a set of numbers. The presented experimental results indicate that the generalized problem is much harder than the initial problem. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Number partitioning integer linear programming Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

integer linear programming approaches for non-unique probe selection

引用

DISCRETE APPLIED MATHEMATICS 2007年第6-7期155卷 840-856页

作者： Klau, Gunnar W. Rahmann, Sven Schliep, Alexander Vingron, Martin Reinert, Knut Free Univ Berlin D-14195 Berlin Germany DFG Res Ctr MATHEON Math Key Technol Berlin Germany Univ Bielefeld Tech Fak D-33594 Bielefeld Germany Max Planck Inst Mol Genet D-14195 Berlin Germany Free Univ Berlin D-14195 Berlin Germany

In addition to their prevalent use for analyzing gene expression, DNA microarrays are an efficient tool for biological, medical, and industrial applications because of their ability to assess the presence or absence of biological agents, the targets, in a sample. Given a collection of genetic sequences of targets one faces the challenge of finding short oligonucleotides, the probes, which allow detection of targets in a sample by hybridization experiments. The experiments are conducted using either unique or non-unique probes, and the problem at hand is to compute a minimal design, i.e., a minimal set of probes that allows to infer the targets in the sample from the hybridization results. If we allow to test for more than one target in the sample, the design of the probe set becomes difficult in the case of non-unique probes. Building upon previous work on group testing for microarrays we describe the first approach to select a minimal probe set for the case of non-unique probes in the presence of a small number of multiple targets in the sample. The approach is based on an integer linear programming formulation and a branch-and-cut algorithm. Our implementation significantly reduces the number of probes needed while preserving the decoding capabilities of existing approaches. (c) 2006 Elsevier B.V. All rights reserved.

关键词： integer linear programming microarray probe oligonucleotide design group testing

来源：评论

学校读者我要写书评

暂无评论

Decision support system for tower crane location and material supply point in construction sites using an integer linear programming model

引用

ENGINEERING CONSTRUCTION AND ARCHITECTURAL MANAGEMENT 2023年第4期30卷 1444-1462页

作者： Amiri, Roya Sardroud, Javad Majrouhi Kermani, Vahid Momenaei Islamic Azad Univ Fac Civil & Earth Resources Engn Dept Civil Engn Cent Tehran Branch Tehran Iran Islamic Azad Univ Dept Math Kerman Branch Kerman Iran

Purpose The site layout has a significant impact on the efficiency of construction operations. Planning an effective site layout partly involves identifying and positioning temporary facilities such as tower cranes and areas on the jobsite for materials storage. This study proposes an approach to optimizing the type and location of the tower crane and material supply point on construction sites. Design/methodology/approach The problem is formulated into an integer linear programming (ILP) model considering the total cost of material transportation as the objective function and site conditions as constraints. The efficacy of the approach is demonstrated by finding the optimum site layout for a numerical example. The proposed model is validated and verified using two methods. Findings Results indicate that the proposed model successfully identifies the type and location of the tower crane and the location of material supply point, leading to approximately 20% cost reduction compared with when such features of a site layout are decided solely based on experience and educated guesses of the construction manager. Originality/value The primary contribution of this study is to present a modified linear mathematical model for site layout optimization that exhibits improved performance compared with previous models. The type and location of the tower crane and the material supply point as decision variables are extracted directly from solving the proposed model. The proposed model will help enhance time and cost efficiency on construction sites.

关键词： Decision making Tower crane Material supply point Optimization integer linear programming Construction site

来源：评论

学校读者我要写书评

暂无评论

integer linear programming Formulations for the RCPSP considering Multi-Skill, Multi-Mode, and Minimum and Maximum Time Lags

引用

IEEE LATIN AMERICA TRANSACTIONS 2021年第1期19卷 5-16页

作者： Melo, Luciana Vieira Queiroz, Thiago Alves Univ Fed Goias Reg Catalao Programa Posgrad Engn Prod BR-75708560 Catalao Goias Brazil

The project scheduling problem is essential both in the theoretical part, as in the field of operational research, and practice, with the project management in corporate environments. integer linear programming formulations indexed on time are studied for the Resource-Constrained Project Scheduling Problem (RCPSP). Moreover, the multi-skill, multiple modes, and time lag constraints are taken into consideration. The objective of the RCPSP is to minimize the makespan. The formulations are solved with the default branch-and-cut algorithm of the solver Gurobi Optimizer. The formulations and solver are analyzed concerning the runtime, the number of optimal solutions, and the gap on the resolution of more than 2000 instances. Results indicate the solver can have better performance when instances with up to 50 activities are solved. Then, to develop models to handle hard instances of this problem is a challenge. Moreover, it can bring significant advantages to the corporate environment, helping managers to make accurate decisions and reduce costs.

关键词： Computational modeling Scheduling Optimal scheduling integer linear programming Mathematical model IEEE transactions Software Mathematical model Optimal scheduling Optimization

来源：评论

学校读者我要写书评

暂无评论

integer linear programming-Based Simultaneous Scheduling and Binding for SiLago Framework

引用

IEEE ACCESS 2024年 12卷 124081-124094页

作者： Pudi, Dhilleswararao Malviya, Shivam Boppu, Srinivas Yang, Yu Hemani, Ahmed Cenkeramaddi, Linga Reddy Indian Inst Technol Bhubaneswar Sch Elect Sci Bhubaneswar 752050 India KTH Royal Inst Technol Div Elect & Embedded Syst Stockholm S-11428 Sweden Univ Agder Dept ICT N-4630 Grimstad Norway

Coarse-Grained Reconfigurable Array (CGRA) architectures are potential high-performance and power-efficient platforms. However, mapping applications efficiently on CGRA, which includes scheduling and binding operations on functional units and variables on registers, is a daunting problem. SiLago is a recently developed VLSI design framework comprising two large-scale reconfigurable fabrics: Dynamically Reconfigurable Resource Array (DRRA) and Distributed Memory Architecture (DiMArch). It uses the Vesyla compiler to map applications on these fabrics. The present version of Vesyla executes binding and scheduling sequentially, with binding first, followed by scheduling. In this paper, we proposed an integer linear programming (ILP)-based exact method to solve scheduling and binding simultaneously that delivers better solutions while mapping applications on these fabrics. The proposed ILP combines two objective functions, one for scheduling and one for binding, and both of these objective functions are coupled with weightage factors $\alpha $ and $\beta $ so that the user can have the flexibility to prioritize either scheduling or binding or both based on the requirements. We determined the binding and execution time of image processing tasks and various routines of the Basic linear Algebraic Subprogram (BLAS) using the proposed ILP for multiple combinations of weightage factors. Furthermore, a comparison analysis has been conducted to compare the latency and power dissipation of several benchmarks between the existing and proposed approaches. The experimental results demonstrate that the proposed method exhibits a substantial reduction in power consumption and latency compared to the existing method.

关键词： Random access memory Radio frequency Registers Switches Dynamic scheduling Reconfigurable architectures Distributed management Memory management integer linear programming Scheduling Power demand Coarse-grain reconfigurable architecture dynamically reconfigurable resource array distributed memory architecture integer linear programming high-level synthesis scheduling binding

来源：评论

学校读者我要写书评

暂无评论

integer linear programming-based cost optimization for scheduling scientific workflows in multi-cloud environments

引用

JOURNAL OF SUPERCOMPUTING 2018年第9期74卷 4717-4745页

作者： Mohammadi, Somayeh Pedram, Hossein PourKarimi, Latif Islamic Azad Univ Dept Comp Engn Sci & Res Branch Tehran Iran Amirkabir Univ Technol Dept Comp Engn Tehran Iran Razi Univ Dept Math Kermanshah Iran

Given that multi-cloud environments contain considerably diverse resources, scheduling workflows in these environments significantly reduces financial costs and overcomes the resource limitations imposed by commercial cloud providers. Accordingly, this study addressed the problem of scientific workflow scheduling in multi-cloud settings under deadline constraint to minimize associated financial costs. To this end, we proposed integer linear programming models that can be solved in a reasonable time by available solvers. In a mathematical model, the objective of a problem and real and physical constraints or restrictions are formulated using exact mathematical functions. Such formulation enabled us to comprehensively understand the system under evaluation, consider secondary preferences and post-optimality analysis and apply useful revisions to inappropriately selected input data. We analyzed the treatment of optimal cost under variations in deadline and workflow size. As part of the post-optimality analysis, sensitivity analysis and deadline revision were implemented. Results indicated that our proposed approach outperforms previously developed methods in terms of financial cost reduction.

关键词： Multi-cloud Scheduling Scientific workflow integer linear programming Cost minimization

来源：评论

学校读者我要写书评

暂无评论

integer linear programming formulation of the vehicle positioning problem in automated manufacturing systems

引用

JOURNAL OF INTELLIGENT MANUFACTURING 2011年第4期22卷 545-552页

作者： Montoya-Torres, Jairo R. Onate Bello, Gonzalo Univ La Sabana Escuela Int Ciencias Econ & Adm Chia Cundinamarca Colombia

This paper addresses the problem of vehicle location (positioning) for automated transport in fully automated manufacturing systems. This study is motivated by the complexity of vehicle control found in modern integrated circuit semiconductor fabrication facilities where the material handling network path is composed of multiple loops interconnected. In order to contribute to decrease the manufacturing lead-time of semiconductor products, we propose an integer linear program that minimizes the maximum time needed to serve a transport request. Computation experiments are based on real-life data. We discuss the practical usefulness of the mathematical model by means of a simulation experiment used to analyze the factory operational behavior.

关键词： Vehicle location integer linear programming Automated manufacturing IC semiconductors Simulation

来源：评论

学校读者我要写书评

暂无评论

integer linear programming-Based Bit-Level Optimization for High-Speed FIR Decimation Filter Architectures

引用

CIRCUITS SYSTEMS AND SIGNAL PROCESSING 2010年第1期29卷 81-101页

作者： Blad, Anton Gustafsson, Oscar Linkoping Univ Dept Elect Engn S-58183 Linkoping Sweden

Analog-to-digital converters based on sigma-delta modulation have shown promising performance, with steadily increasing bandwidth. However, associated with the increasing bandwidth is an increasing modulator sampling rate, which becomes costly to decimate in the digital domain. Several architectures exist for the digital decimation filter, and among the more common and efficient are polyphase decomposed finite-length impulse response (FIR) filter structures. In this paper, we consider such filters implemented with partial product generation for the multiplications, and carry-save adders to merge the partial products. The focus is on the efficient pipelined reduction of the partial products, which is done using a bit-level optimization algorithm for the tree design. However, the method is not limited only to filter design, but may also be used in other applications where high-speed reduction of partial products is required. The presentation of the reduction method is carried out through a comparison between the main architectural choices for FIR filters: the direct-form and transposed direct-form structures. For the direct-form structure, usage of symmetry adders for linear-phase filters is investigated, and a new scheme utilizing partial symmetry adders is introduced. The optimization results are complemented with energy dissipation and cell area estimations for a 90 nm CMOS process.

关键词： FIR Polyphase Sigma-delta CIC Optimization integer linear programming Decimation Digital filter Carry-save

来源：评论

学校读者我要写书评

暂无评论

integer linear programming for the Bayesian network structure learning problem

引用

ARTIFICIAL INTELLIGENCE 2017年 244卷 258-271页

作者： Bartlett, Mark Cussens, James Univ York Dept Comp Sci York N Yorkshire England

Bayesian networks are a commonly used method of representing conditional probability relationships between a set of variables in the form of a directed acyclic graph (DAG). Determination of the DAG which best explains observed data is an NP-hard problem [1]. This problem can be stated as a constrained optimisation problem using integer linear programming (ILP). This paper explores how the performance of ILP-based Bayesian network learning can be improved through ILP techniques and in particular through the addition of non-essential, implied constraints. There are exponentially many such constraints that can be added to the problem. This paper explores how these constraints may best be generated and added as needed. The results show that using these constraints in the best discovered configuration can lead to a significant improvement in performance and show significant improvement in speed using a state-of-the-art Bayesian network structure learner. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Bayesian networks integer linear programming Constrained optimisation Cutting planes Separation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：