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

An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第1期291卷 67-83页

作者： Seker, Oylum Ekim, Tinaz Taskin, Z. Caner Univ Toronto Dept Mech & Ind Engn Toronto ON M5S 3G8 Canada Bogazici Univ Dept Ind Engn TR-34342 Istanbul Turkey

We consider the selective graph coloring problem, which is a generalization of the classical graph coloring problem. Given a graph together with a partition of its vertex set into clusters, we want to choose exactly one vertex per cluster so that the number of colors needed to color the selected set of vertices is minimized. This problem is known to be NP-hard. In this study, we focus on an exact cutting plane algorithm for selective graph coloring in perfect graphs. Since there exists no suite of perfect graph instances to the best of our knowledge, we also propose an algorithm to randomly (but not uniformly) generate perfect graphs, and provide a large collection of instances available online. We conduct computational experiments to test our method on graphs with varying size and densities, and compare our results with a state-of-the-art algorithm from the literature and with solving an integer programming formulation of the problem by CPLEX. Our experiments demonstrate that our solution strategy significantly improves the solvability of the problem. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph theory Selective graph coloring Partition coloring cutting plane algorithm Perfect graph generation

来源：评论

学校读者我要写书评

暂无评论

An enhanced cutting plane algorithm of elastoplastic constitutive models for geomaterials

引用

COMPUTERS AND GEOTECHNICS 2023年第1期155卷

作者： Zhao, Lun-Yang Liu, Ling-Hui Lai, Yuan-Ming South China Univ Technol South China Inst Geotech Engn Sch Civil Engn & Transportat Guangzhou 510641 Peoples R China South China Univ Technol State Key Lab Subtrop Bldg Sci Guangzhou 510641 Peoples R China Chinese Acad Sci Northwest Inst Ecoenvironm & Resources State Key Lab Frozen Soil Engn Lanzhou 730000 Gansu Peoples R China

Integration of the nonlinear stress-strain relationship plays a critical role in the application of constitutive models to engineering practice. Aiming at the nonlinear integration problems commonly existing in elastoplastic constitutive models for geomaterials, we herein present a robust enhanced cutting plane algorithm (ECPA). This algorithm is based on the traditional cutting plane algorithm (CPA) with a new adaptive substepping technique. The accuracy of the CPA is first investigated via a series of numerical examples on a unified hardening/softening elastoplastic model with different nonlinearity degrees of yield functions and plastic potential functions. An intriguing observation is that the accuracy of CPA cannot be guaranteed as long as the plastic flow direction (i.e., partial derivative G/partial derivative sigma) is not a constant during loading. To overcome this deficiency, a substepping technique for adaptively restricting substep increments solely related to the plastic flow direction was originally proposed and embedded into CPA. The robustness, including the accuracy and efficiency of the proposed ECPA, is evaluated by setting different increment steps and error tolerances. Finally, the ECPA is applied to the Modified Cam Clay (MCC) model, and the robustness of the ECPA is further assessed in element scale tests and a boundary value problem.

关键词： Numerical integration cutting plane algorithm Adaptive substepping Elastoplastic models Modified Cam Clay

来源：评论

学校读者我要写书评

暂无评论

A faster cutting plane algorithm with accelerated line search for linear SVM

引用

PATTERN RECOGNITION 2017年 67卷 127-138页

作者： Chu, Dejun Zhang, Changshui Tao, Qing Tsinghua Univ Dept Automat State Key Lab Intelligent Technol & Syst Tsinghua Natl Lab Informat Sci & Technol TNList Beijing Peoples R China Army Officer Acad PLA Hefei Peoples R China

cutting plane algorithm (CPA) is a generalization of iterative first-order gradient method, in which the objective function is approximated successively by supporting hyperplanes. CPA has been tailored to solve regularized loss minimization in machine learning by exploiting the regularization structure. In particular, for linear Support Vector Machine (SVM) embedding a line search procedure effectively remedies the fluctuations of function value and speeds up the convergence in practical issue. However, the existing line search strategy based on sorting algorithm takes O(mlogm) time. In this paper, we propose a more effective line search solver which spends only linear time. It can be extended to multiclass SVM in which an optimized explicit piecewise linear function finding algorithm is prearranged. The total SVM training time is proved to reduce theoretically and experiments consistently confirm the effectiveness of the proposed algorithms. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Linear support vector machine Binary classification Root finding cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

Multiple kernel multivariate performance learning using cutting plane algorithm

Multiple kernel multivariate performance learning using cutt...

引用

IEEE International Conference on Systems, Man, and Cybernetics (SMC)

作者： Wang, Jingbin Wang, Haoxiang Zhou, Yihua McDonald, Nancy Chinese Acad Sci Natl Time Serv Ctr Xian 710600 Peoples R China Chinese Acad Sci Grad Univ Beijing 100039 Peoples R China Cornell Univ Dept Elect & Comp Engn Ithaca NY 14850 USA Lehigh Univ Dept Mech Engn & Mech Bethlehem PA 18015 USA Tulane Univ Dept Comp Sci New Orleans LA 70118 USA

