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

0-1 multilinear programming as a unifying theory for LAD pattern generation

DISCRETE APPLIED MATHEMATICS 2017年 218卷 21-39页

作者： Yan, Kedong Ryoo, Hong Seo Korea Univ Grad Sch Informat Management & Secur Dept Informat Management Engn 145 Anam Ro Seoul 02841 South Korea Korea Univ Sch Ind Management Engn Coll Engn 145 Anam Ro Seoul 02841 South Korea

This paper revisits the Boolean logical requirement of a pattern and develops 0-1 multi linear programming (MP) models for (Pareto-)optimal patterns for logical analysis of data (LAD). We show that all existing and also new pattern generation models can naturally be obtained from the MP models via linearization techniques for 0-1 multilinear functions. Furthermore, 0-1 MP provides an insight for understanding how different and independently developed models for a particular type of pattern are inter-related. These show that 0-1 MP presents a unifying theory for pattern generation in LAD. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Boolean logic Logical analysis of data Pattern generation multilinear programming 0-1 linearization

来源：评论

学校读者我要写书评

暂无评论

Using mathematical programming to solve Factored Markov Decision Processes with Imprecise Probabilities

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2011年第7期52卷 1000-1017页

作者： Delgado, Karina Valdivia de Barros, Leliane Nunes Cozman, Fabio Gagliardi Sanner, Scott Univ Sao Paulo Escola Artes Ciencias & Humanidades BR-05508 Sao Paulo Brazil Univ Sao Paulo Inst Matemat & Estat BR-05508 Sao Paulo Brazil Univ Sao Paulo Escola Politecn BR-05508 Sao Paulo Brazil Australian Natl Univ Canberra ACT 2601 Australia NICTA Canberra ACT 2601 Australia

This paper investigates Factored Markov Decision Processes with Imprecise Probabilities (MDPIPs);that is, Factored Markov Decision Processes (MDPs) where transition probabilities are imprecisely specified. We derive efficient approximate solutions for Factored MDPIPs based on mathematical programming. To do this, we extend previous linear programming approaches for linear approximations in Factored MDPs, resulting in a multilinear formulation for robust "maximin" linear approximations in Factored MDPIPs. By exploiting the factored structure in MDPIPs we are able to demonstrate orders of magnitude reduction in solution time over standard exact non-factored approaches, in exchange for relatively low approximation errors, on a difficult class of benchmark problems with millions of states. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Imprecise Markov Decision Processes (MDPIPs) Probabilistic planning multilinear programming

来源：评论

学校读者我要写书评

暂无评论

Computing lower and upper expectations under epistemic independence

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2007年第3期44卷 244-260页

作者： de Campos, Cassio Polpo Cozman, Fabio Gagliardi Univ Sao Paulo USP Leste Escola Artes Ciencias & Humanidades BR-03828000 Sao Paulo Brazil Univ Sao Paulo Escola Politecn Sao Paulo Brazil

This paper investigates the computation of lower/upper expectations that must cohere with a collection of probabilistic assessments and a collection of judgements of epistemic independence. New algorithms, based on multilinear programming, are presented, both for independence among events and among random variables. Separation properties of graphical models are also investigated. (C) 2006 Elsevier Inc. All rights reserved.

关键词： sets of probability measures concepts of independence imprecise probabilities epistemic independence multilinear programming

来源：评论

学校读者我要写书评

暂无评论

An Approximation Algorithm for Sharing-Aware Virtual Machine Revenue Maximization

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2021年第1期14卷 1-15页

作者： Rampersaud, Safraz Grosu, Daniel Wayne State Univ Dept Comp Sci 5057 Woodward Ave Detroit MI 48202 USA

Cloud providers face the challenge of efficiently managing their infrastructure through minimizing resource consumption while allocating service requests such that their revenue is maximized. Solutions addressing this challenge should consider the sharing of memory pages among virtual machines (VMs) and the available capacity of each type of requested resources. We provide such solution by designing a greedy approximation algorithm for solving the sharing-aware virtual machine revenue maximization (SAVMRM) problem. The SAVMRM problem requires determining the set of VMs that can be instantiated on a given server such that the revenue derived from hosting the VMs is maximized. In addition, we model the SAVMRM problem as a multilinear binary program and optimally solve it, while accounting for page sharing and multiple resource constraints. We determine and analyze the approximability properties of our proposed greedy algorithm and evaluate it by performing extensive experiments using Google cluster workload traces. The experimental results show that under various scenarios, our proposed algorithm generates higher revenue than other VM allocation algorithms while achieving significant reduction of allocated memory.

关键词： Approximation algorithm multilinear programming multidimensional knapsack sharing-aware virtual machine

来源：评论

学校读者我要写书评

暂无评论

Conservative scales in packing problems

引用

OR SPECTRUM 2013年第2期35卷 505-542页

作者： Belov, G. Kartak, V. M. Rohling, H. Scheithauer, G. Tech Univ Dresden Inst Numer Math D-01062 Dresden Germany Ufa State Aviat Tech Univ Dept Numer Math Ufa Russia Tech Univ Dresden D-01062 Dresden Germany

