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

New integer linear programming approaches for course timetabling

COMPUTERS & OPERATIONS RESEARCH 2008年第7期35卷 2209-2233页

作者： Boland, Natashia Hughes, Barry D. Merlot, Liam T. G. Stuckey, Peter J. Univ Melbourne Dept Math & Stat Melbourne Vic 3010 Australia Quantm Melbourne Vic 3000 Australia Univ Melbourne Dept Comp Sci & Software Engn Melbourne Vic 3010 Australia

The most complete form of academic timetabling problem is the population and course timetabling problem. In this problem, there may be multiple classes of each subject, and the decision on which students are to constitute each class is made in concert with the decision on the timetable for each class. In order to solve this problem, it is normally simplified or decomposed in some fashion. One simplification commonly used in practice is known as blocking: it is assumed that the classes can be partitioned into sets of classes (or blocks) that will be timetabled in parallel. This restricts clashing to occur only between classes in the same block, and essentially removes the timetabling aspect of the problem, which can be carried out, once the blocks are constituted and the classes populated. The problem of constituting the blocks and populating the classes, known as the course blocking and population problem, is nevertheless a challenging problem, and provides the focus of this paper. We demonstrate, using data provided by a local high school, that integer linear programming approaches can solve the problem in a matter of seconds. Key features include remodelling to remove symmetry caused by students with identical subject selection, and the observation that in practice, only integrality of the block composition variables needs to be enforced;the class population aspects of the model have strong integrality properties. (C) 2006 Elsevier Ltd. All rights reserved.

关键词： academic timetabling blocking integer linear programming

来源：评论

学校读者我要写书评

暂无评论

IntSat: integer linear programming by conflict-driven constraint learning

引用

OPTIMIZATION METHODS & SOFTWARE 2024年第1期40卷 169-196页

作者： Nieuwenhuis, Robert Oliveras, Albert Rodriguez-Carbonell, Enric Univ Politecn Cataluna Dept Comp Sci Barcelona Spain

State-of-the-art SAT solvers are nowadays able to handle huge real-world instances. The key to this success is the Conflict-Driven Clause-Learning (CDCL) scheme, which encompasses a number of techniques that exploit the conflicts that are encountered during the search for a solution. In this article, we extend these techniques to integer linear programming (ILP), where variables may take general integer values instead of purely binary ones, constraints are more expressive than just propositional clauses, and there may be an objective function to optimize. We explain how these methods can be implemented efficiently and discuss possible improvements. Our work is backed with a basic implementation showing that, even in this far less mature stage, our techniques are already a useful complement to the state of the art in ILP.

关键词： integer linear programming SAT solving conflict-driven clause learning

来源：评论

学校读者我要写书评

暂无评论

DNA solution of integer linear programming

引用

APPLIED MATHEMATICS AND COMPUTATION 2005年第1期170卷 626-632页

作者： Wang, SY Yang, AM Shanxi Univ Dept Math Taiyuan 030006 Shanxi Peoples R China

The integer linear programming is an NP-complete problem. In this paper, a detailed discussion is given of DNA algorithms for the DNA solution of the integer linear programming. (c) 2005 Elsevier Inc. All rights reser... 详细信息

关键词： DNA computing integer linear programming

来源：评论

学校读者我要写书评

暂无评论

On-line verification of initial-state opacity by Petri nets and integer linear programming

引用

ISA TRANSACTIONS 2019年 93卷 108-114页

作者： Cong, Xuya Fanti, Maira 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 Macao Peoples R China

This paper deals with a problem related to the observability of discrete event systems: the initial-state opacity. Given a set of system states (the secret), a system observation is called initial-state opaque if an agent (named intruder), who can partially observe the system, cannot determine whether the set of initial states consistent with an event sequence is included in the secret. Such a character can describe security problems in cyber-infrastructures, such as Internet and mobile communication networks or national defense service systems. This work presents a novel on-line methodology to verify the notion of initial-state opacity of discrete event systems that are modeled by labeled Petri nets. By working on-line, the intruder records an event and exploits integer linear programming problem for checking the initial-state opacity of the system's evolution under the given observation. A set of examples are shown to shed light on the efficiency of the presented methodology. (C) 2019 ISA. Published by Elsevier Ltd. All rights reserved.

关键词： Initial-state opacity Petri nets integer linear programming

来源：评论

学校读者我要写书评

暂无评论

VOLTAGE CONTROL USING A COMBINED integer linear-programming AND RULE-BASED APPROACH

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 1992年第2期7卷 744-752页

