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

An integer linear programming approach for a class of bilinear integer programs

OPERATIONS RESEARCH LETTERS 2014年第3期42卷 226-230页

作者： Hu, Wuhua Tay, Wee Peng Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

We propose an integer Linear programming (ILP) approach for solving integer programs with bilinear objectives and linear constraints. Our approach is based on finding upper and lower bounds for the integer ensembles in the bilinear objective function, and using the bounds to obtain a tight ILP reformulation of the original problem, which can then be solved efficiently. Numerical experiments suggest that the proposed approach outperforms a latest iterative ILP approach, with notable reductions in the average solution time. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Bilinear integer programming integer linear programming integer quadratic programming Binary binary linearization Binary integer linearization Bipartite graph

来源：评论

学校读者我要写书评

暂无评论

New Models for Commercial Territory Design

引用

NETWORKS & SPATIAL ECONOMICS 2011年第3期11卷 487-507页

作者： Angelica Salazar-Aguilar, Maria Rios-Mercado, Roger Z. Cabrera-Rios, Mauricio Univ Autonoma Nuevo Leon Grad Program Syst Engn San Nicolas De Los Garza 66450 NL Mexico Univ Puerto Rico Dept Ind Engn Mayaguez PR 00681 USA

In this work, a series of novel formulations for a commercial territory design problem motivated by a real-world case are proposed. The problem consists on determining a partition of a set of units located in a territory that meets multiple criteria such as compactness, connectivity, and balance in terms of customers and product demand. Thus far, different versions of this problem have been approached with heuristics due to its NP-completeness. The proposed formulations are integer quadratic programming models that involve a smaller number of variables than heretofore required. These models have also enabled the development of an exact solution framework, the first ever derived for this problem, that is based on branch and bound and a cut generation strategy. The proposed method is empirically evaluated using several instances of the new quadratic models as well as of the existing linear models. The results show that the quadratic models allow solving larger instances than the linear counterparts. The former were also observed to require fewer iterations of the exact method to converge. Based on these results the combination of the quadratic formulation and the exact method are recommended to approach problem instances associated with medium-sized cities.

关键词： Mixed-integer linear programming integer quadratic programming Territory design Location Valid inequalities

来源：评论

学校读者我要写书评

暂无评论

Minimizing the tracking error of cardinality constrained portfolios

引用

COMPUTERS & OPERATIONS RESEARCH 2018年第Feb.期90卷 33-41页

作者： Mutunge, Purity Haugland, Dag Univ Bergen Dept Informat Bergen Norway

We study the problem of selecting a restricted number of shares included in a stock market index, such that the portfolio resembles the index as closely as possible. To measure the difference between the portfolio and the index, referred to as the tracking error, we use a quadratic function with the covariance matrix of the index returns as coefficient matrix. The problem is proved to be strongly NP-hard, and we give theoretical evidence that continuous relaxations of mixed integer quadratic programming (MIQP) formulations are likely to produce poor lower bounds on the tracking error. For fast computation of near-optimal portfolios, we demonstrate how the best-extension-by-one construction heuristic can be designed to run in time bounded by a fourth order polynomial. We also show that the running time of one iteration of the best-exchange-by one improvement heuristic is of the same order. Computational experiments applied to real-life stock market indices show that in instances where an index of less than 500 assets is to be tracked by a portfolio of 10 assets, a commercially available MIQP solver fails to reduce the integrality gap below 94% in 30 CPU-minutes. In contrast, the construction heuristic under study needs less than 30 CPU-seconds to produce a portfolio of 100 assets tracking an index of nearly 2000 assets. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Portfolio management Index tracking integer quadratic programming Heuristics

来源：评论

学校读者我要写书评

暂无评论

Utilizing soft constraints to enhance medical relation extraction from the history of present illness in electronic medical records

引用

JOURNAL OF BIOMEDICAL INFORMATICS 2018年 87卷 108-117页

作者： Chen, Li Li, Yuanju Chen, Weipeng Liu, Xinglong Yu, Zhonghua Zhang, Siyuan Sichuan Univ Dept Comp Sci Chengdu Sichuan Peoples R China Chengdu Univ TCM Sch Basic Med Chengdu Sichuan Peoples R China

