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

Tabu Search-Based Heuristic Solver for General integer linear programming Problems

IEEE ACCESS 2024年 12卷 19059-19076页

作者： Koguma, Yuji Independent Researcher Kanagawa Japan

This paper presents a tabu search-based heuristic solver for general integer linear programming (ILP) problems as a dependable alternative to branch-and-bound (B&B) solvers. It aims to expand the range of ILP instances for which optimization practitioners can obtain reasonable solutions using either B&B or heuristic solvers. The challenge in developing such a heuristic solver is ensuring both good performance and versatility. The proposed solver addresses this difficulty by incorporating several performance-improving techniques for search behavior and computation speed while maintaining the versatility. These techniques include instance size reduction, neighborhood filtering, and accelerating solution evaluation. The proposed algorithm was implemented in C++17 and made available as an open-source solver that accepts ILP instances formulated for B&B solvers without modification. In numerical experiments with a 120-second time limit, the proposed solver found better feasible solutions than existing open-source B&B solvers for 17 out of the 82 feasible pure integer instances from MIPLIB 2017 Benchmark Set, including instances with over 100,000 variables. An ablation study verified that the incorporated techniques were essential for the performance.

关键词： Search problems Metaheuristics integer linear programming Indexes Behavioral sciences Heuristic algorithms Simulated annealing heuristics metaheuristics tabu search local search

来源：评论

学校读者我要写书评

暂无评论

Design of experiments and integer linear programming-assisted conjugate-gradient optimisation of high-κ/metal-gate nano-complementary metal-oxide semiconductor static random access memory

引用

IET COMPUTERS AND DIGITAL TECHNIQUES 2012年第4期6卷 240-248页

作者： Mohanty, S. P. Kougianos, E. Univ N Texas NanoSyst Design Lab Comp Sci & Engn Denton TX 76203 USA

Low-power consumption and stability in static random access memories (SRAMs) is essential for embedded applications. This study presents a novel design flow for power minimisation of nano-complementary metal-oxide semiconductor SRAMs, while maintaining stability. A 32 nm high-kappa/metal-gate SRAM has been used as an example circuit. The baseline circuit is subjected to power minimisation using a dual-threshold voltage assignment based on novel combined design of experiments and integer linear programming (DOE-ILP) approach. However, this leads to a 15% reduction in the static noise margin (SNM) of the cell. The conjugate gradient optimisation overcomes this SNM degradation, while reducing the power consumption. The final SRAM design shows 86% reduction in power consumption (including leakage) and 8% increase in the SNM compared with the baseline design. The variability analysis of the optimised cell is performed by considering the effect of 12 parameters. SRAM arrays of different sizes are constructed to demonstrate the feasibility of the proposed SRAM cell. To the best of the authors' knowledge, this is the first study which makes use of DOE-ILP and conjugate gradient method for simultaneous stability and power optimisation in high-kappa/metal-gate SRAM circuits.

关键词： linear programming SNM Optimisation techniques static random access memories integer linear programming Semiconductor storage gradient methods Memory circuits integer programming power consumption dual threshold voltage SRAM conjugate gradient optimisation high-κ/metal-gate nano-complementary metal-oxide semiconductor static random access memory static noise margin power minimisation baseline circuit SRAM chips

来源：评论

学校读者我要写书评

暂无评论

On solving the 1+1 routing, wavelength and network coding assignment problem with a bi-objective integer linear programming model

引用

TELECOMMUNICATION SYSTEMS 2019年第2期71卷 155-165页

作者： Dao Thanh Hai Hanoi Univ Ind Inst Technol Hanoi Vietnam

