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

Influence of the normalization constraint on the integral simplex using decomposition

DISCRETE APPLIED MATHEMATICS 2017年第Part1期217卷 53-70页

作者： Rosat, Samuel Elhallaoui, Issmail Soumis, Francois Chakour, Driss Polytech Montreal CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Ecole Polytech Route Saclay F-91128 Palaiseau France Gerad 3000 Ch Cote St Catherine Montreal PQ H3T 2A7 Canada

Since its introduction in 1969, the set partitioning problem has received much attention, and the structure of its feasible domain has been studied in detail. In particular, there exists a decreasing sequence of integer feasible points that leads to the optimum, such that each solution is a vertex of the polytope of the linear relaxation and adjacent to the previous one. Several algorithms are based on this observation and aim to determine that sequence;one example is the integral simplex using decomposition (ISUD) of Zaghrouti et al. (2014). In ISUD, the next solution is often obtained by solving a linear program without using any branching strategy. We study the influence of the normalization-weight vector of this linear program on the integrality of the next solution. We extend and strengthen the decomposition theory in ISUD, prove theoretical properties of the generic and specific normalization constraints, and propose new normalization constraints that encourage integral solutions. Numerical tests on scheduling instances (with up to 500,000 variables) demonstrate the potential of our approach. (C) 2016 Elsevier B.V. All rights reserved.

关键词： 0-1 programming Set partitioning problem Primal algorithms Normalization constraint Augmenting algorithms

来源：评论

学校读者我要写书评

暂无评论

Continuous dynamical systems that realize discrete optimization on the hypercube

引用

SYSTEMS & CONTROL LETTERS 2004年第3-4期52卷 297-304页

作者： Absil, PA Sepulchre, R Florida State Univ Sch Comp Sci & Informat Technol Tallahassee FL 32306 USA Univ Liege Inst Montefiore B28 Dept Elect Engn & Comp Sci B-4000 Liege Belgium

We study the problem of finding a local minimum of a multilinear function E over the discrete set {0, 1}(n). The search is achieved by a gradient-like system in [0, 1](n) with cost function E. Under mild restrictions on the metric, the stable attractors of the gradient-like system are shown to produce solutions of the problem, even when they are not in the vicinity of the discrete set {0, 1}(n). Moreover, the gradient-like system connects with interior point methods for linear programming and with the analog neural network studied by Vidyasagar (IEEE Trans. Automat. Control 40 (8) (1995) 1359), in the same context. (C) 2004 Elsevier B.V. All rights reserved.

关键词： gradient-like systems multilinear functions 0-1 programming interior point methods Lyapunov stability

来源：评论

学校读者我要写书评

暂无评论

Finding the efficient frontier of a bi-criteria, spatially explicit, harvest scheduling problem

引用

FOREST SCIENCE 2006年第1期52卷 93-107页

作者： Tóth, SF McDill, ME Rebain, S Penn State Sch Forest Resources University Pk PA 16802 USA USDA Forest Serv Forest Management Serv Ctr Ft Collins CO 80526 USA

This article evaluates the performance of five traditional methods and one new method of generating the efficient frontier for a bi-criteria, spatially explicit harvest scheduling problem. The problem is to find all possible efficient solutions, thus defining the trade-offs between two objectives: (1) maximizing the net present value of the forest and (2) maximizing the minimum area over the planning horizon in large, mature forest patches. The methods for generating the efficient frontier were tested using a hypothetical forest consisting of 50 stands. The methods were compared based on the number of efficient solutions each method can identify and on how quickly the solutions were identified. The potential to generalize these algorithms to 3- or n-criteria cases is also assessed. Three of the traditional approaches, the epsilon-constraining;the triangles method, the decomposition algorithm based on the Tchebycheff metric;and the new, proposed method are capable of generating all or most of the efficient solutions. However, the triangles and the new method far outperformed the other approaches in terms of solution time. The new method, called alpha-delta, appears to be the simplest to generalize to the tri-criteria case.

关键词： multicriteria optimization wildlife habitat trade-off analysis 0-1 programming

来源：评论

学校读者我要写书评

暂无评论

Clustering categories in support vector machines

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2017年第PartA期66卷 28-37页