Relation extraction between medical concepts from electronic medical records has pervasive applications as well as significance. However, previous researches utilizing machine learning algorithms judge the semantic types of medical concept pair mentions independently. In fact, different concept pair mentions in the same context are of dependencies which can provide beneficial evidences for identifying their relation types. To the best of our knowledge, only one study has considered such dependencies in discharge summaries. However, its hard constraints are not applied effectively to the History of Present Illness (HPI) in electronic Medical Records. According to the writing characteristics of HPI records, we generalize two regularities of dependencies among concept pairs mentioned in an HPI record to enhance the performance of relation extraction. We incorporate the two soft constraints corresponding to the regularities and the posterior probabilities returned by a local classifier into a joint inference process which applies integer quadratic programming method to carry out collective classification for all concept pair mentions in an HPI record. We implement four local classification models including support vector machine, logistics regression, random forest and piecewise convolutional neural networks to examine the performance of our approach. A series of experimental results demonstrate that our collective classification method has made a principal improvement and outperforms the other state-of-the-art methods.

关键词： Electronic medical record History of present illness Relation extraction integer quadratic programming Soft constraints

来源：评论

学校读者我要写书评

暂无评论

Lagrangian relaxation graph matching

引用

PATTERN RECOGNITION 2017年第0期61卷 255-265页

作者： Jiang, Bo Tang, Jin Cao, Xiaochun Luo, Bin Anhui Univ Sch Comp Sci & Technol 111 Jiu Long Rd Hefei 230601 Anhui Peoples R China Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing Peoples R China

Graph matching is a fundamental problem in computer vision area. Graph matching problem that incorporates pair-wise constraints can be formulated as an integer quadratic programming (IQP) problem with affine mapping constraint. Since it is known to be NP-hard, approximate relaxation methods are usually required to find approximate solutions. In this paper, we present a new effective graph matching relaxation method, called Lagrangian relaxation graph matching (LRGM), which aims to generate a relaxation model by incorporating the affine mapping constraint into the matching objective optimization. There are three main benefits of the proposed LRGM method: (1) The nonnegative affine mapping constraint encoding one-to-one mapping is naturally incorporated in LRGM relaxation via Lagrangian regularization. (2) By further adding a l(1)-norm constraint, LRGM can generate a sparse solution empirically and thus returns a desired discrete solution for original IQP matching problem. (3) An effective update algorithm is derived to solve the proposed LRGM model. Theoretically, the converged solution can be proven to be Karush-Kuhn-Tucker (KKT) optimal. Experimental results on both synthetic data and real-world image datasets show the effectiveness and benefits of the proposed LRGM method. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Graph matching integer quadratic programming Lagrangian relaxation Multiplicative update

来源：评论

学校读者我要写书评

暂无评论

integer quadratic OPTIMIZATION

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1985年第2期19卷 268-273页

作者： KORNER, F HUNGARIAN ACAD SCI INST COMP & AUTOMATH-1502 BUDAPESTHUNGARY

A branch and bound algorithm is considered to solve linearly constrained, integer quadratic optimization problems. The main result consists in making a rule by which it will be decided in every node of the branch and bound tree which variable is going to branch next such that only a small number of branch and bound nodes need to be investigated. If Fletcher's algorithm is applied to solve continuous partial problems, then only O(n[SUP2]) operations are required to find an 'advantageous' variable for branching. [ABSTRACT FROM AUTHOR]

关键词： branch and bound integer quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Ascent with quadratic assistance for the construction of exact experimental designs

引用

COMPUTATIONAL STATISTICS 2020年第2期35卷 775-801页

作者： Filova, Lenka Harman, Radoslav Comenius Univ Fac Math Phys & Informat Bratislava Slovakia Johannes Kepler Univ Linz Linz Austria

In the area of statistical planning, there is a large body of theoretical knowledge and computational experience concerning so-called optimal approximate designs of experiments. However, for an approximate design to be realizable, it must be converted into an exact, i.e., integer, design, which is usually done via rounding procedures. Although rapid, rounding procedures often yield worse exact designs than heuristics that do not require approximate designs at all. In this paper, we build on an alternative principle of utilizing optimal approximate designs for the computation of optimal, or nearly-optimal, exact designs. The principle, which we call ascent with quadratic assistance (AQuA), is an integer programming method based on the quadratic approximation of the design criterion in the neighborhood of the optimal approximate information matrix. To this end, we present quadratic approximations of all Kiefer's criteria with an integer parameter, including D- and A-optimality and, by a model transformation, I-optimality. Importantly, we prove a low-rank property of the associated quadratic forms, which enables us to use AQuA efficiently and apply it to large design spaces. We numerically demonstrate the robustness and superior performance of the proposed method for selected statistical models under various types of experimental constraints. We also show how can iterative application of AQuA be used for a stratified information-based subsampling of large datasets under a lower bound on the quality and an upper bound on the cost of the subsample.

关键词： Optimal design integer quadratic programming Experimental constraints Mixture designs Subsampling