ISBN: (纸本)9781479986965

In this paper, we propose a multi-kernel classifier learning algorithm to optimize a given nonlinear and nonsmoonth multivariate classifier performance measure. Moreover, to solve the problem of kernel function selection and kernel parameter tuning, we proposed to construct an optimal kernel by weighted linear combination of some candidate kernels. The learning of the classifier parameter and the kernel weight are unified in a single objective function considering to minimize the upper boundary of the given multivariate performance measure. The objective function is optimized with regard to classifier parameter and kernel weight alternately in an iterative algorithm by using cutting plane algorithm. The developed algorithm is evaluated on two different pattern classification methods with regard to various multivariate performance measure optimization problems. The experiment results show the proposed algorithm outperforms the competing methods.

关键词： Pattern recognition multiple kernel multivariate performance measures cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

STABILITY ANALYSIS OF DISCRETE-TIME LINEAR COMPLEMENTARITY SYSTEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2025年第1期35卷 419-444页

作者： Raghunathan, Arvind u. Linderoth, Jeffrey t. Mitsubishi Elect Res Labs Cambridge MA 02139 USA Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA

A Discrete-Time Linear Complementarity System (DLCS) is a dynamical system in discrete time whose state evolution is governed by linear dynamics in states and algebraic variables that solve a Linear Complementarity Problem (LCP). The DLCS is the hybrid dynamical system that is the discrete-time counterpart of the well-known Linear Complementarity System (LCS). We derive sufficient conditions for Lyapunov stability of a DLCS when using a quadratic Lyapunov function that depends only on the state variables and a quadratic Lyapunov function that depends both on the state and the algebraic variables. The sufficient conditions require checking the feasibility of a copositive program over nonconvex cones. Our results only assume that the LCP is solvable and do not require the solutions to be unique. We devise a novel, exact cutting plane algorithm for the verification of stability and the computation of the Lyapunov functions. To the best of our knowledge, our algorithm is the first exact approach for stability verification of DLCS. A number of numerical examples are presented to illustrate the approach. Though our main object of study in this paper is the DLCS, the proposed algorithm can be readily applied to the stability verification of LCS. In this context, we show the equivalence between the stability of a LCS and the DLCS, resulting from a time-stepping procedure applied to the LCS for all sufficiently small time steps.

关键词： Lyapunov stability common quadratic Lyapunov function extended quadratic Lyapunov function copositive program cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact method for trilevel hub location problem with interdiction

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期319卷 696-710页

作者： Ramamoorthy, Prasanna Jayaswal, Sachin Sinha, Ankur Vidyarthi, Navneet Indian Inst Technol Delhi Dept Management Studies New Delhi 110016 India Indian Inst Management Ahmedabad Operat & Decis Sci Ahmadabad 380015 Gujarat India Concordia Univ John Molson Sch Business Montreal PQ H3G 1M8 Canada Concordia Univ CIRRELT Montreal PQ H3G 1M8 Canada

In this paper, we study the problem of designing a hub network that is robust against deliberate attacks (interdictions). The problem is modeled as a three-level, two-player Stackelberg game, in which the network designer (defender) acts first to locate hubs to route a set of flows through the network. The attacker (interdictor) acts next to interdict a subset of the located hubs in the designer's network, followed again by the defender who routes the flows through the remaining hubs in the network. We model the defender's problem as a trilevel optimization problem, wherein the attacker's response is modeled as a bilevel hub interdiction problem. We study such a trilevel problem on three variants of hub location problems studied in the literature namely: p-hub median problem, p-hub center, and p-hub maximal covering problems. We present a cutting plane based exact method to solve the problem. The cutting plane method uses supervalid inequalities, which is obtained from the solution of the lower level interdiction problem. To solve the lower level hub interdiction problem efficiently, we propose a penalty-based reformulation of the problem. Using the reformulation, we present a branch-and-cut based exact approach to solve the problem efficiently. We conduct experiments to show the computational advantages of the above algorithm. To the best of our knowledge, the cutting plane approach proposed in this paper is among the first exact method to solve trilevel location-interdiction problems. Our computational results show interesting implications of incorporating interdiction risks in the hub location problem.

关键词： Location Interdiction Trilevel programming cutting plane algorithm Stackelberg games

来源：评论

学校读者我要写书评

暂无评论

A cutting plane approach to maximization of fundamental frequency in truss topology optimization

引用

STRUCTURAL AND MULTIDISCIPLINARY OPTIMIZATION 2024年第4期67卷 54-54页

作者： Aroztegui, Jose Miguel Pessoa, Artur Univ Fed Paraiba Dept Comp Cient Joao Pessoa PB Brazil Univ Fed Fluminense Dept Engn Prod Niteroi RJ Brazil

