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

Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization

INFORMS JOURNAL ON COMPUTING 2021年第4期33卷 1419-1430页

作者： Juenger, Michael Mallach, Sven Univ Cologne Dept Math & Comp Sci D-50932 Cologne Germany Univ Bonn High Performance Comp & Analyt Lab D-53115 Bonn Germany

The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, physics, chemistry, neuroscience, and circuit layout-which is also due to its equivalence to the unconstrained binary quadratic optimization problem. Leading solution methods are based on linear or semidefinite programming and require the separation of the so-called odd-cycle inequalities. In their groundbreaking research, F. Barahona and A. R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the inequalities obtained correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context;it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection.

关键词： maximum cut binary quadratic optimization integer linear programming

来源：评论

学校读者我要写书评

暂无评论

SLAQA: Quality-level Aware Scheduling of Task Graphs on Heterogeneous Distributed Systems

引用

ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS 2021年第5期20卷 1–31页

作者： Roy, Sanjit Kumar Devaraj, Rajesh Sarkar, Arnab Senapati, Debabrata Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati 781039 Assam India Nvidia Graph Bangalore 560045 Karnataka India Indian Inst Technol Kharagpur Adv Technol Dev Ctr Kharagpur 721302 W Bengal India

Continuous demands for higher performance and reliability within stringent resource budgets is driving a shift from homogeneous to heterogeneous processing platforms for the implementation of today's cyber-physical systems (CPSs). These CPSs are typically represented as Directed-acyclic Task Graph (DTG) due to the complex interactions between their functional components that are often distributed in nature. In this article, we consider the problem of scheduling a real-time application modelled as a single DTG, where tasks may have multiple implementations designated as quality-levels, with higher quality-levels producing more accurate results and contributing to higher rewards/Quality-of-Service for the system. First, we introduce an optimal solution using integer linear programming (ILP) for a DTG with multiple quality-levels, to be executed on a heterogeneous distributed platform. However, this ILP-based optimal solution exhibits high computational complexity and does not scale for moderately large problem sizes. Hence, we propose two low-overhead heuristic algorithms called Global Slack Aware Quality-level Allocator (G-SLAQA) and Total Slack Aware Quality-level Allocator (T-SLAQA), which are able to produce satisfactorily efficient as well as fast solutions within a reasonable time. G-SLAQA, the baseline heuristic, is greedier and faster than its counter-part T-SLAQA, whose performance is at least as efficient as G-SLAQA. The efficiency of all the proposed schemes have been extensively evaluated through simulation-based experiments using benchmark and randomly generated DTGs. Through the case study of a real-world automotive traction controller, we generate schedules using our proposed schemes to demonstrate their practical applicability.

关键词： Distributed systems optimal scheduling directed-acyclic task graphs integer linear programming heterogeneous platform quality-of-service

来源：评论

学校读者我要写书评

暂无评论

Coefficients Quantization for Separable Two-Dimensional FIR Filter

引用

IEEJ TRANSACTIONS ON ELECTRICAL AND ELECTRONIC ENGINEERING 2021年第3期16卷 419-425页

作者： Li, Weiqi Wang, Hao Cheng, Xinmin Guo, Chunsheng Hangzhou Dianzi Univ Sch Commun Engn Hangzhou Zhejiang Peoples R China Huzhou Univ Sch Informat Engn Hangzhou Zhejiang Peoples R China

A separable two-dimensional (2-D) finite impulse response (FIR) filter can be implemented using an efficient parallel structure. The continuous coefficient separable 2-D FIR filter has already been well studied. In this study, the quantization of the coefficients of a separable 2-D FIR filter is addressed for the first time. Two (iterative) schemes [two-step integer linear programming algorithm (2-step-integer-LP) and two-step integer linear programming neighborhood search algorithm (2-step-integer-LP-neighbor)] for quantizing the coefficients are proposed, which have the same core idea: fixing some coefficients and optimally quantizing the other coefficients. Simulation experiment is conducted to verify the effectiveness of the proposed quantization schemes. The experimental results reveal that the two schemes both outperform the direct rounding method in terms of the design error. 2-Step-integer-LP performs slightly better than 2-step-integer-LP-neighbor. However, the former may not work, in some case, due to the large number of optimization variables. (c) 2021 Institute of Electrical Engineers of Japan. Published by Wiley Periodicals LLC.

关键词： separable 2‐ D FIR filter quantization integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A real-time train routing and platforming problem in complex railway stations

引用

JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2021年第4期41卷 5129-5137页

作者： Bai, Lijie Yuan, Zhiming Zhao, Hongtao Zhang, Tao Beijing Hua Tie Informat Technol Dev Co Beijing Peoples R China China Acad Railway Sci Signal & Commun Res Inst Beijing Peoples R China

