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

Exact algorithm for concave knapsack problems: Linear underestimation and partition method

JOURNAL OF GLOBAL OPTIMIZATION 2005年第1期33卷 15-30页

作者： Sun, XL Wang, FL Li, D Shanghai Univ Dept Math Shanghai 200444 Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China

integer programming problems with a concave cost function are often encountered in optimization models involving economics of scale. In this paper, we propose an efficient exact algorithm for solving concave knapsack problems. The algorithm consists of an iterative process between finding lower and upper bounds by linearly underestimating the objective function and performing domain cut and partition by exploring the special structure of the problem. The lower bound is improved iteratively via cutting and partitioning the domain. This iteration process converges to the optimality in a finite number of steps. Promising computational results are reported for large-scale concave knapsack problems with up to 1200 integer variables. Comparison results with other existing methods in the literature are also presented.

关键词： concave knapsack problem domain cut domain partition linear underestimation nonlinear integer programming

来源：评论

学校读者我要写书评

暂无评论

Multi-task entity linking with supervision from a taxonomy

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2023年第10期65卷 4335-4358页

作者： Wang, Xuwu Chen, Lihan Zhu, Wei Ni, Yuan Xie, Guotong Yang, Deqing Xiao, Yanghua Fudan Univ Sch Comp Sci Shanghai Peoples R China Shanghai Key Lab Data Sci Shanghai Peoples R China East China Normal Univ Sch Comp Sci Shanghai Peoples R China Pingan Hlth Tech Shanghai Peoples R China Fudan Univ Sch Data Sci Shanghai Peoples R China

Entity linking is the task of resolving ambiguous mentions in documents to their referent entities in a knowledge graph (KG). Existing solutions mainly rely on three kinds of information: local contextual similarity, global coherence, and prior probability. But the information of the mentions' types is rarely utilized, which is helpful for precise entity linking. That is to say, if the type information of a mention is obtained from a mention classifier, we can exclude candidate entities with different types. However, the key challenge of realizing it lies in obtaining the type labels with appropriate granularity and performing entity linking with the error propagated from the mention classifier. To solve the challenges, we propose a model named type-oriented multi-task entity linking (TMTEL). First, we select types with appropriate granularity from the taxonomy of a KG, which is modeled as a nonlinear integer programming problem. Second, we use a multi-task learning framework to incorporate the selected types into entity linking. The type information is used to enhance the representation of the mentions' context, which is more robust to the errors of the mention classifier. Experimental results show that our model outperforms multiple existing solutions.

关键词： Entity linking Taxonomy Mention classification Knowledge graph Multi-task learning nonlinear integer programming

来源：评论

学校读者我要写书评

暂无评论

Reliability optimisation of FMS with spare tooling

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2000年第8期16卷 551-558页

作者： Altumi, AA Philipose, AM Taboun, SM Univ Windsor Windsor ON N9B 3P4 Canada

Tool reliability plays an important role in the performance cmd justification of flexible manufacturing systems (FMS). Failure of a single tool can cause downtimes over the Entire system. This results in missing due dates, and inferior products. Therefore, in order to justify the large capital investment associated with FMS, the system must perform in a reliable manner to give an acceptable or expected rate of return on capital. FMS reliability should be studied at the planning and design stages, as tool failures pose a major obstacle to achieving this objective. In this paper, a mathematical model has been developed to determine the spares requirement of the tooling system in an FMS, so that the desired system reliability is achieved and the cost is minimised. The influence of tool sharing on cost, reliability, spares requirement, and tool magazine capacity of the FMS are analysed. The tools and tool transporter are subject to general failure distributions.

关键词： flexible manufacturing systems nonlinear integer programming reliability optimisation spare requirements tool sharing

来源：评论

学校读者我要写书评

暂无评论

The design of service systems with queueing time cost, workload capacities and backup service

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1998年第1期104卷 201-217页

作者： Amiri, A Weber State Univ Coll Business Ogden UT 84408 USA

This paper studies a reliable service system design problem that involves locating service facilities, determining their number and capacities and assigning user nodes to those facilities. The goal is to minimize total costs made of the costs of accessing facilities by users and waiting for service at these facilities as well as the cost of setting up and operating the facilities. The service system is designed in such a way that backup service is provided to user nodes while controlling facility workload. This problem arises mainly in the area of telecommunication network design. But it is quite general and can be encountered in several planning contexts such as transportation planning, siting of emergency service facilities and refuse collection and disposal in the public sector. The paper represents a significant improvement over previous research by presenting a unified model of the problem that includes the number, locations, and capacities of service facilities as variables to be determined, incorporates in the total cost to be minimized the user waiting time (queueing) cost, and provides backup service to user nodes. An integer programming formulation of the problem with a nonlinear objective function is presented. Two heuristic solution procedures based on a Lagrangean relaxation of the problem are developed. Extensive computational results across a variety of problem structures are reported. These results indicate that the second solution procedure is very effective for a wide range of problem structures and traffic loads. (C) 1998 Elsevier Science B.V.

