Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Subject: search.filters.subject.linear programming

Search Results

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Stability of Wireless Networks for Mode S Radar
    (2000) Chawla, Jay P.; Marcus, Steven I.; Shayman, Mark A.; Shayman, Mark; Marcus, Steven; ISR
    Stability issues in a connectionless, one-hop queueing system featuringservers with overlapping service regions (e.g. a Mode Select (Mode S) Radarcommunications network or part of an Aeronautical Telecommunications Network (ATN) network) are considered, and a stabilizing policy is determined in closed-loop form. The cases of queues at the sources (aircraft) and queues at the servers (base stations) are consideredseparately. Stabilizability of the system with exponential service times and Poisson arrival rates is equivalent to the solvability of a linear program and if the system is stabilizable, a stabilizing open loop routingpolicy can be expressed in terms of the coefficients of the solution to thelinear program. We solve the linear program for the case of a single class of packets.

    The research and scientific content in this material has beenpublished under the same title in the Proceedings of the 32nd Conference onInformation Sciences and Systems; Princeton, NJ; March 1998.
  • Thumbnail Image
    Item
    An Interior Point Method for Linear Programming, with n Active Set Flavor
    (1999) Tits, Andre L.; ISR
    It is now well established that, especially on large linearprogramming problems, the simplex method typically takes upa number of iterations considerably larger than recentinterior-points methods in order to reach a solution.On the other hand, at each iteration, the size of thelinear system of equations solved by the formercan be significantly less than that of the linearsystem solved by the latter.The algorithm proposed in this paper can be thought ofas a compromise between the two extremes: conceptuallyan interior-point method, it ignores, at each iteration,all constraints except those in a small "active set"(in the dual framework). For sake of simplicity, inthis first attempt, an affine scaling algorithm is usedand strong assumptions are made on the problem. Globaland local quadratic convergence is proved.
  • Thumbnail Image
    Item
    A Simple quadratically convergent Interior Point Algorithm for Linear Programming and Convex quadratic Programming
    (1993) Tits, A.L.; Zhou, J.L.; ISR
    An algorithm for linear programming (LP) and convex quadratic programming (CQP) is proposed, based on an interior point iteration introduced more than ten years ago by J. Herskovits for the solution of nonlinear programming problems. Herskovits' iteration can be simplified significantly in the LP/CQP case, and quadratic convergence from any initial point can be achieved. Interestingly the resulting algorithm is closely related to a popular scheme, proposed in 1989 by Kojima et al. independently of Herskovits' work.
  • Thumbnail Image
    Item
    Optimal Admission Control of Two Traffic Types at a Circuit- Switched Network Node
    (1991) Lambadaris, Ioannis E.; Narayan, P.; Viniotis, I.; ISR
    Two communication traffic streams with Poisson statistics arrive at a network node on separate routes. These streams are to be forwarded to their destinations via a common trunk. The two links leading to the common trunk have capacities C1 and C2 bandwidth units, respectively, while the capacity of the common trunk is C bandwidth units, where C < C1 + C2. Calls of either traffic type that are not admitted at the node are assumed to be discarded. An admitted call of either type will occupy, for an exponentially distributed random time, one bandwidth unit on its forwarding link as well as on the common trunk. Our objective is to determine a scheme for the optimal dynamic allocation of available bandwidth among the two traffic streams so as to minimize a weighted blocking cost. The problem is formulated as a Markov decision process. By using dynamic programming principles, the optimal admission policy is shown to be of the "bang-bang" type, characterized by appropriate "switching curves". The case of a general circuit-switched network, as well as numerical examples, are also presented.