Network coding techniques have been viewed as the promising venue to improve the network efficiency and indeed, have been widely explored in the realm of failure recovery in optical networks. The combination of near-instantaneous recovery achieved by dedicated protections and capacity efficiency enabled by network coding brings about new opportunities to challenge the well-established trade-off of trading speed recovery for capacity efficiency and vice versa. In this context, the use of all-optical XOR network coding has reshaped the traditional 1+1 optical path protection in transparent WDM optical networks and established a new problem, called, 1+1 routing, wavelength and network coding assignment (1+1 RWNCA) as the extension of the conventional 1+1 routing and wavelength assignment (1+1 RWA). In this paper, we propose a bi-objective integer linear programming model of the 1+1 RWNCA problem aiming at minimizing the wavelength resources as the primary objective and simultaneously minimizing the wavelength link usage as the secondary objective. Our formulation uses a weighting method to combine two objectives into an integrated one and we provide insights on setting up the weight vectors to capture the priority of individual objectives. The effectiveness of our integrated objective model in comparison with reference designs based on the single-objective model, 1+1 RWA and 1+1 RWNCA, is numerically evaluated on different realistic topologies and traffic sets. Extensive simulation highlights that our proposal uses as efficient as around 60% of the required wavelength link resources of reference designs and simultaneously achieve the highest performance on the primary objective of minimizing the wavelength resources while its computation time is a few time longer than its single objective counterpart model.

关键词： Routing and wavelength assignment Dedicated path protection All-optical XOR network coding Transparent WDM networks integer linear programming Multi-objective pptimization

来源：评论

学校读者我要写书评

暂无评论

Sparse Array Design via integer linear programming

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2024年 72卷 4812-4826页

作者： Zhuang, Yangjingzhi Zhang, Xuejing He, Zishu Greco, Maria Sabrina Gini, Fulvio Univ Elect Sci & Technol China Dept Informat & Commun Engn Chengdu 611731 Peoples R China Univ Pisa Dept Informat Engn I-56122 Pisa Italy

In this paper, a design framework based on integer linear programming is proposed for optimizing sparse array structures. We resort to binary vectors to formulate the design problem for non-redundant arrays (NRA) and minimum-redundant arrays (MRA). The flexibility of the proposed framework allows for dynamic adjustment of constraints to meet various applicative requirements, e.g., to achieve desired array apertures and mitigate mutual coupling effects. The proposed framework is also extended to the design of high-order arrays associated by exploiting high-order cumulants. The effectiveness of the proposed sparse array design framework is investigated through extensive numerical analysis. A comparative analysis with closed-form solutions and integer linear programming-based array design methods confirms the superiority of the proposed design framework in terms of number of degrees of freedom (DOF) and direction of arrival (DOA) estimation accuracy.

关键词： Sensor arrays Antenna arrays Mutual coupling Vectors Sensors Redundancy Apertures Non-redundant array minimum-redundant array sparse array design integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Solving the constrained Single-Row Facility Layout Problem with integer linear programming

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2023年第6期61卷 1882-1897页

作者： Maier, Kerstin Taferner, Veronika Alpen Adria Univ Klagenfurt Dept Math A-9020 Klagenfurt Austria

The Single-Row Facility Layout Problem (SRFLP) is one of the most studied facility layout problems in the literature. It asks for an optimal arrangement of departments with given lengths on a row such that the weighted sum of all centre-to-centre distances between department pairs is minimised. Real-world facility layouts may require taking different restrictions on the placement of departments into account, such as arrangement on a fixed position, pairwise placement, or precedence considerations. Therefore, we consider the constrained Single-Row Facility Layout Problem (cSRFLP) that additionally considers positioning, ordering, and relation constraints on single-row facility layouts. In this work, we suggest a new integer linear programming (ILP) formulation for the cSRFLP, which outperforms the best available exact approach in literature. In an extensive computational study, we apply our ILP approach as well as an LP-based cutting plane algorithm on SRFLP and cSRFLP instances from the literature. We provide optimal cSRFLP layouts as well as strong lower bounds for instances with up to 42 departments. Further, we present new results for SRFLP instances from the literature. Additionally, we demonstrate the individual impact of the constraint sets on the run times of cSRFLP instances to emphasise further research on this rarely studied practice-oriented Facility Layout Problem.

关键词： Facility planning and design Facility Layout Problem single-row layout integer linear programming cutting planes

来源：评论

学校读者我要写书评

暂无评论

Solving haplotype inference problem with non-genotyped founders via integer linear programming

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第1期23卷 50-60页

