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

Exact approaches for the knapsack problem with setups

COMPUTERS & OPERATIONS RESEARCH 2018年 90卷 208-220页

作者： Furini, Fabio Monaci, Michele Traversi, Emiliano PSL Res Univ Univ Paris Dauphine LAMSADE F-75016 Paris France Univ Bologna DEI I-40136 Bologna Italy Univ Paris 13 Lab Informat Paris Nord F-93430 Villetaneuse France

We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We theoretically compare the strength of the relaxations and derive specific results for a relevant case arising in benchmark instances from the literature. Finally, we embed the algorithms above into a unified implicit enumeration scheme which is run in parallel with an improved Dynamic Programming algorithm to effectively solve the problem to proven optimality. An extensive computational analysis shows that our new exact algorithm is capable of efficiently solving all the instances of the literature and turns out to be the best algorithm for instances with a low number of classes. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Knapsack problems Column generation Relaxations branch-and-bound algorithms Computational experiments

来源：评论

学校读者我要写书评

暂无评论

Guaranteed Analysis and Optimisation of Parametric Systems with Application to their Stability Degree

引用

EUROPEAN JOURNAL OF CONTROL 1997年第1期3卷 68-80页

作者： Didrit, O. Jaulin, L. Walter, E. CNRS Supelec Lab Signaux & Syst F-91192 Gif Sur Yvette France Univ Angers Equipe Signaux Syst & Applicat Fac Sci Angers France

Two splitting-domain algorithms using interval analysis to analyse and optimise a scalar criterion that depends non-linearly on a parameter vector are presented. Their results are guaranteed, and provided with an estimation of their degree of approximation. As an example of application, the stability degree of linear time-invariant parametric systems is considered. It is thus possible to characterise isodegrees in the parameter space and to compute a set guaranteed to contain all values of the parameters that maximise (or minimise) the stability degree as well as an interval guaranteed to contain its optimal value. Several examples of the literature illustrate the efficiency of the method.

关键词： branch-and-bound algorithms Global optimisation Interval analysis Splitting-domain algorithms Stability degree

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL SCHEDULING IN FILM PRODUCTION TO MINIMIZE TALENT HOLD COST

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1993年第3期79卷 479-492页

作者： CHENG, TCE DIAMOND, JE LIN, BMT UNIV MANITOBA DEPT MECH & IND ENGN WINNIPEG R3T 2N2 MANITOBA CANADA NATL CHIAO TUNG UNIV DEPT COMP & INFORMAT SCI HSINCHU TAIWAN

The problem of minimizing the cost due to talent hold days in the production of a feature film is considered. A combinatorial model is developed for the sequencing of shooting days in a film shoot. The problem is shown to be strongly NP-hard. A branch-and-bound solution algorithm and a heuristic solution method for large instances of the problem (15 shooting days or more) are developed and implemented on a computer. A number of randomly generated problem instances are solved to study the power and speed of the algorithms. The computational results reveal that the heuristic solution method is effective and efficient in obtaining near-optimal solutions.

关键词： SCHEDULING branch-and-bound algorithms NP-HARDNESS

来源：评论

学校读者我要写书评

暂无评论

Solving sum of ratios fractional programs via concave minimization

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2007年第1期135卷 1-17页

作者： Benson, H. P. Univ Florida Warrington Coll Business Adm Gainesville FL 32611 USA

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.

关键词： global optimization sum of ratios fractional programming concave minimization branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Global maximization of a generalized concave multiplicative function

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2008年第1期137卷 105-120页

作者： Benson, H. P. Univ Florida Dept Informat & Decis Sci Gainesville FL 32611 USA

This article presents a branch-and-bound algorithm for globally solving the problem (P) of maximizing a generalized concave multiplicative function over a compact convex set. Since problem (P) does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving this problem. It works by globally solving a problem (P1) equivalent to problem (P). The branch-and-bound search undertaken by the algorithm uses rectangular partitioning and takes place in a space which typically has a much smaller dimension than the space to which the decision variables of problem (P) belong. Convergence of the algorithm is shown;computational considerations and benefits for users of the algorithm are given. A sample problem is also solved.

关键词： global optimization branch-and-bound algorithms multiplicative programming quadratic programming bilinear programming

来源：评论

学校读者我要写书评

暂无评论

A fast algorithm for non-negativity model selection

引用

STATISTICS AND COMPUTING 2013年第3期23卷 403-411页

作者： Gatu, Cristian Kontoghiorghes, Erricos John Alexandru Ioan Cuza Univ Fac Comp Sci Iasi Romania Univ Cyprus Dept Publ & Business Adm Nicosia Cyprus Cyprus Univ Technol Fac Management & Econ Lemesos Cyprus Univ London Sch Econ & Finance London England