作者： Carrizosa, Emilio Nogales-Gomez, Amaya Morales, Dolores Romero Univ Seville Fac Matemat Dept Estadist & Invest Operat Seville Spain Huawei France R&D Math & Algorithm Sci Lab Paris France Copenhagen Business Sch Dept Econ Copenhagen Denmark

The support vector machine (SVM) is a state-of-the-art method in supervised classification. In this paper the Cluster Support Vector Machine (CLSVM) methodology is proposed with the aim to increase the sparsity of the SVM classifier in the presence of categorical features, leading to a gain in interpretability. The CLSVM methodology clusters categories and builds the SVM classifier in the clustered feature space. Four strategies for building the CLSVM classifier are presented based on solving: the SVM formulation in the original feature space, a quadratically constrained quadratic programming formulation, and a mixed integer quadratic programming formulation as well as its continuous relaxation. The computational study illustrates the performance of the CLSVM classifier using two clusters. In the tested datasets our methodology achieves comparable accuracy to that of the SVM in the original feature space, with a dramatic increase in sparsity. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Support vector machine Categorical features Classifier sparsity Clustering Quadratically constrained programming 0-1 programming

来源：评论

学校读者我要写书评

暂无评论

A Group Rotate-Vector Algorithm for Mixed-Variable Optimization Problems

引用

IEEE ACCESS 2024年 12卷 184629-184643页

作者： Li, Zhongming Yan, Lutao Li, Haiyuan Wang, Lianxin Beijing Univ Posts & Telecommun Sch Intelligent Engn & Automat Beijing 100876 Peoples R China China Acad Chinese Med Sci Inst Basic Res Clin Med Beijing 100700 Peoples R China

Many engineering design optimization problems can be represented as mixed-variable optimization problems. This study presents a heuristic approach for solving mixed-variable optimization using rotation and contraction of vectors. The current optimization algorithm, known as rotate-vector, has shown promising results in solving optimization problems with real or integer variables. Building upon this concept, the authors of this paper develop methods to solve 0-1 type and general discrete type variables, and introduce corresponding rotation and contraction operators. To address the simultaneous search and optimization of multiple variable types in nonlinear mixed integer programming problems, a grouping and comprehensive processing method is employed. The proposed group rotate-vector algorithm (GRV) is evaluated through the solution of multiple 0-1 programming problems and mixed-variable optimization problems. The study also investigates the impact of parameter settings on solution quality and efficiency. The experimental results demonstrate that the GRV algorithm outperforms other algorithms in terms of solution quality.

关键词： Optimization Vectors Heuristic algorithms Search problems Robots Integer programming programming Convergence Constraint handling Classification algorithms Mixed-variable optimization 0-1 programming rotate-vector heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

Simple but efficient approaches for the collapsing knapsack problem

引用

DISCRETE APPLIED MATHEMATICS 1997年第3期77卷 271-280页

作者： Pferschy, U Pisinger, D Woeginger, GJ UNIV COPENHAGEN DIKUDK-2100 COPENHAGENDENMARK GRAZ TECH UNIV INST MATH BA-8010 GRAZAUSTRIA

The collapsing knapsack problem is a generalization of the ordinary knapsack problem, where the knapsack capacity is a non-increasing function of the number of items included, Whereas previous papers on the topic have applied quite involved techniques, the current paper presents and analyzes two rather simple approaches: One approach that is based on the reduction to a standard knapsack problem, and another approach that is based on a simple dynamic programming recursion. Both algorithms have pseudo-polynomial solution times, guaranteeing reasonable solution times for moderate coefficient sizes. Computational experiments are provided to expose the efficiency of the two approaches compared to previous algorithms.

关键词： collapsing knapsack problem nonlinear knapsack 0-1 programming

来源：评论

学校读者我要写书评

暂无评论

Earliness/tardiness production planning approaches with due-window for manufacturing systems

引用

COMPUTERS & INDUSTRIAL ENGINEERING 1998年第4期34卷 825-836页

作者： Wang, DW Wang, W Northeastern Univ Coll Informat Sci & Engn Dept Syst Engn Shenyang 110006 Peoples R China

