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

On the path-width of integer linear programming

INFORMATION AND COMPUTATION 2017年第Part2期253卷 257-271页

作者： Enea, Constantin Habermehl, Peter Inverso, Omar Parlato, Gennaro Univ Paris Diderot IRIF F-75205 Paris 13 France CNRS F-75205 Paris 13 France Gran Sasso Sci Inst Viale Francesco Crispi 7 Laquila Italy Univ Southampton Sch Elect & Comp Sci Southampton SO9 5NH Hants England

We consider the feasibility problem of integer linear programming (ILP). We show that solutions of any ILP instance can be naturally represented by an FO-definable class of graphs. For each solution there may be many graphs representing it. However, one of these graphs is of path-width at most 2n, where n is the number of variables in the instance. Since FO is decidable on graphs of bounded path-width, we obtain an alternative decidability result for ILP. The technique we use underlines a common principle to prove decidability which has previously been employed for automata with auxiliary storage. We also show how this new result links to automata theory and program verification. (C) 2016 Elsevier Inc. All rights reserved.

关键词： integer linear programming Bounded path-width First-order logic on graphs Automata

来源：评论

学校读者我要写书评

暂无评论

A parallel domain decomposition algorithm for coastal ocean circulation models based on integer linear programming

引用

OCEAN DYNAMICS 2017年第5期67卷 639-649页

作者： Jordi, Antoni Georgas, Nickitas Blumberg, Alan Stevens Inst Technol Davidson Lab Hoboken NJ 07030 USA

This paper presents a new parallel domain decomposition algorithm based on integer linear programming (ILP), a mathematical optimization method. To minimize the computation time of coastal ocean circulation models, the ILP decomposition algorithm divides the global domain in local domains with balanced work load according to the number of processors and avoids computations over as many as land grid cells as possible. In addition, it maintains the use of logically rectangular local domains and achieves the exact same results as traditional domain decomposition algorithms (such as Cartesian decomposition). However, the ILP decomposition algorithm may not converge to an exact solution for relatively large domains. To overcome this problem, we developed two ILP decomposition formulations. The first one (complete formulation) has no additional restriction, although it is impractical for large global domains. The second one (feasible) imposes local domains with the same dimensions and looks for the feasibility of such decomposition, which allows much larger global domains. Parallel performance of both ILP formulations is compared to a base Cartesian decomposition by simulating two cases with the newly created parallel version of the Stevens Institute of Technology's Estuarine and Coastal Ocean Model (sECOM). Simulations with the ILP formulations run always faster than the ones with the base decomposition, and the complete formulation is better than the feasible one when it is applicable. In addition, parallel efficiency with the ILP decomposition may be greater than one.

关键词： Coastal ocean circulation model Parallel computing Domain decomposition integer linear programming Urban ocean ECOM

来源：评论

学校读者我要写书评

暂无评论

Trip-Based integer linear programming Model for Static Multi-Car Elevator Operation Problems

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2017年第2期E100A卷 385-394页

作者： Inamoto, Tsutomu Higami, Yoshinobu Kobayashi, Shin-ya Ehime Univ Grad Sch Sci & Engn Matsuyama Ehime 7908577 Japan

In this paper, the authors propose an integer linear programming (ILP) model for static multi-car elevator operation problems. Here, "static" means that all information which make the behavior of the elevator system indeterministic is known before scheduling. The proposed model is based on the trip-based ILP model for static single-car elevator operation problems. A trip of an elevator is a one-directional movement of that elevator, which is labaled upward or downward. In the trip-based ILP model, an elevator trajectory is scheduled according to decision variables which determine allocations of trips to users of an elevator system. That model has such an advantage that the difficulty in solving ILP formulations resulted by that model does not depend on the length of the planning horizon nor the height of the considered building, thus is effective when elevator trajectories are simple. Moreover, that model has many variables relevant to elevators' positions. The proposed model is resulted by adding 3 constraints which are basically based on those variables and make it possible to prevent elevators in a same shaft from interfering. The first constraint simply imposes the first and last floors of an upper trip to be above those of its lower trip. The second constraint imagines the crossing point between upper and lower trips and imposes it ahead of or behind the lower trip according to their directions. The last constraint estimates future positions of elevators and imposes the upper trip to be above floors of passengers on the lower trip. The basic validity of the proposed model is displayed by solving 90 problem instances and examining elevator trajectories generated from them, then comparing objective function values of elevator trajectories on a multi-car elevator system with those on single-car elevator systems.

关键词： elevator operation problem multi-car elevator system integer linear programming interference prevention

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Discovery of Boolean metabolic networks: integer linear programming based approach

引用

BMC SYSTEMS BIOLOGY 2018年第Sup1期12卷 7-7页

作者： Qiu, Yushan Jiang, Hao Ching, Wai-Ki Cheng, Xiaoqing Shenzhen Univ Coll Math & Stat Nanhai Ave 3688 Shenzhen 518060 Peoples R China Renmin Univ China Sch Informat Dept Math 59 Zhong Guan Cun Ave Beijing 100872 Peoples R China Univ Hong Kong Dept Math Pokfulam Rd Hong Kong Hong Kong Peoples R China Xi An Jiao Tong Univ Sch Math & Stat 28 West Xianning Rd Xian 710049 Peoples R China

