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

integer programming-based non-uniform window decoding schedules for spatially coupled low-density parity-check codes

引用

IET COMMUNICATIONS 2022年第17期16卷 2019-2035页

作者： Khittiwitchayakul, Sirawit Phakphisut, Watid Supnithi, Pornchai King Mongkuts Inst Technol Ladkrabang Sch Engn Bangkok 10520 Thailand

Spatially coupled low-density parity-check (SC-LDPC) codes generally use a window decoding scheme, which is known to yield a near-optimal decoding, compared to full block decoding. Recently, a non-uniform schedule has been proposed to eliminate unnecessary updates of variable nodes within a window: this schedule is generated based on the behaviour of variable node updates analysed by density evolution. Here, the authors present a new non-uniform schedule based on integer programming, whereby the objective functions and constraints are derived from a protograph-based extrinsic information transfer chart. Our design is more flexible than the previous design, because the integer programming-based design allows reduction of update numbers and performance losses through the constraints function, whereas the previous design requires observation of variable node update behaviour. The authors report the performance of their designs of non-uniform schedules in additive white Gaussian noise (AWGN) and inter-symbol interference (ISI) channels. Particularly, in the ISI channel, the authors' non-uniform schedules are designed with cooperative decoding between a Bahl-Cocke-Jelinek-Raviv (BCJR) detector and an SC-LDPC decoder.

关键词： integer programming-based design block decoding protograph-based extrinsic information transfer chart additive white Gaussian noise channels Bahl-Cocke-Jelinek-Raviv detector SC-LDPC decoder nonuniform window decoding schedules AWGN channels telecommunication scheduling density evolution parity check codes integer programming decoding intersymbol interference channels channel coding intersymbol interference cooperative communication spatially coupled low-density parity-check codes near-optimal decoding variable node update behaviour ISI channels low-density parity-check codes BCJR detector

来源：评论

学校读者我要写书评

暂无评论

A mixed-integer programming formulation for optimizing the double row layout problem

引用

OPTIMIZATION METHODS & SOFTWARE 2024年第6期39卷 1428-1444页

作者： Amaral, Andre R. S. Fed Univ Espirito Santo UFES Grad Sch Comp Sci BR-29075910 Vitoria Brazil

The Double Row Layout Problem (DRLP) asks for an arrangement of machines on both sides of a straight line corridor so as to minimize the total cost for transferring materials among machines. The DRLP is NP-Hard and has practical relevance, specially in manufacturing systems design. In this paper, we drastically reduce the time required to solve the problem by constructing a new and effective mixed-integer linear programming (MILP) model of the DRLP. The new model was obtained by reformulating an existing MILP model. This includes tightening some constraints, introducing new variables, implementing constraints to link the new and original variables;and adding valid inequalities and a valid system of equations. To reduce the size of the reformulated model, we eliminate several of the new introduced variables by a substitution using the system of equations. The computational results demonstrate that the proposed model requires considerably smaller computational times compared to the ones in the literature. As a consequence, optimal solutions can now be efficiently found for larger instances of the problem. Previous studies have been able to optimally solve, within reasonable time, instances with size up to 16 machines, while with the new model four instances with 20 machines could be optimally solved.

关键词： integer programming discrete optimization facility layout

来源：评论

学校读者我要写书评

暂无评论

From approximate to exact integer programming

引用

MATHEMATICAL programming 2024年第1期210卷 223-241页

作者： Dadush, Daniel Eisenbrand, Friedrich Rothvoss, Thomas Ctr Wiskunde & Informat CWI Amsterdam Netherlands Ecole Polytech Fed Lausanne EPFL Lausanne Switzerland Univ Washington Seattle WA 98195 USA

