We prove, in a constructive way, the equivalence between hybrid and piecewise affine systems. By focusing our investigation on the latter class, we show through counter-examples that observability and controllability ...
详细信息
We prove, in a constructive way, the equivalence between hybrid and piecewise affine systems. By focusing our investigation on the latter class, we show through counter-examples that observability and controllability properties cannot be easily deduced from those of the component linear subsystems. Instead, we propose practical numerical tests based on mixed-integer linear programming.
Bayesian networks, also known as Bayesian belief networks, are a connectionist knowledge representation that is popular in AI for reasoning under uncertainty. A Bayesian network is a directed acyclic graph augmented w...
详细信息
Bayesian networks, also known as Bayesian belief networks, are a connectionist knowledge representation that is popular in AI for reasoning under uncertainty. A Bayesian network is a directed acyclic graph augmented with conditional probability distributions residing in each node. An important problem on Bayesian networks is that of finding the most probable network assignment, or explanation, that is consistent with a given set of observances called the evidence. In an earlier paper (1998), the author presented an algorithm that allows the explanation problem on Bayesian networks to be modeled by integer linear programming. In this paper, he presents the results of applying this algorithm to a group of Bayesian networks.
In a recent paper, Yang proposes an integer labeling algorithm for determining whether an arbitrary simplex P in R-n contains an integer point or not. The problem under consideration is a very difficult one in the sen...
详细信息
In a recent paper, Yang proposes an integer labeling algorithm for determining whether an arbitrary simplex P in R-n contains an integer point or not. The problem under consideration is a very difficult one in the sense that it is NP-complete. The algorithm is based on a specific integer labeling rule and a specific triangulation of R-n. In this paper we discuss a practical implementation of the algorithm and present a computer program (ILIN) for solving integerprogramming using integer labeling algorithm. We also report on the solution of a number of tested examples with up to 500 integer variables. Numerical results indicate that the algorithm is computationally simple, flexible, efficient and stable.
In this paper we discuss minimal spanning trees with a constraint on the number of leaves. Tree topologies appear when designing centralized terminal networks. The constraint on the number of leaves arises because the...
详细信息
In this paper we discuss minimal spanning trees with a constraint on the number of leaves. Tree topologies appear when designing centralized terminal networks. The constraint on the number of leaves arises because the software and hardware associated to each terminal differs accordingly with its position in the tree. Usually, the software and hardware associated to a "degree-1" terminal is cheaper than the software and hardware used in the remaining terminals because for any intermediate terminal j one needs to check if the arrival message is destined to that node or to any other node located after node j. As a consequence, that particular terminal needs software and hardware for message routing. On the other hand, such equipment is not needed in "degree-1" terminals. Assuming that the hardware and software for message routing in the nodes is already available, the above discussion motivates a constraint stating that a tree solution has to contain exactly a certain number of "degree-1" terminals. We present two different formulations for this problem and some lower bounding schemes derived From them. We discuss a simple local-exchange heuristic and present computational results taken from a set of complete graphs with up to 40 nodes. integer linear programming formulations for related problems are also discussed st the end. (C) 1998 Elsevier Science B.V.
In high-level synthesis, a data how graph (DFG) description of an algorithm is mapped onto a register transfer level description of an architecture, Each node of the DFG is scheduled to a specific time and allocated t...
详细信息
In high-level synthesis, a data how graph (DFG) description of an algorithm is mapped onto a register transfer level description of an architecture, Each node of the DFG is scheduled to a specific time and allocated to a processor. In this paper, we present new integer linear programming (ILP) models which generate a blocked schedule for a DFG with automatic retiming, pipelining, and unfolding while performing module selection and data format conversion. A blocked schedule is a schedule which overlaps multiple iterations of the DFG to guarantee a processor optimal schedule. During module selection an appropriate processor is chosen from a library of processors to construct a cost optimal architecture. Furthermore, we also include the cost and latency of data format conversions between processors of different implementation styles, We also present a new formulation for minimizing the unfolding factor of the blocked schedule. The approach presented in this paper is the only systematic approach proposed so far to include implicit unfolding and to perform synthesis using nonuniform processor styles and data format converters.
In this paper, an industrial-facilities selection problem has been considered. The selection of machine tools is the most important capital investment decision made by managers. In this research, an attempt has been m...
详细信息
In this paper, an industrial-facilities selection problem has been considered. The selection of machine tools is the most important capital investment decision made by managers. In this research, an attempt has been made to use set theory for the facility-selection problem. From a known work load and the known capabilities of manufacturing resources, a set theoretic analysis leads to the identification of constraints bearing upon the process of resource selection in any given case. a suitable criterion of optimality then permits an optimal selection to be made by integerprogramming or other mathematical programming methods. The manufacturing system design for aircraft engine parts has been investigated. (C) 1998 Elsevier Science S.A.
In this paper routing, planning of working capacity, rerouting, and planning of spare capacity in wavelength division multiplexing (WDM) networks are investigated. integer linear programming (ILP) and simulated anneal...
详细信息
In this paper routing, planning of working capacity, rerouting, and planning of spare capacity in wavelength division multiplexing (WDM) networks are investigated. integer linear programming (ILP) and simulated annealing (SA) are used as solution techniques. A complex cost model is presented. The spare capacity assignment is optimized with respect to three restoration strategies. The benefit of wavelength conversion, the choice of the fiber line system, and the influence of cost parameter values are discussed, with respect to the different restoration strategies and solution techniques. Wavelength conversion is found to be of limited importance, whereas tunability at the end points of the connections has substantial benefits.
In the present paper trim-loss problems, often named the cutting stock problem, connected to the paper industry are considered. The problem is to cut out a set of product paper rolls from raw paper rolls such that the...
详细信息
In the present paper trim-loss problems, often named the cutting stock problem, connected to the paper industry are considered. The problem is to cut out a set of product paper rolls from raw paper rolls such that the cost function, including the trim loss as well as the costs for the over production, is minimized. The problem is non-convex due to certain bilinear constraints. The problem can, however, be transformed into linear or convex form. The resulting transformed problems can, thereafter, be solved as mixed-integer linear programming problems or convex mixed-integer non-linearprogramming problems. The linear and convex formulations are attractive from a formal point of view, since global optimal solutions to the originally non-convex problem can be obtained. However, as the examples considered will show, the numerical efficiency of the solutions from the different transformed formulations varies considerably. An example based on a trim optimization problem encountered daily at a Finnish paper converting mill is, finally, presented in order to demonstrate differences in the numerical solutions. (C) 1998 Elsevier Science B.V.
作者：
Wren, AUniv Leeds
Sch Comp Studies Leeds LS2 9JT W Yorkshire England
Heuristics which have been developed for transport scheduling over a lengthy period starting in 1960 are presented. They are generated in response to requirements to solve practical problems, and most are now in regul...
详细信息
Heuristics which have been developed for transport scheduling over a lengthy period starting in 1960 are presented. They are generated in response to requirements to solve practical problems, and most are now in regular use by bus and train companies. Mathematical programming models have been formulated for some of the problems, but have been inappropriate on their own;in some cases. heuristics have led to a reduced problem which has then been solved by integer linear programming. The paper is designed to illustrate the development of heuristics for a range of related problem areas over nearly forty years. It explores the relationships between heuristics and other approaches and emphasises the need to convince users of the suitability of me overall system. Where appropriate, indications are given of difficulties in achieving practical implementation.
暂无评论