Background: Traditional drug discovery methods focused on the efficacy of drugs rather than their toxicity. However, toxicity and/or lack of efficacy are produced when unintended targets are affected in metabolic networks. Thus, identification of biological targets which can be manipulated to produce the desired effect with minimum side-effects has become an important and challenging topic. Efficient computational methods are required to identify the drug targets while incurring minimal side-effects. Results: In this paper, we propose a graph-based computational damage model that summarizes the impact of enzymes on compounds in metabolic networks. An efficient method based on integer linear programming formalism is then developed to identify the optimal enzyme-combination so as to minimize the side-effects. The identified target enzymes for known successful drugs are then verified by comparing the results with those in the existing literature. Conclusions: Side-effects reduction plays a crucial role in the study of drug development. A graph-based computational damage model is proposed and the theoretical analysis states the captured problem is NP-completeness. The proposed approaches can therefore contribute to the discovery of drug targets. Our developed software is available at "http://***/similar to wkc/***".

关键词： Metabolic network integer linear programming Boolean model

来源：评论

学校读者我要写书评

暂无评论

Decentralized Fault Diagnosis by Petri Nets and integer linear programming

引用

IFAC-PapersOnLine 2017年第1期50卷 13624-13629页

作者： Cong, Xuya Pia Fanti, Maria Marcello Mangini, Agostino Li, Zhiwu School of Electro-Mechanical Engineering Xidian University No. 2 South Taibai Road Xi'an710071 China Department of Electrical and Information Engineering Polytechnic of Bari Bari70125 Italy Institute of Systems Engineering Macau University of Science and Technology TaipaMacau China

This paper addresses the problem of decentralized on-line fault diagnosis in the Petri net framework by using integer linear programming. The decentralized architecture consists of a set of local sites communicating with a coordinator that determines whether the behaviour of a system is normal or faulty. In particular, a protocol is presented for the communication between the local sites and the coordinator, and the rules for the coordinator to decide the global diagnosis results are proposed. © 2017

关键词： integer programming Clustering algorithms Failure analysis Fault detection Petri nets Program diagnostics Decentralized architecture Decentralized fault diagnosis integer linear programming Local sites NET framework On line fault diagnosis

来源：评论

学校读者我要写书评

暂无评论

On the path-width of integer linear programming 5

On the path-width of integer linear programming

引用

5th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF)

关键词： integer linear programming Bounded path-width First-order logic on graphs Automata

来源：评论

学校读者我要写书评

暂无评论

A Regression-based Approach using integer linear programming for Single-document Summarization 29

A Regression-based Approach using Integer Linear Programming...

引用

29th Annual IEEE International Conference on Tools with Artificial Intelligence (ICTAI)

作者： Oliveira, Hilario Lins, Rafael Dueire Lima, Rinaldo Freitas, Fred Simske, Steven J. Univ Fed Pernambuco Informat Ctr Recife PE Brazil HP Labs Ft Collins CO 80528 USA

ISBN: (纸本)9781538638767

Most of the existing approaches for extractive single-document summarization of news articles rely on a single method to summarize all input documents. Recent work demonstrated that this is a significant limitation, since no summarization technique can achieve high performance for all input articles. In this context, this paper proposes a new regression-based approach using integer linear programming (ILP) for single-document summarization. The proposed solution relies on a concept-based ILP method to generate multiple candidate summaries for each input article exploring different concept weighting methods and representation forms. Afterward, a regression model enriched with several extracted features at summary, sentence and n-gram level is applied to select among the candidates the most informative summary based on an estimation of the traditional ROUGE-1 score. The investigated features are derived from indicators of content importance such as frequency, position, and coverage. Experiments conducted on the DUC 2001-2002 and CNN corpora show that the proposed method statistically outperforms other state-of-the-art extractive summarization approaches in most scenarios regarding ROUGE-1 and ROUGE-2 recall measures.

关键词： Feature extraction Task analysis Mathematical model Frequency measurement integer linear programming Optimization Coherence

来源：评论

学校读者我要写书评

暂无评论

Decentralized Fault Diagnosis by Petri Nets and integer linear programming

Decentralized Fault Diagnosis by Petri Nets and Integer Line...

引用

20th World Congress of the International-Federation-of-Automatic-Control (IFAC)

作者： Cong, Xuya Fanti, Maria Pia Mangini, Agostino Marcello Li, Zhiwu Xidian Univ Sch Electromech Engn 2 South Taibai Rd Xian 710071 Shaanxi Peoples R China Polytech Bari Dept Elect & Informat Engn I-70125 Bari Italy Macau Univ Sci & Technol Inst Syst Engn Taipa Macau Peoples R China

关键词： Fault diagnosis Petri nets integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Solving the Join Ordering Problem via Mixed integer linear programming 17

Solving the Join Ordering Problem via Mixed Integer Linear P...

引用

ACM International Conference on Management of Data

作者： Trummer, Immanuel Koch, Christoph Cornell Univ Ithaca NY 14853 USA Ecole Polytech Fed Lausanne Lausanne Switzerland

ISBN: (纸本)9781450341974

We transform join ordering into a mixed integer linear 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.

关键词： Query optimization integer linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：