Approximate integer programming is the following: For a given convex body K subset of R-n, either determine whether K boolean AND Z(n) is empty, or find an integer point in the convex body 2 center dot (K - c)+ c which is K, scaled by 2 from its center of gravity c. Approximate integer programming can be solved in time 2(O(n)) while the fastest known methods for exact integer programming run in time 2(O(n)) center dot n(n). So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point x* is an element of (K n Z(n)) can be found in time 2(O(n)), provided that the remainders of each component x(i)* mod l for some arbitrarily fixed l >= 5(n + 1) of x* are given. The algorithm is based on a cutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a 2(O(n)) n(n) algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a new asymmetric approximate Caratheodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equation-standard form Ax = b, 0 <= x <= u, x is an element of Z(n). Such a problem can be reduced to the solution of Pi(i) O(log u(i) + 1) approximate integer programming problems. This implies, for example that knapsack or subset-sum problems with polynomial variable range 0 <= x(i) <= p(n) can be solved in time (log n)(O(n)). For these problems, the best running time so far was n(n) center dot 2(O(n)).

关键词： integer programming Lattices Convex geometry

来源：评论

学校读者我要写书评

暂无评论

Optimizing Connected Components Graph Partitioning With Minimum Size Constraints Using integer programming and Spectral Clustering Techniques

引用

NETWORKS 2024年第3期85卷 245-260页

作者： Cordero, Mishelle Miniguano-Trujillo, Andres Recalde, Diego Torres, Ramiro Vaca, Polo Escuela Politec Nacl Res Ctr Math Modelling ModeMat Quito Ecuador Univ Edinburgh Maxwell Inst Math Sci Edinburgh Scotland Heriot Watt Univ Edinburgh Scotland Escuela Politec Nacl Dept Math Quito Ecuador

In this work, a graph partitioning problem in a fixed number of connected components is considered. Given an undirected graph with costs on the edges, the problem consists of partitioning the set of nodes into a fixed number of subsets with minimum size, where each subset induces a connected subgraph with minimal edge cost. The problem naturally surges in applications where connectivity is essential, such as cluster detection in social networks, political districting, sports team realignment, and energy distribution. Mixed integer programming formulations together with a variety of valid inequalities are demonstrated and computationally tested. An assisted column generation approach by spectral clustering is also proposed for this problem with additional valid inequalities. Finally, the methods are tested for several simulated instances, and computational results are discussed. Overall, the proposed column generation technique enhanced by spectral clustering offers a promising approach to solve clustering and partitioning problems.

关键词： column generation combinatorial optimization graph partitioning integer programming mixed integer programming spectral clustering

来源：评论

学校读者我要写书评

暂无评论

A Customized Augmented Lagrangian Method for Block-Structured integer programming

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2024年第12期46卷 9439-9455页

作者： Wang, Rui Zhang, Chuwen Pu, Shanwen Gao, Jianjun Wen, Zaiwen Southwestern Univ Finance & Econ Sch Math Chengdu 611130 Peoples R China Great Bay Inst Adv Study Ctr Intelligent Comp Dongguan 523000 Peoples R China Peking Univ Beijing Int Ctr Math Res Ctr Machine Learning Res Beijing 100871 Peoples R China Peking Univ Changsha Inst Comp & Digital Econ Beijing 100871 Peoples R China Shanghai Univ Finance & Econ Sch Informat Management & Engn Shanghai 200433 Peoples R China

integer programming with block structures has received considerable attention recently and is widely used in many practical applications such as train timetabling and vehicle routing problems. It is known to be NP-hard due to the presence of integer variables. We define a novel augmented Lagrangian function by directly penalizing the inequality constraints and establish the strong duality between the primal problem and the augmented Lagrangian dual problem. Then, a customized augmented Lagrangian method is proposed to address the block-structures. In particular, the minimization of the augmented Lagrangian function is decomposed into multiple subproblems by decoupling the linking constraints and these subproblems can be efficiently solved using the block coordinate descent method. We also establish the convergence property of the proposed method. To make the algorithm more practical, we further introduce several refinement techniques to identify high-quality feasible solutions. Numerical experiments on a few interesting scenarios show that our proposed algorithm often achieves a satisfactory solution and is quite effective.

