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

A new and faster representation for counting integer points in parametric polyhedra

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2024年 1-51页

作者： Gribanov, Dmitry V. Malyshev, Dmitry S. Pardalos, Panos M. Zolotykh, Nikolai Yu. Moscow Inst Phys & Technol Lab Discrete & Combinatorial Optimizat Inst Lane 9 Moscow 141700 Russia HSE Univ Lab Algorithms & Technol Network Anal 136 Rodionova Ulitsa Nizhnii Novgorod 603093 Russia Univ Florida Dept Ind & Syst Engn 401 Weil Hall 116595 Gainesville FL USA Lobachevsky State Univ Nizhny Novgorod 23 Gagarina Ave Nizhnii Novgorod 603950 Russia

In this paper, we consider the counting function EP(y)=|Py boolean AND Znx|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y) = |{{\,\mathrm{\mathcal {P}}\,}}_{y} \cap {{\,\mathrm{\mathbb {Z}}\,}}<^>{n_x}|$$\end{document} for a parametric polyhedron Py={x is an element of Rnx:Ax <= b+By}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\mathcal {P}}\,}}_{y} = \{ x \in {{\,\mathrm{\mathbb {R}}\,}}<^>{n_x} :A x \le b + B y\}$$\end{document}, where y is an element of Rny\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$y \in {{\,\mathrm{\mathbb {R}}\,}}<^>{n_y}$$\end{document}. We give a new representation of EP(y)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)$$\end{document}, called a piece-wise step-polynomial with periodic coefficients, which is a generalization of piece-wise step-polynomials and integer/rational Ehrhart's quasi-polynomials. It gives the fastest way to calculate EP(y)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{

关键词： integer linear programming Parametric integer programming Short rational generating function Bounded sub-determinants Multidimensional knapsack problem Subset-sum problem Counting problem

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第4期89卷 1033-1067页