This paper studies the real-time trains routing and platforming problem (RT-TRPP) in railway stations that arises from the unreliable arrival times of freight trains, flexible shunting operations and dynamic station layout caused by equipment failure. The feasibility of station timetable is checked before preparing a route for a train or after updating the station layout. If the station timetable is infeasible, the reassignment of trains is triggered. After introducing a problem formulation for the RT-TRPP, we propose an integer linear Program (ILP) that strives to minimize the number of conflicting trains. In resulting timetable, directions, arrival and leaving time remain the same with networks timetable to prevent traffic disturbance of neighboring territories. If the resulting timetable is still infeasible, conflicting trains are pointed out with the cause analysis. The method is tested on real-world complex station which receives always the overload of trains' activities. The optimal full-day solution of 249 trains is obtained within 2 seconds. The efficiency of this method meets the time-critical nature of RT-TRPP.

关键词： Train platforming train routing traffic management integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Hybrid hierarchical network design scheme with wavelength conversion

引用

IEICE COMMUNICATIONS EXPRESS 2025年第5期14卷 197-200页

作者： Doai, Reon Hayashi, Rie Matsukawa, Tatsuya Seki, Takeshi Miyamura, Takashi Kawabata, Akio Toyohashi Univ Technol 1-1 Hibarigaoka Tempaku Cho Toyohashi Aichi 4418580 Japan Senshu Univ 2-1-1 HigashimitaTama Ku Kawasaki Kanagawa 2148580 Japan NTT Corp NTT Network Serv Syst Labs 3-9-11 Midori Cho Musashino Tokyo 1808585 Japan

This paper proposes a hybrid hierarchical network design scheme with wavelength conversion (H2NDS) to design a low-delay network by integrating a conventional IP network and an optical network with wavelength conversion devices. In H2NDS, the network is divided into multiple domains, and wavelength converter devices and router devices are located at the relay node, an interconnection point between these domains. H2NDS is formulated as an integer linear programming problem to the sum of the delay of all end-to-end paths (delay) with constraint of the number of wavelengths in the optical network. Each end-to-end path selects the optimal relay node and selects either the router or wavelength converter devices to minimize the delay. The evaluation results showed that H2NDS significantly improved the delay performance compared to the benchmark model in which all end nodes belong to the nearest relay node, achieving a maximum reduction of 77.9 %.

关键词： all-photonics network wavelength conversion hierarchical net-work integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Extreme Event-Triggered Islanding Control of Urban Sub-Transmission Systems Considering Frequency Security Constraints

引用

IEEE Transactions on Power Systems 2025年

作者： Li, Jiaxu Xu, Yin Wang, Ying Wei, Wei Xu, Yan Beijing Jiaotong University School of Electrical Engineering Beijing100044 China State Grid Beijing Electric Power Company Urban District Power Supply Company Beijing100031 China Tsinghua University Department of Electrical Engineering Beijing100084 China Nanyang Technological University School of Electrical and Electronic Engineering 639198 Singapore

Urban power systems are featured by high density of critical loads. There is an urgent need to enhance their resilience. This paper proposes an islanding control method for urban power sub-transmission system to ensure a smooth transition to islanded operation under extreme events. An optimal islanding control problem is formulated, aiming to minimize the total control costs subject to dynamic frequency security constraints. An improved system frequency response model considering limiters, switches, and time delays is established to emulate dynamic frequency under large disturbances. Through discretization and linearization, the frequency-related constraints involving nonlinear differential-algebraic equations are converted into linear forms, and the islanding control problem is transformed into a mixed-integer linear program. The selection method of discretization is specially investigated. Finally, a two-stage solution method is designed to accelerate the computation of large-scale mixed-integer linear program by prefixing some integer variables. Simulation results show that the proposed method can maintain system transient frequency security during the islanding process and keep static node voltages in a reasonable range in islanded operation. In addition, the discretization method has high accuracy, and the proposed solution method can speed up the computation. © 1969-2012 IEEE.

关键词： integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Integrating lot-sizing and pricing decisions in multi-channel markets with discrete menus of prices

引用

Computers and Operations Research 2025年 182卷

作者： Terzi, Mourad Ouazene, Yassine Yalaoui, Alice Yalaoui, Farouk Mines Saint-Etienne Univ. Clermont Auvergne CNRS UMR 6158 LIMOS CMP Department of Manufacturing Sciences and Logistics GardanneF-13541 France Université de Technologie de Troyes 12 rue Marie Curie CEDEX TroyesCS 42060 10004 France Chaire Connected Innovation Université de Technologie de Troyes 12 rue Marie Curie CEDEX TroyesCS 42060 10004 France

