A binary linear programming formulation of the graph edit distance for unweighted, undirected graphs with vertex attributes is derived and applied to a graph recognition problem. A general formulation for editing grap...
详细信息
A binary linear programming formulation of the graph edit distance for unweighted, undirected graphs with vertex attributes is derived and applied to a graph recognition problem. A general formulation for editing graphs is used to derive a graph edit distance that is proven to be a metric, provided the cost function for individual edit operations is a metric. Then, a binary linear program is developed for computing this graph edit distance, and polynomial time methods for determining upper and lower bounds on the solution of the binary program are derived by applying solution methods for standard linear programming and the assignment problem. A recognition problem of comparing a sample input graph to a database of known prototype graphs in the context of a chemical information system is presented as an application of the new method. The costs associated with various edit operations are chosen by using a minimum normalized variance criterion applied to pairwise distances between nearest neighbors in the database of prototypes. The new metric is shown to perform quite well in comparison to existing metrics when applied to a database of chemical graphs.
In this paper, we present a proposal for a variation of the predictor-corrector interior point method with multiple centrality corrections. The new method uses the continued iteration to compute a new search direction...
详细信息
In this paper, we present a proposal for a variation of the predictor-corrector interior point method with multiple centrality corrections. The new method uses the continued iteration to compute a new search direction for the predictor corrector method. The purpose of incorporating the continued iteration is to reduce the overall computational cost required to solve a linear programming problem. The computational results constitute evidence of the improvement obtained with the use of this technique combined with the interior point method.
It has been an increasing trend to develop multicriteria decision-making models with imprecise, uncertain, or vague decision data. An effective way to express a decision maker's (DM's) uncertain preference inf...
详细信息
作者：
Li, HaohaoZhejiang Univ
Dept Math State Key Lab CAD & CG Hangzhou 310027 Peoples R China
Most algorithms for solving linear program require a phase-1 procedure to find a feasible solution. Recently, a dual-primal algorithm for linear optimization has been proposed by Li [Dual-primal algorithm for linear o...
详细信息
Most algorithms for solving linear program require a phase-1 procedure to find a feasible solution. Recently, a dual-primal algorithm for linear optimization has been proposed by Li [Dual-primal algorithm for linear optimization, Optimiz. Methods Softw. 28 (2013), pp. 327-338]. In the process of implementing the dual-primal algorithms, we found an interesting phenomenon that the phase-1 algorithm developed in [Li (2013)] always terminates in one iteration. This fact does not come by chance. A rigorous proof is given in this paper.
Possibilities are investigated of the combined use of interior and exterior penalty functions for discovering the generalized (approximate) solutions of improper problems of linear programming of the 1st kind. Diagram...
详细信息
Possibilities are investigated of the combined use of interior and exterior penalty functions for discovering the generalized (approximate) solutions of improper problems of linear programming of the 1st kind. Diagrams of algorithms, theorems of convergence, results of numerical experiments are presented.
A problem consisting of the determination of the optimal discharge hydrograph of a pumping station located at the downstream end of a storm drainage channel subject to time-varying inflow, is described. The goal of th...
详细信息
A problem consisting of the determination of the optimal discharge hydrograph of a pumping station located at the downstream end of a storm drainage channel subject to time-varying inflow, is described. The goal of the pumping station operational strategy is to always maintain the minimum amount of water stored in the channel by maximizing the instantaneous pumped flow rate. The equations of water motion in the channel and the design and operational constraints are approximated by employing a quasilinear time integration scheme and a staggered spatial discretization. The resulting discrete equations are linear in the unknown values of the flow variables. Accordingly, the computation of the optimal pumped flow rate is formulated as a linear programming problem for each time step. An efficient solution algorithm is developed on the basis of the particular structure of the dynamic and operational constraints associated with the problem of interest. A numerical example that illustrates the application of the proposed procedure is presented.
In this article, we consider a variant of the bandwidth packing problem, in which some demands need to be scheduled within given time windows. The emergence of cloud services has introduced a new challenge to the band...
详细信息
In this article, we consider a variant of the bandwidth packing problem, in which some demands need to be scheduled within given time windows. The emergence of cloud services has introduced a new challenge to the bandwidth packing problem. For example, a typical cloud service network consists of multiple data centres (DCs), and a huge amount of data must be exchanged between DCs to ensure the integrity of the data. This operation is not necessarily real-time, which allows network operators to schedule the demands over time. Motivated by a real-life network service provider in South Korea, we developed a practical heuristic algorithm for the problem. The algorithm utilises an open source linear programming solver. The performance of the proposed algorithm was assessed on the real-life telecommunication network in South Korea. The computational results showed that the proposed approach can provide near-optimal solutions within a short time.
This paper provides an effective modification to the big-M method which leads to reducing the iterations of this method, when it is used to recognize the infeasibility of linear systems. (c) 2008 Elsevier B.V. All rig...
详细信息
This paper provides an effective modification to the big-M method which leads to reducing the iterations of this method, when it is used to recognize the infeasibility of linear systems. (c) 2008 Elsevier B.V. All rights reserved.
Our strategy for automatic generation of functional vectors is based on exercising selected paths in the given hardware description language (HDL) model. The HDL model describes interconnections of arithmetic, logic, ...
详细信息
Our strategy for automatic generation of functional vectors is based on exercising selected paths in the given hardware description language (HDL) model. The HDL model describes interconnections of arithmetic, logic, and memory modules. Given a path in the HDL model, the search for input stimuli that exercise the path can be converted into a standard satisfiability (SAT) checking problem by expanding the arithmetic modules into logic gates, However, this approach is not very efficient. We present a new HDL-SAT checking algorithm that works directly on the HDL model. The primary feature of our algorithm is a seamless integration of linear-programming techniques for feasibility checking of arithmetic equations that govern the behavior of data-path modules and SAT checking for logic equations that govern the behavior of control modules. This feature is critically important to efficiency, since it avoids module expansion and allows us to work with logic and arithmetic equations whose cardinality tracks the size of the HDL model. We describe the details of the HDL-SAT checking algorithm in this paper. Experimental results that show significant speedups over state-of-the-art gate-level SAT checking methods are included.
The appliance and lighting group of the General Electric (GE) Company allocates its shipping truckload to 17 different trucking companies over 701 different routes from one of its nine terminals. A sequence of several...
详细信息
The appliance and lighting group of the General Electric (GE) Company allocates its shipping truckload to 17 different trucking companies over 701 different routes from one of its nine terminals. A sequence of several linear programming models was developed to help the management of the appliance and lighting division develop an optimal allocation. Two user-friendly interfaces were also developed to aid GE management in the use of one of the models. The tool is being used at GE and significant savings (approximately 15.5% of shipping costs) are possible with the optimal truckload allocation solution provided by the model. [Received 8 May 2010;Revised 2 June 2011;Accepted 15 June 2011]
暂无评论