作者： HSU, YY HO, KL LIANG, CC LAI, TS BIJWE, PR KOTHARI, DP TAIWAN POWER CO DEPT SYST OPERAT TAIPEI TAIWAN INDIAN INST TECHNOL NEW DELHI 110029 INDIA

Voltage control of Taiwan Power Company is investigated using a nile-based expert system. The developed expert system, which is implemented on a personal computer, is written using the artificial intelligence language PROLOG. To benefit from human experts' past experience, the heuristic rules currently followed by the operators at Taiwan Power Company are compiled and coded in the rule base of the expert system. To determine the required adjustments to the various VAR control devices, an integer linear programming (LP) routine is developed using the branch and bound method. With the developed integer LP routine, integer solutions to the control variables such as switchable inductors and capacitors and transformer tap settings can be achieved by the expert system without rounding off the results. The objective function employed in this study is to minimize the number of required adjustments, making the approach suitable for practical applications. The designed expert system has been applied to correct the abnormal voltages in Taiwan Power Company during emergency conditions. It is found from the study results that the proposed expert system is a valuable aid to system operators for voltage control.

关键词： VAR MANAGEMENT VOLTAGE CONTROL POWER SYSTEM OPERATION EXPERT SYSTEMS integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Discovering workflow nets using integer linear programming

引用

COMPUTING 2018年第5期100卷 529-556页

作者： van Zelst, S. J. van Dongen, B. F. van der Aalst, W. M. P. Verbeek, H. M. W. Eindhoven Univ Technol Dept Math & Comp Sci POB 513 NL-5600 MB Eindhoven Netherlands