作者： Cheng, Yongxi Lin, Guohui Xi An Jiao Tong Univ Sch Management Xian 710049 Shaanxi Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

In Cheng et al. (Acta Math. Appl. Sin. (English Ser.), 25:475-486, 2009), the authors present a cubic time zero-recombination haplotyping algorithm that can handle some incomplete pedigrees. More specifically, the algorithm can handle pedigrees with non-genotyped founders, provided that for each nuclear family at least one parent is genotyped and each non-genotyped founder appears in at most one nuclear family. The importance of this lies in that such cases frequently happen in real data, because some founders may have passed away and their genotype data can no longer be collected. In this paper, we further generalize the above algorithm by removing the first restriction. We present a new integer linear programming based algorithm that handles pedigrees with non-genotyped founders. The new algorithm allows the pedigrees to have nuclear families where both parents are non-genotyped founders, provided that each non-genotyped founder appears in at most one nuclear family.

关键词： Haplotype inference Pedigree Efficient algorithm integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Static Mapping of Applications on Heterogeneous Multi-Core Platforms Combining Logic-Based Benders Decomposition with integer linear programming

引用

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS 2018年第2期23卷 1–24页

作者： Emeretlis, Andreas Theodoridis, George Alefragis, Panayiotis Voros, Nikolaos Univ Patras VLSI Design Lab Dept Elect & Comp Engn Rion 26504 Greece Technol Educ Inst Western Greece Embedded Syst Design & Applicat Lab Comp & Informat Engn Dept Antirrio 30020 Greece

The proper mapping of an application on a multi-core platform and the scheduling of its tasks are key elements to achieve the maximum performance. In this article, a novel hybrid approach based on integrating the Logic-Based Benders Decomposition (LBBD) principle with a pure integer linear programming (ILP) model is introduced for mapping applications described by Directed Acyclic Graphs (DAGs) on platforms consisting of heterogeneous cores. The LBBD approach combines two optimization techniques with complementary strengths, namely ILP and Constraint programming (CP), and is employed as a cut generation scheme. The generated constraints are utilized by the ILP model to cut possible assignment combinations aiming at improving the solution or proving the optimality of the best-found one. The introduced approach was applied both on synthetic DAGs and on DAGs derived from real applications. Through the proposed approach, many problems were optimally solved that could not be solved by any of the above methods (ILP, LBBD) alone within a time limit of 2 hours, while the overall solution time was also significantly decreased. Specifically, the hybrid method exhibited speedups equal to 4.2 x for the synthetic instances and 10 x for the real-application DAGs over the LBBD approach and two orders of magnitude over the ILP model.

关键词： Task scheduling multi-core embedded platforms integer linear programming constraint programming Benders decomposition

来源：评论

学校读者我要写书评

暂无评论

Edge metric dimensions via hierarchical product and integer linear programming

引用

OPTIMIZATION LETTERS 2021年第6期15卷 1993-2003页

作者： Klavzar, Sandi Tavakoli, Mostafa Univ Ljubljana Fac Math & Phys Ljubljana Slovenia Univ Maribor Fac Nat Sci & Math Maribor Slovenia Inst Math Phys & Mech Ljubljana Slovenia Ferdowsi Univ Mashhad Fac Math Sci Dept Appl Math POB 1159 Mashhad 91775 Razavi Khorasan Iran

If S = {v(1),..., v(k)} is an ordered subset of vertices of a connected graph G and e is an edge of G, then the vector r(G)(e vertical bar S) = (d(G)(v(1), e),..., d(G)(v(k), e)) is the edge metric S-representation of e. If the vertices of G have pairwise different edge metric S-representations, then S is an edge metric generator for G. The cardinality of a smallest edge metric generator is the edge metric dimension edim(G) of G. A general sharp upper bound on the edge metric dimension of hierarchical products G(U) Pi H is proved. Exact formula is derived for the case when vertical bar U vertical bar = 1. An integer linear programming model for computing the edge metric dimension is proposed. Several examples are provided which demonstrate how these two methods can be applied to obtain the edge metric dimensions of some applicable graphs.