This paper presents a model for coordinating lot-sizing and pricing decisions for manufacturers operating in multichannel markets with limited production capacity. Integrating these decisions is a significant challenge for manufacturers because it allows them to align their marketing and operational strategies effectively. This study addresses the application of attraction models to characterize consumers’ preferences and switching behavior between sales channels. Initially, the problem is formulated as a non-convex mixed-integer nonlinear programming (MINLP) model that incorporates production capacity constraints and a discrete menu of prices for each channel. To overcome the challenges of nonlinearity and nonconvexity, the problem is reformulated as an exact mixed-integer linear programming (MILP) model. Then, two MILP-based heuristics, the Fix-and-Relax and Double-Fix-and-Relax methods, are designed to solve the problem efficiently. An illustrative example demonstrates the model's practical application and offers valuable insights for decision-makers in real-life scenarios. Furthermore, a comprehensive experimental study on 120 benchmark instances shows that the proposed solution methods achieve near-optimal solutions in less than one minute of computational time. © 2025 The Authors

关键词： integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A flow formulation for the rolling stock maintenance scheduling problem

引用

IFAC-PapersOnLine 2024年第19期58卷 516-521页

作者： Pietro Folco Enrico Malaguti Abderrahim Sahli Sana Belmokhtar-Berraf Laurent Bouillaut Univ Gustave Eifel COSYS-GRETTIA 16 bd Newton Champs sur Marne F-77454 France DEI - University of Bologna 40136 Viale del Risorgimento 2 Bologna Italy IKOS Lab 155 Rue Anatole France Levallois-Perret 92300 France

Rolling stock maintenance is a key issue for the railway operations. Planning cyclical maintenance activities is a fundamental aspect of maintenance management, requiring a variety of operational choices. We present a novel flow formulation approach to schedule rolling stock maintenance activities optimising both maintenance costs and train availability. The schedule takes into account cyclical maintenance activities and the decoupling between elapsed and operational time. Limited resource and depot capacity are taken into account together with operational constraints to reflect the real operations of the railway system. The proposed formulation is based on an integer linear programming (ILP) approach, which is solved using a commercial solver on randomly generated realistic instances.

关键词： Rolling stock maintenance scheduling integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Competence-based assignment of tasks to workers in factories with demand-driven manufacturing

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2021年第2期29卷 553-565页

作者： Staruch, Bozena Staruch, Bogdan Univ Warmia & Mazury Olsztyn Poland

The paper is motivated by real problems concerning tasks assignment to workers in medium-sized upholstered furniture plants managed using the Demand-Driven Manufacturing. Although the methodology was developed for furniture plants it can be applied to other types of production plants. We involve competence coefficients, which describe the level of the worker's skills or capabilities to perform a specific task. The competence coefficients are also used to block the possibility of assigning the given task to a worker that has no skills to do it. Additionally, we involve a dummy worker to the model which guarantees the existence of a solution to the problem. We present and discuss integer linear programming Models for the posted problem that are closely related to the Generalized Assignment Problem. We also discuss the potential use of the presented methodology to solve real-life problems related to production management.

关键词： Tasks assignment Competence coefficient Production planning Demand-driven manufacturing Lean production Kanban integer linear programming Generalized assignment problem Multi-knapsack problem

来源：评论

学校读者我要写书评

暂无评论

A simultaneous sequencing and allocation problem for military pilot training: integer programming approaches

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2021年 154卷 107161-107161页

作者： Mak-Hau, Vicky Hill, Brendan Kirszenblat, David Moran, Bill Nguyen, Vivian Novak, Ana Deakin Univ Sch Informat Technol Geelong Vic 3218 Australia Dept Def Def Sci & Technol Grp 506 Lorimer St Fishermans Bend Vic 3207 Australia

In this paper, we study a unique, rich combinatorial optimization problem that arose from helicopter aircrew training for the Royal Australian Navy. Each pilot trainee (student) has to complete a syllabus. A syllabus is a sequence of courses (commonly known as subjects), and each course is associated with a pass rate. A prerequisite structure exists amongst some courses. Each course has a number of repeated sessions, each spanning the same amount of time, but occupying a different set of (possibly overlapping) time slots. A feasible schedule is a sequence of course sessions such that each course in the syllabus is covered by exactly one session, and that all pre-requisite requirements are observed. The optimization problem is to simultaneously assemble course sessions to form feasible schedules, allocate students to these schedules with an objective to minimize the total time-span in completing the syllabus, while ensuring that the class size limits for each course session is not exceeded. The problem is different from the school or university time tabling family of problems due to the assembly component required. This paper is to serve as a pilot study: we derive a number of mixed-integer linear programming models and investigate their performance using test instances provided for us by our industry partner. For each of these models, we propose a number of solution strategies as topics for future research papers. From our numerical testing, it appears that the Column Generation-based approach is computationally the most promising method.

关键词： Scheduling Allocation integer linear programming Column generation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：