关键词： design of service system reliability nonlinear integer programming Lagrangean relaxation heuristics

来源：评论

学校读者我要写书评

暂无评论

LEO satellites selection-based computation offloading algorithm in aircraft-satellite multi-access edge computing networks

引用

COMPUTER COMMUNICATIONS 2024年 223卷 115-127页

作者： Zhang, Jiadong Zhang, Ruidong Shi, Wenxiao Jilin Univ Coll Commun Engn Changchun 130012 Peoples R China

The emergence of sixth -generation (6G) mobile networks and non -terrestrial networks (NTNs) has led to increased interest in low Earth orbit (LEO) satellite -based communication networks for their potential to provide global coverage and ubiquitous connectivity. In this paper, we investigate the LEO satellites selectionbased computation offloading problem in the aircraft-satellite multi-access edge computing (ASMEC) network, where LEO satellites and edge computing processors are integrated to provide ubiquitous and low -latency communication and computation services for aircraft during flights. In contrast to most existing works, which directly assume a fixed number of satellites or orbits in satellite -based MEC networks, we investigate the problem of how many satellites and which satellites to select in the ASMEC network. Our objective is to minimize the average total time delay of tasks during aircraft-satellite computation offloading. To achieve this, we formulate a nonlinear integer programming (NLIP) problem and propose the LEO satellites selectionbased computation offloading (LSSBCO) algorithm to solve it, which includes the shortest aircraft-satellite distance based access satellite selection (ASS -SD) algorithm and the nearest k ( t ) neighboring satellites selection (NSS- k ( t ) ) algorithm. We evaluate the performance of the LSSBCO algorithm in terms of the average total time delay, the maximum throughput, the average aircraft-satellite distance, the average connection duration, and the number of satellite handovers. Numerical results show that the proposed algorithm outperforms the benchmark algorithms with a lower average total time delay.

关键词： Aircraft-satellite communication Computation offloading LEO satellites selection Multi-access edge computing nonlinear integer programming Queuing system

来源：评论

学校读者我要写书评

暂无评论

Optimal response to epidemics and cyber attacks in networks

引用

NETWORKS 2015年第2期66卷 145-158页

作者： Goldberg, Noam Leyffer, Sven Safro, Ilya Bar Ilan Univ Dept Management IL-52900 Ramat Gan Israel Argonne Natl Lab MCS Div Argonne IL 60439 USA Clemson Univ Dept Comp Sci Clemson SC 29634 USA

This article introduces novel formulations for optimally responding to epidemics and cyber attacks in networks. In our models, at a given time period, network nodes (e.g., users or computing resources) are associated with probabilities of being infected, and each network edge is associated with some probability of propagating the infection. A decision maker would like to maximize the network's utility;keeping as many nodes open as possible, while satisfying given bounds on the probabilities of nodes being infected in the next time period. The model's relation to previous deterministic optimization models and to both probabilistic and deterministic asymptotic models is explored. Initially, maintaining the stochastic independence assumption of previous work, we formulate a nonlinear integer program with high-order multilinear terms. We then propose a quadratic formulation that provides a lower bound and feasible solution to the original problem. Further motivation for the quadratic model is given by showing that it alleviates the assumption of stochastic independence. The quadratic formulation is then linearized in order to be solved by standard integer programming solvers. We develop valid inequalities for the resulting formulations. (c) 2015 Wiley Periodicals, Inc.

关键词： nonlinear integer programming cutting planes network optimization probability bounds cybersecurity epidemiology

来源：评论

学校读者我要写书评

暂无评论

On the complexity of quasiconvex integer minimization problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第4期73卷 761-788页

作者： Chirkov, A. Yu. Gribanov, D. V. Malyshev, D. S. Pardalos, P. M. Veselov, S. I. Zolotykh, N. Yu. Lobachevsky State Univ Nizhny Novgorod 23 Gagarina Ave Nizhnii Novgorod 603950 Russia Natl Res Univ Higher Sch Econ 25-12 Bolshaja Pecherskaja Ulitsa Nizhnii Novgorod 603155 Russia Univ Florida 401 Weil HallPOB 116595 Gainesville FL 32611 USA