关键词： integer programming augmented Lagrangian method block coordinate descent convergence

来源：评论

学校读者我要写书评

暂无评论

Shapley-Scarf Housing Markets: Respecting Improvement, integer programming, and Kidney Exchange

引用

MATHEMATICS OF OPERATIONS RESEARCH 2024年第3期49卷 1938-1972页

作者： Biro, Peter Klijn, Flip Klimentova, Xenia Viana, Ana Inst Econ Ctr Econ & Reg Stud H-1097 Budapest Hungary Corvinus Univ Budapest Inst Operat & Dec Sci H-1093 Budapest Hungary Inst Econ Anal IAE CSIC Barcelona 08193 Spain Barcelona Sch Econ Barcelona 08005 Spain Inst Syst & Comp Engn Technol & Sci P-4200465 Porto Portugal Polytech Porto Sch Engn P-4249015 Porto Portugal

In a housing market of Shapley and Scarf, each agent is endowed with one indivisible object and has preferences over all objects. An allocation of the objects is in the (strong) core if there exists no (weakly) blocking coalition. We show that, for strict preferences, the unique strong core allocation "respects improvement"-if an agent's object becomes more desirable for some other agents, then the agent's allotment in the unique strong core allocation weakly improves. We extend this result to weak preferences for both the strong core (conditional on nonemptiness) and the set of competitive allocations (using probabilistic allocations and stochastic dominance). There are no counterparts of the latter two results in the two-sided matching literature. We provide examples to show how our results break down when there is a bound on the length of exchange cycles. Respecting improvements is an important property for applications of the housing markets model, such as kidney exchange: it incentivizes each patient to bring the best possible set of donors to the market. We conduct computer simulations using markets that resemble the pools of kidney exchange programs. We compare the game-theoretical solutions with current techniques (maximum size and maximum weight allocations) in terms of violations of the respecting improvement property. We find that game-theoretical solutions fare much better at respecting improvements even when exchange cycles are bounded, and they do so at a low efficiency cost. As a stepping stone for our simulations, we provide novel integer programming formulations for computing core, competitive, and strong core allocations.

关键词： housing market respecting improvement core competitive allocations integer programming kidney exchange programs

来源：评论

学校读者我要写书评

暂无评论

integer programming Methods to Identify Nash Equilibrium Solutions for Platform-Based Scheduling Games

引用

Operations Research Forum 2023年第4期4卷 94页

作者： Cho, Lucky Sharkey, Thomas C. School of Industrial Engineering Purdue University West Lafayette IN United States Department of Industrial Engineering Clemson University Clemson SC United States

This paper proposes an integer programming approach to examining Nash equilibrium solutions of a game modeling freelancer platforms. This Platform-Based Scheduling Game is played by the clients who choose a single freelancer that processes their jobs and the freelancers create a schedule of work based on the clients who choose them and their preferences. In order to identify a Nash equilibrium schedule, a schedule in which no clients change their choice of freelancers based on every other client’s choice, integer programming is utilized. We create a set of integer programming constraints where there exists a one-to-one correspondence between a Nash equilibrium of the game and a feasible solution to the integer program. The one-to-one correspondence allows the integer program to find the optimal Nash equilibrium schedules for objectives that model the considerations of the platform, freelancers, and clients. It also allows us to precisely calculate the price of anarchy and price of stability, and evaluate the loss in objective function value for one stakeholder of the game when the game is optimized for another stakeholder. We show that the decentralized matching performs well for the clients and the freelancers compared to the centralized optimal matching (that arises when we do not consider the clients as independent decision-makers) but the platform can suffer heavily from allowing clients autonomy in their decision making. © 2023, The Author(s), under exclusive licence to Springer Nature Switzerland AG.

关键词： Game theory integer programming Price of anarchy Price of stability Scheduling

来源：评论

学校读者我要写书评

暂无评论

Molecular Design Based on integer programming and Splitting Data Sets by Hyperplanes

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2024年第5期21卷 1529-1541页