Although the earliness/tardiness production planning approaches for manufacturing systems with due-date have appeared in the literature, in practice, customers prefer a time duration rather than an exact due-date. This kind of due-date is called due-window. This paper focuses on the production planning problems to minimize the total earliness and tardiness penalties with a due-window subject to the manufacturing resource constraints. Two models, one for mass manufacture and another for one-of-a-kind product (OKP) manufacture, are discussed separately. By means of mathematical deduction, the model for mass manufacture is translated into a linear programming problem and solved by a simplex method. In the case of OKP manufacture, the problem is reduced to a linear 0-1 programming model, using the elaborate definition of variables. The computational results show that both algorithms achieve the optimal production planning and are applicable to practical manufacturing systems. (C) 1998 Elsevier Science Ltd. All rights reserved.

关键词： earliness/tardiness production planning due-window linear programming 0-1 programming

来源：评论

学校读者我要写书评

暂无评论

Efficient location and paging area planning in future cellular systems

引用

WIRELESS PERSONAL COMMUNICATIONS 2000年第1期12卷 83-109页

作者： Demestichas, PP Demesticha, VP Tzifa, EC Kazantzakis, MG Anagnostou, ME Natl Tech Univ Athens Div Comp Sci GR-15773 Athens Greece

Efficient resource utilisation in future cellular systems is partly related to the location update and paging operations, which rely on "proper" planning of location and paging areas, and the application of efficient paging schemes. Important is the design of low complexity planning algorithms that may enable the system to dynamically adapt to new traffic and mobility conditions. In this paper we define and solve versions of the location and paging area planning problems focusing also on algorithms that are applicable in real-time. Thus, they can be used to adapt location and paging areas to traffic and mobility conditions. Starting from a formal definition and an optimal formulation, we solve efficiently by means of a low complexity heuristic, a general version of the location area planning problem. Regarding paging area planning, we provide a low complexity algorithm, under the assumption that the scheme applied falls within the last interaction based paging (LIBP) category. The results presented, and the low cost and complexity induced by the proposed schemes, indicates that the real-time application of the schemes is feasible.

关键词： UMTS location update location area paging paging area 0-1 programming

来源：评论

学校读者我要写书评

暂无评论

On a linearization technique for solving the quadratic set covering problem and variations

引用

OPTIMIZATION LETTERS 2017年第7期11卷 1357-1370页

作者： Pandey, Pooja Punnen, Abraham P. Simon Fraser Univ Dept Math 250-13450 102nd Ave Surrey BC V3T 0A3 Canada

In this paper we identify various inaccuracies in the paper by Saxena and Arora (Optimization 39:33-42, 1997). In particular, we observe that their algorithm does not guarantee optimality, contrary to what is claimed. Experimental analysis has been carried out to assess the value of this algorithm as a heuristic. The results disclose that for some classes of problems the Saxena-Arora algorithm is effective in achieving good quality solutions while for some other classes of problems, its performance is poor. We also discuss similar inaccuracies in another related paper.

关键词： 0-1 programming Quadratic programming Agorithms Set covering problem Heuristic

来源：评论

学校读者我要写书评

暂无评论

Efficient model and heuristic for the intermodal terminal location problem

引用

COMPUTERS & OPERATIONS RESEARCH 2014年第Nov.期51卷 41-51页

作者： Lin, Chang-Chun Chiang, Yen-I Lin, Shih-Wei Chang Gung Univ Dept Informat Management Taoyuan 333 Taiwan

A multimodal transportation system transports freight using at least two transportation modes. Among available transportation modes, intermodal freight transportation transports freight in an intermodal container or conveyance without handling the freight itself when changing modes. The locations of intermodal terminals constitute the foundation of an intermodal transportation network. The intermodal terminal location problem therefore aims to determine terminal locations and routes within a transportation network in order to minimize the total transportation and operation costs through collaborations of unimodal road transport and intermodal transport chains. Relevant research includes that of Arnold et al., who first presented mathematical programming models for the problem. Sorensen et al. recently proposed a standard model for the same problem. However, these models are complex and time consuming. Some decision variables and constraints of Sorensen et al.'s model are proven to be redundant. A modified mixed integer programming model is then developed to increase computation efficiency. The modified model finds more optimal solutions to the benchmark problems than current approaches do, within a reasonable time. Furthermore, two matheuristics are presented to solve the problem more efficiently while obtaining near optimal solutions. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Multimodal transportation Intermodal transportation Intermodal terminals 0-1 programming Heuristics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：