Packing problems (sometimes also called cutting problems) are combinatorial optimization problems concerned with placement of objects (items) in one or several containers. Some packing problems are special cases of several other problems such as resource-constrained scheduling, capacitated vehicle routing, etc. In this paper we consider a bounding technique for one- and higher-dimensional orthogonal packing problems, called conservative scales (CS) (in the scheduling terminology, redundant resources). CS are related to the possible structure of resource consumption: filling of a bin, distribution of the resource to the jobs, etc. In terms of packing, CS are modified item sizes such that the set of feasible packings is not reduced. In fact, every CS represents a valid inequality for a certain binary knapsack polyhedron. CS correspond to dual variables of the set-partitioning model of a special 1D cutting-stock problem. Some CS can be constructed by (data-dependent) dual-feasible functions ((D)DFFs). We discuss the relation of CS to DFFs: CS assume that at most one copy of each object can appear in a combination, whereas DFFs allow several copies. The literature has investigated the so-called extremal maximal DFFs (EMDFFs) which should provide very strong CS. Analogously, we introduce the notions of maximal CS (MCS) and extremal maximal CS (EMCS) and show that EMDFFs do not necessarily produce (E)MCS. We propose fast greedy methods to "maximize" a given CS. Using the fact that EMCS define facets of the binary knapsack polyhedron, we use lifted cover inequalities as EMCS. For higher-dimensional orthogonal packing, we propose a Sequential LP (SLP) method over the set of CS and investigate its convergence. Numerical results are presented.

关键词： Packing Resource-constrained problems Capacitated problems Conservative scales Dual-feasible functions Knapsack inequalities Lifting multilinear programming Linearization Sequential linear programming Convergence

来源：评论

学校读者我要写书评

暂无评论

A SIMPLE BILINEAR OPTIMIZATION PROBLEM

引用

SYSTEMS & CONTROL LETTERS 1986年第1期8卷 1-4页

作者： WITSENHAUSEN, HS AT&T BELL LABS MURRAY HILLNJ 07974

multilinear optimization problems arise in many contexts, yet already the bilinear case, even for variables restricted to parallelotopes, is intractable in general. As an example of a manageable case, which may also be used to bound other cases, the elementary problem of maximizing the inner product of two vectors, each constrained to a sphere, is solved here.

关键词： Complexity Bilinear programming multilinear programming Maximum inner product Two-sphere problem

来源：评论

学校读者我要写书评

暂无评论

Computing lower and upper expectations under epistemic independence 4

Computing lower and upper expectations under epistemic indep...

引用

4th International Symposium on Imprecise Probabilities and Their Applications

作者： de Campos, Cassio Polpo Cozman, Fabio Gagliardi Univ Sao Paulo USP Leste Escola Artes Ciencias & Humanidades BR-03828000 Sao Paulo Brazil Univ Sao Paulo Escola Politecn Sao Paulo Brazil

关键词： sets of probability measures concepts of independence imprecise probabilities epistemic independence multilinear programming

来源：评论

学校读者我要写书评

暂无评论

Representing and Solving Factored Markov Decision Processes with Imprecise Probabilities

Representing and Solving Factored Markov Decision Processes ...

引用

6th International Symposium on Imprecise Probability

作者： Delgado, Karina Valdivia de Barros, Leliane Nunes Cozman, Fabio Gagliardi Shirota, Ricardo Univ Sao Paulo Inst Matemat & Estat Sao Paulo Brazil Univ Sao Paulo Escola Politecn Sao Paulo Brazil

This paper investigates Factored Markov Decision Processes with Imprecise Probabilities;that is, Markov Decision Processes where transition probabilities are imprecisely specified, and where their specification does not deal directly with states, but rather with factored representations of states. We first define a Factored MDPIP, based on a multilinear formulation for MDPIPs;then we propose a novel algorithm for generation of Gamma-maximin policies for Factored MDPIPs. We also developed a representation language for Factored MDPIPs (based on the standard PPDDL language);finally, we describe experiments with a problem of practical significance, the well-known System Administrator Planning problem.

关键词： Imprecise Markov Decision Processes (MDPIPs) Probabilistic Planning and PPDDL Knowledge Representation Languages multilinear programming

来源：评论

学校读者我要写书评

暂无评论

Target-Directed Control of Nonlinear Systems

引用

IFAC Proceedings Volumes 1989年第3期22卷 89-94页

作者： R.F. Drenick Polytechnic University Brooklyn NY 11201 USA and Polysystems Analysis Corp. P.O. Box 846 Huntingdon NY 11743 USA

A new theory for the design of controls is reviewed which applies to systems with pronounced nonlinearities and large variations in their dynamic characteristics. It assumes that the nonlinearities either are or have been approximated by polynomials. The control objective is to drive the system outputs into a target set, possibly a single point. A design theory is described that either leads to globally stable controls for a given system or else indicates a faulyy problem formulation. These results do not require control to be of the closed-loop type. Feedback is introduced specifically to provide robustness against variations in the system characteristics, i.e., for the purpose for which it was invented in the first place. It is shown that the new approach leads to results with global validity, by contrast to the traditional ones which are restricted in infinitesimally small variations.

关键词： Nonlinear control systems control systems design robust controls polynomial nonlinearities multilinear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：