作者： Zhu, Jianshen Azam, Naveed Ahmed Haraguchi, Kazuya Zhao, Liang Nagamochi, Hiroshi Akutsu, Tatsuya Kyoto Univ Dept Appl Math & Phys Kyoto 6068501 Japan Quaid i Azam Univ Dept Math Islamabad 45320 Pakistan Kyoto Univ Grad Sch Adv Integrated Studies Human Survavibil Kyoto 6068306 Japan Kyoto Univ Inst Chem Res Bioinformat Ctr Uji 6110011 Japan

A novel framework for designing the molecular structure of chemical compounds with a desired chemical property has recently been proposed. The framework infers a desired chemical graph by solving a mixed integer linear program (MILP) that simulates the computation process of two functions: a feature function defined by a two-layered model on chemical graphs and a prediction function constructed by a machine learning method. To improve the learning performance of prediction functions in the framework, we design a method that splits a given data set C into two subsets C-(i), i = 1, 2 by a hyperplane in a chemical space so that most compounds in the first (resp., second) subset have observed values lower (resp., higher) than a threshold theta. We construct a prediction function psi to the data set C by combining prediction functions psi(i), i = 1, 2 each of which is constructed on C-(i) independently. The results of our computational experiments suggest that the proposed method improved the learning performance for several chemical properties to which a good prediction function has been difficult to construct.

关键词： Machine learning integer programming chemo-informatics materials informatics QSAR/QSPR molecular design

来源：评论

学校读者我要写书评

暂无评论

Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming

引用

MATHEMATICAL programming 2024年第1-2期208卷 497-531页

作者： Brianski, Marcin Koutecky, Martin Kral, Daniel Pekarkova, Kristyna Schroder, Felix Jagiellonian Univ Fac Math & Comp Sci Theoret Comp Sci Dept Krakow Poland Charles Univ Prague Comp Sci Inst Prague Czech Republic Masaryk Univ Fac Informat Brno Czech Republic Charles Univ Prague Fac Math & Phys Prague Czech Republic

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A;both these parameterization imply that A is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the l(1)-norm of the Graver basis is bounded by a function of the maximum l(1)-norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the l(1)-norm of the Graver basis of the constraint matrix, when parameterized by the l(1)-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.

关键词： integer programming Width parameters Matroids Graver basis Tree-depth Fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

A droplet-intermixing printing method for high-uniformity pixel ink volume control based on integer programming

引用

JOURNAL OF MANUFACTURING PROCESSES 2024年 124卷 638-649页

作者： Wang, Yixin Chen, Jiankui Li, Yiqun Yin, Zhouping Huazhong Univ Sci & Technol State Key Lab Intelligent Mfg Equipment & Technol Wuhan 430074 Peoples R China

Inkjet printing is a promising technology for new display mass production. However, a major challenge in inkjet printing applications is pixel ink volume nonuniformity caused by the volume error of droplets ejected from multiple nozzles. This nonuniformity can lead to nonuniform pixel film thickness and Mura defects in a display panel. To address this issue, an integer programming-based droplet-intermixing printing method for highuniformity pixel ink volume control is proposed in this study. The printing method is used to homogenize the volume of ink deposited in each pixel by intermixing droplets from different nozzles to improve the whole-panel uniformity. To ensure that the droplet intermixing results meet the printing process requirements, a specific scheduling and printing planning model for the method is established. According to the droplet volume from each nozzle and the printing pattern, the most efficient printing path and nozzle ejection action are obtained by the established model while meeting the volume uniformity requirement of pixel ink. Experiments show that the proposed printing method can realize pixel film thickness error control under +/- 6 nm on a 400 cm(2 )display substrate, and the uniformity of different pixels is less than +/- 4.62 %. Compared with traditional method, the achieved uniformity is improved at 45.4 % under the same conditions. This method has been applied in printed display manufacturing equipment and achieved good results.

关键词： Printed display Inkjet printing Pixel ink volume control Droplet-intermixing printing method integer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：