This work introduces a cutting plane algorithm to solve the maximization of the minimum frequency of truss structures subject to volume and compliance constraints. Multiple load cases and multiple scenarios of non-structural mass distributions are considered. This problem is formulated as a non-convex semi-definite programming problem with Bi-linear Matrix Inequality (BMI) constraints. The proposed algorithm consists of iteratively tightening a linear relaxation of that problem. A new family of linear constraints (cutting planes) is defined as a linearization of BMI constraints. It is proved that the algorithm can find a violated valid cut for any infeasible solution that could be found in any iteration. Implementation details of the algorithm are given. We show the robustness of the method with some numerical examples and compare its performance with other available solvers. The reported results indicate that the new method outperforms the previous ones when the number of non-structural mass scenarios is large.

关键词： cutting plane algorithm Bi-linear matrix inequality Truss topology optimization Semi-definite Programming

来源：评论

学校读者我要写书评

暂无评论

Weak Disambiguation for Partial Structured Output Learning

引用

IEEE TRANSACTIONS ON CYBERNETICS 2022年第2期52卷 1258-1268页

作者： Lu, Xiaolei Chow, Tommy W. S. City Univ Hong Kong Dept Elect Engn Hong Kong Peoples R China

Existing disambiguation strategies for partial structured output learning just cannot generalize well to solve the problem that there are some candidates that can be false positive or similar to the ground-truth label. In this article, we propose a novel weak disambiguation for partial structured output learning (WD-PSL). First, a piecewise large margin formulation is generalized to partial structured output learning, which effectively avoids handling a large number of candidate-structured outputs for complex structures. Second, in the proposed weak disambiguation strategy, each candidate label is assigned with a confidence value indicating how likely it is the true label, which aims to reduce the negative effects of wrong ground-truth label assignment in the learning process. Then, two large margins are formulated to combine two types of constraints which are the disambiguation between candidates and noncandidates, and the weak disambiguation for candidates. In the framework of alternating optimization, a new 2n-slack variables cutting plane algorithm is developed to accelerate each iteration of optimization. The experimental results on several sequence labeling tasks of natural language processing show the effectiveness of the proposed model.

关键词： cutting plane algorithm partial structured output learning piecewise large margin weak disambiguation

来源：评论

学校读者我要写书评

暂无评论

Pessimistic evasive flow capturing problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第1期293卷 133-148页

作者： Bogyrbayeva, Aigerim Kwon, Changhyun Univ S Florida Dept Ind & Management Syst Engn Tampa FL 33620 USA

The evasive flow capturing problem (EFCP) is to locate a set of law enforcement facilities to intercept unlawful flows. One application of the EFCP is the location problem of weigh-in-motion systems deployed by authorities to detect overloaded vehicles characterized by evasive behavior. In contrast to the existing literature, this study focuses on the bounded-rationality of drivers and represents the most generic form of the EFCP. We present two pessimistic formulations of the problem to capture various degrees of ambiguity in the route choice of drivers. In particular, we look at the worst-case scenario, when drivers select roads with the highest damage costs. The resulting formulations yield a robust network design and represent the realistic behavior of drivers. The pessimistic formulations introduce another level in the optimization problem, for which we propose a cutting plane algorithm. The proposed solution methods demonstrate their effectiveness on real and randomly generated networks. We also provide numerical analysis to measure the value of considering pessimistic formulations and demonstrate the vulnerability of optimizing and optimistic assumptions on the behavior of drivers. (C) 2020 Published by Elsevier B.V.

关键词： Transportation Bilevel optimization Pessimistic formulation Mixed-integer program cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

Robust reward-risk ratio portfolio optimization

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2021年第4期28卷 2169-2190页

作者： Sehgal, Ruchika Mehra, Aparna Indian Inst Technol Dept Math New Delhi 110016 India

In this paper, we propose robust portfolio optimization models for reward-risk ratios utilizing Omega, semi-mean absolute deviation ratio, and weighted stable tail adjusted return ratio (STARR). We address the uncertainty in returns on assets by varying them in symmetric bounded intervals. The proposed robust reward-risk ratios preserve linearity in the resulting models, and hence are tractable. However, the robust models involve a sizably voluminous number of constraints, especially when the number of assets and scenarios is large. We employ the cutting plane algorithm to solve the proposed models in a much reduced time efficiently. We evaluate the performance of the robust reward-risk ratio models on the listed stocks of FTSE 100, Nikkei 225, S&P 500, and S&P BSE 500. The robust portfolio optimization models are found to outperform their conventional counterpart models in terms of statistics measured by the standard deviation, value at risk (VaR), conditional value at risk (CVaR), Sharpe ratio, and STARR ratio.

关键词： robust portfolio optimization reward– risk ratio Omega ratio STARR ratio weighted conditional value at risk cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：