作者： Gribanov, Dmitry Shumilov, Ivan Malyshev, Dmitry Zolotykh, Nikolai HSE Univ Lab Algorithms & Technol Network Anal 136 Rodionova Ulitsa Nizhnii Novgorod 603093 Russia Lobachevsky State Univ Nizhny Novgorod 23 Gagarina Ave Nizhnii Novgorod 603950 Russia Lobachevsky State Univ Nizhni Novgorod Math Future Technol Ctr 23 Gagarina Ave Nizhnii Novgorod 603950 Russia

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P boolean AND Zn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\mathcal {P}}\,}}\cap {{\,\mathrm{\mathbb {Z}}\,}}<^>n$$\end{document}, assuming that P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\mathcal {P}}\,}}$$\end{document} is a polyhedron, defined by systems Ax <= b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A x \le b$$\end{document} or Ax=b,x >= 0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Ax = b,\, x \ge 0$$\end{document} with a sparse matrix A. We develop algorithms for these problems that outperform state-of-the-art ILP and counting algorithms on sparse instances with bounded elements in terms of the computational complexity. Assuming that the matrix A has bounded elements, our complexity bounds have the form sO(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s<^>{O(n)}$$\end{document}, where s is the minimum between numbers of non-zeroes in

关键词： integer linear programming Counting problem Parameterized complexity Multipacking Multicover Stable set Vertex cover Dominating set Multiset multicover Hypergraph matching Sparse matrix

来源：评论

学校读者我要写书评

暂无评论

A Scalable and Adaptable Supervised Learning Approach for Solving the Traveling Salesman Problems

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2024年第11期25卷 17092-17104页

作者： Lyu, Zefeng Islam, Md. Zahidul Yu, Andrew Junfang Univ Tennessee Knoxville Dept Ind & Syst Engn Knoxville TN 37996 USA Clemson Univ Dept Ind Engn Clemson SC 29634 USA

The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem that has attracted extensive research efforts in developing exact methods and heuristics. However, the scalability and generalization of learning-based approaches remain significant challenges. This paper addresses this gap by proposing an approach that integrates supervised learning with traditional approaches. In particular, we introduce the concept of "anchors", which represents nodes that should be connected to their nearest neighbors in the optimal solution. Our approach differs from the previous supervised learning approaches in that, instead of using the whole distance matrix, our neural network leverages local information to make predictions, which enables it to handle arbitrarily large-scale TSP instances without a decline on prediction accuracy. Experimental results demonstrate that our model successfully identifies 87% of the anchors with a precision of over 95% for both generated instances and TSPLIB instances, which were unseen by the model during the training. The performance of the proposed framework is evaluated by integrating the predicted anchors into existing methods such as the Miller-Tucker-Zemlin (MTZ) model and the insertion algorithms. Our approach demonstrates remarkable improvements in solution quality and computational time. By comparing with the graph pointer network, a state-of-the-art learning-based approach, the proposed algorithm achieves a 28% reduction in the average gap and a 59% decrease in computational time for solving TSP instances with 1,000 nodes.

关键词： Supervised learning Prediction algorithms Machine learning algorithms Scalability Heuristic algorithms Training Computational modeling Traveling salesman problem supervised learning constructive heuristics integer linear programming generalization adaptability

来源：评论

学校读者我要写书评

暂无评论

A fuzzy-probabilistic bi-objective mathematical model for integrated order allocation, production planning, and inventory management

引用

International Journal of Applied Decision Sciences 2024年第6期17卷 772-798页

作者： Solikhin, S. Sutrisno, S. Aziz, Abdul Wicaksono, Purnawan Adi Department of Mathematics Diponegoro University Jalan Prof. Soedarto SH Tembalang Semarang50275 Indonesia Department of Industrial Engineering Diponegoro University Jalan Prof. Soedarto SH Tembalang Semarang50275 Indonesia

An optimisation-based decision-making support is proposed in this study in the form of fuzzy-probabilistic programming, which can be used to solve integrated order allocation, production planning, and inventory management problems in fuzzy and probabilistic uncertain environments. The problem was modelled in an uncertain mathematical optimisation model with two objectives: maximising the expectation of production volume and minimising the expectation of total operational cost subject to demand and other constraints. The model belongs to fuzzy-probabilistic bi-objective integer linear programming, and the generalised reduced gradient method combined with the branch-and-bound algorithm was utilised to solve the derived model. Numerical simulations were performed to illustrate how the optimal decision was formulated. The results showed that the proposed decision-making support was successful in providing the optimal decision with the maximum expectation of the production volume and minimum expectation of the total operational cost. Therefore, the approach can be implemented by decision-makers in manufacturing companies. © 2024 Inderscience Enterprises Ltd.

关键词： integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Coordinating scheduling and rejection decisions in a two-machine flow shop scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期316卷 887-898页

作者： Shabtay, Dvir Gerstl, Enrique Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel Hebrew Univ Jerusalem Sch Business Adm Jerusalem Israel

We study a two-machine flow shop scheduling problem where any operation can be rejected at a certain cost. A solution for such a problem requires two sets of decisions. The first involves the partition of the set of operations into two subsets: the set of operations that are accepted for scheduling in the shop, and the set of rejected operations. The second decision involves scheduling the set of accepted operations in the shop. The objective is to find a solution that minimizes the sum of the makespan and the total rejection cost. We prove that the problem is NP -hard even if all processing operations have identical processing times and identical rejection costs on either one of the two machines. We show, however, that the problem is fixed parameterized tractable with respect to a parameter that combine the number of different processing times on both machines with the number of different rejection costs on one out of the two machines. We also provide a pseudo-polynomial time algorithm for the problem, which we then convert into a fully polynomial time approximation scheme. This is achieved by dividing the problem into a set of subproblems and deriving a fully polynomial time approximation scheme for each one of them, separately. Finally, we present an integer linear programming formulation of the problem and two simple 2 -approximation algorithms.

关键词： Scheduling Flow shop Approximation algorithms Rejection integer linear programming

来源：评论

学校读者我要写书评

暂无评论

On Δ-modular integer linear problems in the canonical form and equivalent problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第3期88卷 591-651页

作者： Gribanov, Dmitry Shumilov, Ivan Malyshev, Dmitry Pardalos, Panos HSE Univ Lab Algorithms & Technol Network Anal 136 Rodionova Ulitsa Nizhnii Novgorod 603093 Russia Lobachevsky State Univ Nizhny Novgorod 23 Gagarina Ave Nizhnii Novgorod 603950 Russia Univ Florida Dept Ind & Syst Engn 401 Weil Hall Gainesville FL 32611 USA

Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type max{c(inverted perpendicular)x : Ax = b, x is an element of Z(>= 0)(n)}, where all the entries of A, b, c are integer, parameterized by the number of rows of A and parallel to A parallel to(max) . This class of problems is known under the name of ILP problems in the standard form, adding the word "bounded" if x <= u, for some integer vector u. Recently, many new sparsity, proximity, and complexity results were obtained for bounded and unbounded ILP problems in the standard form. In this paper, we consider ILP problems in the canonical form max{c(inverted perpendicular)x: b(l) <= Ax <= b(r), is an element of Z(n)}, where b(l) and b(r) are integer vectors. We assume that the integer matrix A has the rank n,(n+m) rows, n columns, and parameterize the problem by m and Delta(A), where Delta (A) is the maximum of n x n sub-determinants of A, taken in the absolute value. We show that any ILP problem in the standard form can be polynomially reduced to some ILP problem in the canonical form, preserving m and Delta(A), but the reverse reduction is not always possible. More precisely, we define the class of generalized ILP problems in the standard form, which includes an additional group constraint, and prove the equivalence to ILP problems in the canonical form. We generalize known sparsity, proximity, and complexity bounds for ILP problems in the canonical form. Additionally, sometimes, we strengthen previously known results for ILP problems in the canonical form, and, sometimes, we give shorter proofs. Finally, we consider the special cases of m is an element of {0, 1). By this way, we give specialised sparsity, proximity, and complexity bounds for the problems on simplices, Knapsack problems and Subset-Sum problems.

关键词： integer linear programming Knapsack problem Subset-sum problem Group minimization problem Sparsity & proximity bounds Empty simplex

来源：评论

学校读者我要写书评

暂无评论

Revamping the Resilience and High Availability of 5G Core for 6G Ready Network Slices

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2024年第2期21卷 2287-2302页

作者： Vittal, Shwetha Sarkar, Sourav Franklin, A. Antony Indian Inst Technol Hyderabad Dept Comp Sci & Engn Hyderabad 502285 India

Current advancements in the design of the service-based architecture of 5G Core (5GC) are flexible to be deployed with Network Function Virtualization (NFV) in the form of network slices. While some slices tolerate the delay and some do not, this versatility of slice services imposes challenges to Mobile Network Operators in designing a robust, scalable, and yet resilient 5GC. Therefore, in this work, we build a self-resilient 5GC that not only addresses the scheduling requirements per slice type but also yields service satisfaction. Precisely, we build it as a combination of large integer linear programming based Column Generation (CG) and Artificial Intelligence based Deep Learning in a Closed Loop Automation with a Self Organizing Network paradigm. During unexpected situations of overload and failures of serving instances, the proposed CG technique in the work improves the scheduling and serving of control plane user requests by dropping 15% lesser user requests in delay-tolerant slices and 5% lesser in delay-sensitive slices, than the existing state-of-the-art solutions. With 95% learning accuracy, the Deep Learning-based Long Short Term Memory (LSTM) method predicts the availability of serving instances of the Network Functions (NFs) of the 5GC. Overall, by deriving the optimal number of serving instances for each NF of the 5GC, this blend of CG and AI in the 5GC not only contributes to efficient scaling and reconfiguration of the slices but also improves the resilience and High Availability of the 5GC. We believe that this proposed work is a highly promising solution for building Cognitive Autonomous Networks (CAN) of core side slices for upcoming Beyond 5G (B5G) and 6G in both cloud and edge deployments.

关键词： 5G core network slicing integer linear programming column generation deep learning long short term memory resilience high availability network function virtualization (NFV) cognitive autonomous networks (CAN)

来源：评论

学校读者我要写书评

暂无评论

Automating functional unit and register binding for synchoros CGRA platform

引用

DESIGN AUTOMATION FOR EMBEDDED SYSTEMS 2024年第2期28卷 155-186页

作者： Pudi, Dhilleswararao Tiwari, Utsav Boppu, Srinivas Yang, Yu Hemani, Ahmed Indian Inst Technol Bhubaneswar IITBBS Sch Elect Sci Bhubaneswar 752050 Odisha India Royal Inst Technol KTH Sch Elect Engn & Comp Sci Kistagangen 16 S-16440 Stockholm Sweden

Coarse-grain reconfigurable architectures, which provide high computing throughput, low cost, scalability, and energy efficiency, have grown in popularity in recent years. SiLago is a new VLSI design framework comprised of two coarse-grain reconfigurable fabrics: a dynamically reconfigurable resource array and a distributed memory architecture. It employs the Vesyla compiler to map streaming applications on these fabrics. Binding is a critical step in the high-level synthesis that maps operations and variables to functional units and storage elements in the design. It influences design performance metrics such as power, latency, area, etc. The current version of Vesyla does not support automatic binding, and it has to be specified manually through pragmas, which makes it less flexible. This paper proposes various approaches to automate the binding in Vesyla. We present a list scheduling-based approach to automate functional unit binding and an integer linear programming approach to automate register binding. Furthermore, we determine the binding of various basic linear algebraic subprogram and image processing tasks using the proposed approaches. Finally, a comparative analysis has been made between the automatic and manual binding concerning the power dissipation and latency for various benchmarks. The experimental results show that the proposed automatic binding consumes significantly less power for nearly the same latency as manual binding.

关键词： High-level synthesis Coarse-grain reconfigurable architecture Binding SiLago Vesyla integer linear programming Dynamically reconfigurable resource array Distributed memory architecture

来源：评论

学校读者我要写书评

暂无评论

引用

Autonomous Intelligent Systems 2025年第1期5卷 1-13页

作者： Chen, Kezhou Wang, Tao Zhuo, Huimin Cheng, Lianglun School of Computer Science and Technology Guangdong University of Technology Guangzhou510006 China School of Automation Guangdong University of Technology Guangzhou510006 China

Service Composition and Optimization Selection (SCOS) is crucial in Cloud Manufacturing (CMfg), but the uncertainties in service states and working environments pose challenges for existing QoS-based methods. Recently, digital twins have gained prominence in CMfg due to their predictive capabilities, enhancing the reliability of service composition. Heuristic algorithms are widely used in this field for their flexibility and compatibility with uncertain environments. This paper proposes the Whale-Goshawk Optimization Algorithm (WGO), which combines the Whale Optimization Algorithm (WOA) and Northern Goshawk Optimization Algorithm (NGO). A novel similar integer coding method, incorporating spatial feature information, addresses the limitations of traditional integer coding, while a whale-optimized prey generation strategy improves NGO’s global optimization efficiency. Additionally, a local search method based on similar integer coding enhances WGO’s local search ability. Experimental results demonstrate the effectiveness of the proposed approach. © The Author(s) 2025.

关键词： integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Flow-shop and job-shop robust scheduling problems with budgeted uncertainty

引用

European Journal of Operational Research 2025年第1期326卷 54-68页

作者： Juvin, Carla Houssin, Laurent Lopez, Pierre TBS Business School Toulouse France LAAS-CNRS Université de Toulouse CNRS Toulouse France ISAE-SUPAERO Université de Toulouse France

In this paper, we study different solution methods for two two-stage robust, multi-machine scheduling problems, namely permutation flow-shop and job-shop scheduling problems under uncertainty budget. Compact formulations of the problems are proposed and two decomposition approaches are presented: a Benders decomposition approach and a column and constraint generation approach. Computational experiments show that for small-sized instances, a compact formulation of the problem quickly yields optimal solutions. However, for larger instances, decomposition methods, particularly the column and constraint generation method with a master problem solved using constraint programming, provide better quality solutions. An acceleration method for the column and constraint generation algorithm is proposed. This method is generic and can be applied to any two-stage robust optimisation problem. © 2025 Elsevier B.V.

关键词： integer linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：