In this paper, we consider the class of quasiconvex functions and its proper subclass of conic functions. The integer minimization problem of these functions is considered, assuming that the optimized function is defined by the comparison oracle. We will show that there is no a polynomial algorithm on logR to optimize quasiconvex functions in the ball of radius R using only the comparison oracle. On the other hand, if the optimized function is conic, then we show that there is a polynomial on logR algorithm (the dimension is fixed). We also present an exponential on the dimension lower bound for the oracle complexity of the conic function integer optimization problem. Additionally, we give examples of known problems that can be polynomially reduced to the minimization problem of functions in our classes.

关键词： nonlinear integer programming Conic functions Quasiconvex functions Quasiconvex polynomials Convex functions Comparison oracle Oracle model Complexity

来源：评论

学校读者我要写书评

暂无评论

A Novel nonlinear programming Model for Distribution Protection Optimization

引用

IEEE TRANSACTIONS ON POWER DELIVERY 2009年第4期24卷 1951-1958页

作者： Zambon, Eduardo Bossois, Debora Z. Garcia, Berilhes B. Azeredo, Elias F. Univ Fed Espirito Santo Dept Comp Sci BR-29060900 Vitoria ES Brazil ESCELSA Cent Util Espirito Santo BR-29161500 Carapina Serra Brazil

This paper presents a novel nonlinear binary programming model designed to improve the reliability indices of a distribution network. This model identifies the type and location of protection devices that should be installed in a distribution feeder and is a generalization of the classical optimization models given in the literature. This new approach is more flexible and leads to better placement solutions. Numerical results of the tests performed on real feeders are presented for analysis. Furthermore, we make the reliability data of the 36 feeders that were used in our work available to the research community.

关键词： nonlinear integer programming power distribution protection power distribution reliability

来源：评论

学校读者我要写书评

暂无评论

AN ACCELERATED COVERING RELAXATION ALGORITHM FOR SOLVING 0-1 POSITIVE POLYNOMIAL PROGRAMS

引用

MATHEMATICAL programming 1982年第3期22卷 350-357页

作者： GRANOT, D GRANOT, F VAESSEN, W UNIV BRITISH COLUMBIA DEPT COMP SCIVANCOUVER V6T 1W5BCCANADA

The purpose of this note is to present an accelerated algorithm for solving 0–1 positive polynomial (PP) problems. Like our covering relaxation algorithm (Management Science 1979), the accelerated algorithm is a cutting plane method, which uses the linear set covering problem as a relaxation for PP. However, a unique and novel feature of the accelerated algorithm is that it attempts to generate cutting planes from heuristic solutions to the set covering problem whenever possible. Computational results reveal that this strategy of generating cutting planes has led to a significant reduction in the computational time required to solve a PP problem.

关键词： 0–1 programming nonlinear integer programming Cutting Planes Heuristics

来源：评论

学校读者我要写书评

暂无评论

Designing a distributed database on a local area network: a methodology and decision support system

引用

INFORMATION AND SOFTWARE TECHNOLOGY 2000年第3期42卷 171-184页

作者： Lee, H Park, YK Jang, G Huh, SY Korea Adv Inst Sci & Technol Grad Sch Management Corp Informat Syst Lab Dongdaemoon Gu Seoul 130012 South Korea LG LCD Ltd Kangnam Gu Seoul 135280 South Korea Oracle Korea Ltd Nam Gu Ulsan 680030 South Korea Korea Adv Inst Sci & Technol Grad Sch Management Database Applicat Lab Dongdaemoon Gu Seoul 130012 South Korea

Local area networks (LANs) are important for an enterprise to hold a competitive edge. Many companies have therefore converted terminal-based computing systems to LAN-based distributed data processing systems. This paper proposes a design methodology for distributed databases connected by a LAN. Two primary objectives of the methodology are: (i) to allocate data files and workload among heterogeneous servers;and (ii) to determine the number of servers to satisfy the response time required for processing each transaction. The file and workload allocation decision is formulated as a nonlinear zero-one integer programming problem. This problem is proven to be NP-complete. A heuristic is developed to solve this problem effectively. A decision support system is implemented and an example is solved to illustrate the practical usefulness of the system. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： distributed database decision support system local area network file and workload allocation nonlinear integer programming local processing overhead server service capacity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：