An efficient optimization algorithm for identifying the best least squares regression model under the condition of non-negative coefficients is proposed. The algorithm exposits an innovative solution via the unrestricted least squares and is based on the regression tree and branch-and-bound techniques for computing the best subset regression. The aim is to filling a gap in computationally tractable solutions to the non-negative least squares problem and model selection. The proposed method is illustrated with a real dataset. Experimental results on real and artificial random datasets confirm the computational efficacy of the new strategy and demonstrates its ability to solve large model selection problems that are subject to non-negativity constrains.

关键词： Subset selection Non-negative least squares branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Algorithm for the Constrained Two-dimensional Cutting Stock Problem

引用

International Transactions in Operational Research 2001年第1期8卷 3-13页

作者： Amaral, Andre R. S. Wright, Mike Departamento de Informatica Universidade Federal do Espirito Santo Brazil Department of Management Science Lancaster University United Kingdom

This paper considers the constrained two-dimensional cutting stock problem. Some properties of the problem are derived leading to the development of a new algorithm, which uses a very efficient branching strategy for the solution of this problem. This strategy enables the early rejection of partial solutions that cannot lead to optimality. Computational results are given and compared with those produced by a leading alternative method. These results show that the new algorithm is far superior in terms of the computer time needed to solve such problems. International Federation of Operational Research Societies 2001.

关键词： branch-and-bound algorithms Combinatorial optimization Cutting stock problem

来源：评论

学校读者我要写书评

暂无评论

Application of a hill-climbing algorithm to exact and approximate inference in credal networks 4

Application of a hill-climbing algorithm to exact and approx...

引用

4th International Symposium on Imprecise Probabilities and Their Applications

作者： Cano, Andres Gomez, Manuel Moral, Serafin Univ Granada Dept Comp Sci & Artificial Intelligence ETS Ingn Informat E-18071 Granada Spain

This paper proposes two new algorithms for inference in credal networks. These algorithms enable probability intervals to be obtained for the states of a given query variable. The first algorithm is approximate and uses the hill-climbing technique in the Shenoy-Shafer architecture to propagate in join trees;the second is exact and is a modification of Rocha and Cozman's branch-and-bound algorithm, but applied to general directed acyclic graphs.

关键词： Credal network probability intervals Bayesian networks strong independence hill-climbing branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Access Point Assignment algorithms in WLANs Based on Throughput Objectives

Access Point Assignment Algorithms in WLANs Based on Through...

引用

6th International Symposium on Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks

作者： Koukoutsidis, Ioannis Siris, Vasilios A. Univ Athens Dept Informat & Telecommun Athens 15784 Greece Univ Crete Fdn Res & Technol Hellas Inst Comp Sci FORTH ICS Iraklion 71110 Crete Greece

ISBN: (纸本)9781424431212

In this article we present branch-and-bound algorithms for the access point assignment problem in WLANs, when the objective function is based on the throughput of stations in the network. We consider: a) maximizing the aggregate throughput, b) achieving lexicographically max-min fair throughputs, c) achieving proportionally fair throughputs. The performance of all branch-and-bound algorithms is examined for various degrees of approximation. Thus we show trade-offs between the increased cost of exploration and improvement in the objective value. We further compare their performance to that of greedy algorithms, embedded as a depth-first-search in the branch-and-bound methods. An omnipresent result is the near-optimal performance of the greedy algorithms, which is particularly important when considering their practical application. In all cases, the performance of the algorithms improves as the distribution of wireless stations becomes more concentrated in areas of the network, as in hotspot topologies.

关键词： WLAN 802.11 access point assignment throughput optimization branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal line and Arc detection on run-length representations

引用

6th International Workshop on Graphic Recognition

作者： Keysers, Daniel Breuel, Thomas M. DFKI GmbH German Res Ctr Artificial Intelligence Image Understanding & Pattern Recognit Res Grp D-67663 Kaiserslautern Germany Univ Kaiserslautern D-67663 Kaiserslautern Germany

ISBN: (纸本)3540347119

The robust detection of lines and arcs in scanned documents or technical drawings is an important problem in document image understanding. We present a new solution to this problem that works directly on run-length encoded data. The method finds globally optimal solutions to parameterized thick line and are models. Line thickness is part of the model and directly used during the matching process. Unlike previous approaches, it does not require any thinning or other preprocessing steps, no computation of the line adjacency graphs, and no heuristics. Furthermore, the only search-related parameter that needs to be specified is the desired numerical accuracy of the solution. The method is based on a branch-and-bound approach for the globally optimal detection of these geometric primitives using runs of black pixels in a bi-level image. We present qualitative and quantitative results of the algorithm on images used in the 2003 and 2005 GREC arc segmentation contests.

关键词： graphics recognition line drawings technical drawings branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：