Process mining is concerned with the analysis, understanding and improvement of business processes. Process discovery, i.e. discovering a process model based on an event log, is considered the most challenging process mining task. State-of-the-art process discovery algorithms only discover local control flow patterns and are unable to discover complex, non-local patterns. Region theory based techniques, i.e. an established class of process discovery techniques, do allow for discovering such patterns. However, applying region theory directly results in complex, overfitting models, which is less desirable. Moreover, region theory does not cope with guarantees provided by state-of-the-art process discovery algorithms, both w.r.t. structural and behavioural properties of the discovered process models. In this paper we present an ILP-based process discovery approach, based on region theory, that guarantees to discover relaxed sound workflow nets. Moreover, we devise a filtering algorithm, based on the internal working of the ILP-formulation, that is able to cope with the presence of infrequent, exceptional behaviour. We have extensively evaluated the technique using different event logs with different levels of exceptional behaviour. Our experiments show that the presented approach allows us to leverage the inherent shortcomings of existing region-based approaches. The techniques presented are implemented and readily available in the HybridILPMiner package in the open-source process mining tool-kits ProM (http://***) and RapidProM (http://***).

关键词： Process mining Process discovery Region theory integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A method to improve integer linear programming problem with branch-and-bound procedure

引用

APPLIED MATHEMATICS AND COMPUTATION 2006年第2期179卷 484-493页

作者： Chan, Din-Yuen Ku, Cheng-Yuan Li, Ming-Chai Natl Chung Cheng Univ Dept Informat Management Chiayi 62117 Taiwan Natl Chia Yi Univ Dept Comp Sci & Informat Engn Chiayi 62117 Taiwan

integer linear programming (ILP) problems are harder to solve than linear programming (LP) problems. It doesn't work if try to round off the results of LP problems and claim they are the optimum solution. The branch-and-bound (B&B) is the popular method to solve ILP problems. In this paper, we propose a revised B&B, which is demonstrated to be more efficient most of time. This method is extraordinarily useful when facing ILP problems with large differences between constraints and variables. It could reduce the number of constraint and work efficiently when handling ILP problems with many constraints and less variables. Even if the ILP problems have fewer constraints but many variables, we suggest using duality concept to interchange variables with constraints. Then, the revised B&B could be used to compute results very quickly. (c) 2006 Elsevier Inc. All rights reserved.

关键词： integer linear programming branch-and-bound procedure duality acceleration of computation operations research

来源：评论

学校读者我要写书评

暂无评论

Technology Mapping Method Using integer linear programming for Low Power Consumption and High Performance in General-Synchronous Framework

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2016年第7期E99A卷 1366-1373页

作者： Kawaguchi, Junki Mashiko, Hayato Kohira, Yukihide Univ Aizu Aizu Wakamatsu Fukushima 9658580 Japan

In general-synchronous framework, in which the clock is distributed periodically to each register but not necessarily simultaneously, circuit performance is expected to be improved compared to complete synchronous framework, in which the clock is distributed periodically and simultaneously to each register. To improve the circuit performance more, logic synthesis for general-synchronous framework is required. In this paper, under the assumption that any clock schedule is realized by an ideal clock distribution circuit, when two or more cell libraries are available, a technology mapping method which assigns a cell to each gate in the given logic circuit by using integer linear programming is proposed. In experiments, we show the effectiveness of the proposed technology mapping method.

关键词： general-synchronous framework technology mapping integer linear programming

来源：评论

学校读者我要写书评

暂无评论

CDPath: Cooperative Driver Pathways Discovery Using integer linear programming and Markov Clustering

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2021年第4期18卷 1384-1395页

作者： Yang, Ziying Yu, Guoxian Guo, Maozu Yu, Jiantao Zhang, Xiangliang Wang, Jun Shandong Univ Sch Software Jinan 250101 Peoples R China Beijing Univ Civil Engn & Architecture Sch Elect & Informat Engn Beijing 100044 Peoples R China North West A&F Univ Coll Informat Engn Xianyang Shaanxi Peoples R China King Abdullah Univ Sci & Technol Comp Elect & Math Sci & Engn Div Thuwal Saudi Arabia

Discovering driver pathways is an essential task to understand the pathogenesis of cancer and to design precise treatments for cancer patients. Increasing evidences have been indicating that multiple pathways often function cooperatively in carcinogenesis. In this study, we propose an approach called CDPath to discover cooperative driver pathways. CDPath first uses integer linear programming to explore driver core modules from mutation profiles by enforcing co-occurrence and functional interaction relations between modules, and by maximizing the mutual exclusivity and coverage within modules. Next, to enforce cooperation of pathways and help the follow-up exact cooperative driver pathways discovery, it performs Markov clustering on pathway-pathway interaction network to cluster pathways. After that, it identifies pathways in different modules but in the same clusters as cooperative driver pathways. We apply CDPath on two TCGA datasets: breast cancer (BRCA) and endometrial cancer (UCEC). The results show that CDPath can identify known (i.e., TP53) and potential driver genes (i.e., SPTBN2). In addition, the identified cooperative driver pathways are related with the target cancer, and they are involved with carcinogenesis and several key biological processes. CDPath can uncover more potential biological associations between pathways (over 100 percent) and more cooperative driver pathways (over 200 percent) than competitive approaches. The demo codes of CDPath are available at http://***/***?name=CDPath.

关键词： Cancer Markov processes Proteins integer linear programming Genomics Bioinformatics Cooperative driver pathway data fusion integer linear programming markov clustering

来源：评论

学校读者我要写书评

暂无评论

Multi-objective Phasor Measurement Unit Placement in Electric Power Networks: integer linear programming Formulation

引用

ELECTRIC POWER COMPONENTS AND SYSTEMS 2015年第17期43卷 1902-1911页

作者： Aghaei, Jamshid Baharvandi, Amir Akbari, Mohammad-Amin Muttaqi, Kashem M. Asban, Mohammad-Reza Heidari, Alireza Shiraz Univ Technol Dept Elect & Elect Engn Shiraz *** Iran Univ Wollongong Australian Power Qual & Reliabil Ctr Sch Elect Comp & Telecommun Engn Wollongong NSW Australia Univ New S Wales Australian Energy Res Inst Sydney NSW Australia Univ New S Wales Sch Elect Engn & Telecommun Sydney NSW Australia

A multi-objective optimal phasor measurement unit placement model using integer linear programming is presented in this article. The proposed model simultaneously optimizes two objectives, i.e., minimization of phasor measurement unit numbers and maximization of measurement redundancy. To calculate the redundancy criteria, the single-line outage and the phasor measurement unit loss are considered simultaneously. A linear formulation is presented for both objective functions. Also herein, to address conflicting attributes and identify Pareto optimal solutions of the multi-objective optimal phasor measurement unit placement problem, a new multi-objective mathematical programming method is proposed. Finally, a new index, i.e., minimum distance to utopia point, is implemented to select the most preferred solution among the available Pareto front based options on the goal to achieve judicious decision makers. Two test systems, i.e., a modified 9-bus and an IEEE 118-bus test systems, are used to illustrate the effectiveness of the proposed framework.

关键词： phasor measurement unit integer linear programming phasor measurement unit placement redundancy observability analysis multi-objective mathematical programming line outage Pareto solution optimization state estimation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：