来源：评论

学校读者我要写书评

暂无评论

ACROSS: A Framework for Multi-Cultural Interlinking of Web Taxonomies 16

ACROSS: A Framework for Multi-Cultural Interlinking of Web T...

引用

8th ACM Web Science Conference (WebSci)

作者： Boldyrev, Natalia Spaniol, Marc Weikum, Gerhard Max Planck Inst Informat Saarbrucken Germany Univ Caen Normandie Caen France

ISBN: (纸本)9781450342087

The Web hosts a huge variety of multi-cultural taxonomies. They encompass product catalogs of e-commerce, general-purpose knowledge bases and numerous domain-specific category systems. The "common denominator" of all these is their enormous diversity, which makes it infeasible to combine multiple taxonomies for ad-hoc tasks. To support the alignment of independently created Web taxonomies, we introduce the ACROSS framework. For mapping categories across different taxonomies, ACROSS harnesses instance-level features as well as distant supervision from an intermediate source like multiple Wikipedia editions. Our experiments with heterogeneous taxonomies for different domains demonstrate the viability of our approach and improvement over state-of-the-art baselines.

关键词： Multicultural Knowledge Bases Knowledge Taxonomies Alignment Methods integer Linear programming integer quadratic programming Label Propagation

来源：评论

学校读者我要写书评

暂无评论

Parameterized Algorithms for Minimum Sum Vertex Cover 16th

Parameterized Algorithms for Minimum Sum Vertex Cover

引用

16th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Aute, Shubhada Panolan, Fahad Indian Inst Technol Hyderabad Sangareddy India Univ Leeds Sch Comp Leeds W Yorkshire England

ISBN: (纸本)9783031556005;9783031556012

Minimum sum vertex cover of an n-vertex graph G is a bijection phi : V (G) -> [n] that minimizes the cost Sigma({u,v}is an element of E(G)) min{phi(u), phi(v)}. Finding a minimum sum vertex cover of a graph (the MSVC problem) is NP-hard. MSVC is studied well in the realm of approximation algorithms. The best-known approximation factor in polynomial time for the problem is 16/9 [Bansal, Batra, Farhadi, and Tetali, SODA 2021]. Recently, Stankovic [APPROX/RANDOM 2022] proved that achieving an approximation ratio better than 1.014 for MSVC is NP-hard, assuming the Unique Games Conjecture. We study the MSVC problem from the perspective of parameterized algorithms. The parameters we consider are the size of a minimum vertex cover and the size of a minimum clique modulator of the input graph. We obtain the following results. - MSVC can be solved in 2(2O(k)) n(O(1)) time, where k is the size of a minimum vertex cover. - MSVC can be solved in f(k) . n(O(1)) time for some computable function f, where k is the size of a minimum clique modulator.

关键词： FPT Vertex Cover integer quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Aggregate Planning for Multi-product Assembly Lines with Reconfigurable Cells

Aggregate Planning for Multi-product Assembly Lines with Rec...

引用

IFIP WG 5.7 International Conference on Advances in Production Management Systems (APMS)

作者： Uzunosmanoglu, Mehmet Raa, Birger Limere, Veronique De Cock, Alexander Singh, Yogang Lopez, Angel J. Gautama, Sidharta Cottyn, Johannes Univ Ghent Dept Ind Syst Engn & Prod Design Ghent Belgium Flanders Make ISyE CoreLab Lommel Belgium Univ Ghent Dept Business Informat & Operat Management Ghent Belgium Flanders Make CodesingS CoreLab Lommel Belgium

ISBN: (纸本)9783030859022;9783030859015

This paper deals with aggregate planning of Reconfigurable Assembly Lines (RAL). The assembly line considered in this paper consists of hexagonal cells. These have multiple slots where processing modules can be inserted to perform certain operations. In addition, each cell has a single central slot where a central module can be inserted for inter-cellular and intra-cellular transportation of parts. Multiple products with different assembly sequences must be handled over multiple planning periods. An integer quadratic programming (IQP) model is proposed to solve the following problems simultaneously: (i) assigning processing modules and a central module to the cells;(ii) installation of the cells and conveyors between the cells;and (iii) routing products, ensuring that availability of the resources is not exceeded. The assembly line should be reconfigured over time to adapt to possible product functionality and demand changes at minimum reconfiguration, operational and material handling costs while ensuring the demand is met within each period. The IQP model is implemented and solved for an illustrative problem and its extensions using Gurobi.

关键词： Reconfigurable assembly lines Aggregate planning integer quadratic programming Optimisation models

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：