关键词： Metric dimension Edge metric dimension Hierarchical product integer linear programming Molecular graph

来源：评论

学校读者我要写书评

暂无评论

The weighted independent domination problem: integer linear programming models and metaheuristic approaches

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第3期265卷 860-871页

作者： Pinacho Davidson, Pedro Blum, Christian Lozano, Jose A. Univ Basque Country UPV EHU Dept Comp Sci & Artificial Intelligence Intelligent Syst Grp San Sebastian Spain Univ Santo Tomas Escuela Informat Concepcion Chile Artificial Intelligence Res Inst IIIA CSIC Campus UAB Bellaterra Spain Basque Ctr Appl Math BCAM Bilbao Spain

This work deals with the so-called weighted independent domination problem, which is an NP-hard combinatorial optimization problem in graphs. In contrast to previous work, this paper considers the problem from a non-theoretical perspective. The first contribution consists in the development of three integer linear programming models. Second, two greedy heuristics are proposed. Finally, the last contribution is a population-based iterated greedy metaheuristic which is applied in two different ways: (1) the meta heuristic is applied directly to each problem instance, and (2) the metaheuristic is applied at each iteration of a higher-level framework- known as construct, merge, solve and adapt - to sub-instances of the tackled problem instances. The results of the considered algorithmic approaches show that integer linear programming approaches can only compete with the developed metaheuristics in the context of graphs with up to 100 nodes. When larger graphs are concerned, the application of the populated-based iterated greedy algorithm within the higher-level framework works generally best. The experimental evaluation considers graphs of different types, sizes, densities, and ways of generating the node and edge weights. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization integer linear programming Heuristics Population-based iterated greedy Construct, merge, solve & adapt

来源：评论

学校读者我要写书评

暂无评论

Chromosome structures: reduction of certain problems with unequal gene content and gene paralogs to integer linear programming

引用

BMC BIOINFORMATICS 2017年第1期18卷 1-18页

作者： Lyubetsky, Vassily Gershgorin, Roman Gorbunov, Konstantin Russian Acad Sci Kharkevich Inst Inst Informat Transmiss Problems Bolshoy Karetny Per 19Bldg 1 Moscow 127051 Russia Lomonosov Moscow State Univ Fac Mech & Math Leninskiye Gory 1Main Bldg Moscow 119991 Russia

Background: Chromosome structure is a very limited model of the genome including the information about its chromosomes such as their linear or circular organization, the order of genes on them, and the DNA strand encoding a gene. Gene lengths, nucleotide composition, and intergenic regions are ignored. Although highly incomplete, such structure can be used in many cases, e.g., to reconstruct phylogeny and evolutionary events, to identify gene synteny, regulatory elements and promoters (considering highly conserved elements), etc. Three problems are considered;all assume unequal gene content and the presence of gene paralogs. The distance problem is to determine the minimum number of operations required to transform one chromosome structure into another and the corresponding transformation itself including the identification of paralogs in two structures. We use the DCJ model which is one of the most studied combinatorial rearrangement models. Double-, sesqui-, and single-operations as well as deletion and insertion of a chromosome region are considered in the model;the single ones comprise cut and join. In the reconstruction problem, a phylogenetic tree with chromosome structures in the leaves is given. It is necessary to assign the structures to inner nodes of the tree to minimize the sum of distances between terminal structures of each edge and to identify the mutual paralogs in a fairly large set of structures. A linear algorithm is known for the distance problem without paralogs, while the presence of paralogs makes it NP-hard. If paralogs are allowed but the insertion and deletion operations are missing (and special constraints are imposed), the reduction of the distance problem to integer linear programming is known. Apparently, the reconstruction problem is NP-hard even in the absence of paralogs. The problem of contigs is to find the optimal arrangements for each given set of contigs, which also includes the mutual identification of paralogs. Results: We pro

关键词： Chromosome structure Chromosomal rearrangement Ancestral genome Evolution along the tree Reconstruction of ancestral genomes Transformation of chromosome structures Parsimony principle integer linear programming Efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：