On the Global Solution of Linear Programs with Linear Complementarity Constraints

  • Kristin P. Bennett
  • Jing Hu
  • John E. Mitchell
  • Gautam Kunapuli
  • Jong-Shi Pang
    • Categories Complementarity and Variational Inequalities

    This paper presents a parameter-free integer-programming based algorithm for the global resolution of a linear program with linear complementarity constraints (LPEC). The cornerstone of the algorithm is a minimax integer program formulation that characterizes and provides certificates for the three outcomes—infeasibility, unboundedness, or solvability—of an LPEC. An extreme point/ray generation scheme in the spirit of … Read more

    Optimization of forming load and variables in deep drawing process for automotive cup using Genetic Algorithm

  • Ganesh Kakandikar
  • Vilas Nandedkar
    • Categories Mechanical Engineering Tags , , ,

    Sheet metal forming is a significant manufacturing process for producing a large variety of automotive parts and aerospace parts as well as consumer products. Deep drawing is a compression-tension forming process involving wide spectrum of operations and flow conditions. The result of the process depends on the large number of parameters and their interdependence. With … Read more

    An EP theorem for dual linear complementarity problem

  • Marianna Eisenberg-Nagy
  • Tibor Illés
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    The linear complementarity problem (LCP) belongs to the class of NP-complete problems. Therefore we can not expect a polynomial time solution method for LCPs without requiring some special property of the matrix of the problem. We show that the dual LCP can be solved in polynomial time if the matrix is row sufficient, moreover in … Read more

    MIR Closures of Polyhedral Sets

  • Sanjeeb Dash
  • Oktay Gunluk
  • Andrea Lodi
    • Categories Cutting Plane Approaches Tags , ,

    We study the mixed-integer rounding (MIR) closures of polyhedral sets. The MIR closure of a polyhedral set is equal to its split closure and the associated separation problem is NP-hard. We describe a mixed-integer programming (MIP) model with linear constraints and a non-linear objective for separating an arbitrary point from the MIR closure of a … Read more

    Jamming communication networks under complete uncertainty

  • Clayton W. Commander
  • Panos M. Pardalos
  • Valeriy Ryabchenko
  • Oleg Shylo
  • Stan Uryasev
  • Grigoriy Zrazhevsky
    • Categories Global Optimization Applications, Telecommunications

    This paper describes a problem of interdicting/jamming wireless communication networks in uncertain environments. Jamming communication networks is an important problem with many applications, but has received relatively little attention in the literature. Most of the work on network interdiction is focused on preventing jamming and analyzing network vulnerabilities. Here, we consider the case where there … Read more

    One Class Nonsmooth Dyscrete Step Control Problem

  • Shahlar Maharramov
    • Categories Nonsmooth Optimization Tags , , , ,

    In this paper a survey and refinement of its recent results in the discrete optimal control theory are presented. The step control problem depending on a parameter is investigated. No smoothness of the cost function is assumed and new versions of the discrete maximum principle for the step control problem are derived Citationsubmited to the … Read more

    A conic duality Frank–Wolfe type theorem via exact penalization in quadratic optimization

  • Immanuel M. Bomze
  • Werner Schachinger
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags ,

    The famous Frank–Wolfe theorem ensures attainability of the optimal value for quadratic objective functions over a (possibly unbounded) polyhedron if the feasible values are bounded. This theorem does not hold in general for conic programs where linear constraints are replaced by more general convex constraints like positive-semidefiniteness or copositivity conditions, despite the fact that the … Read more

    Solving the uncapacitated facility location problem with semi-Lagrangian relaxation

  • Antonio Alonso-Ayuso
  • Cesar Beltran-Royo
  • Jean-Philippe Vial
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Convex Optimization Tags , ,

    The semi-Lagrangian Relaxation (SLR) method has been introduced in Beltran et al. (2006) to solve the p-median problem. In this paper we apply the method to the Uncapacitated Facility Location (UFL) problem. We perform computational experiments on two main collections of UFL problems with unknown optimal values. On one collection, we manage to solve to … Read more

    Efficient Formulations for the Multi-Floor Facility Layout Problem with Elevators

  • Marc Goetschalckx
  • Takashi Irohara
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Production and Logistics Tags , , , ,

    The block layout problem for a multi-floor facility is an important sub class of the facility layout problem with practical applications when the price of land is high or when a compact building allows for more efficient environmental control. Several alternative formulations for the block layout problem of a multi-floor facility are presented, where the … Read more

    A Lifted Linear Programming Branch-and-Bound Algorithm for Mixed Integer Conic Quadratic Programs

  • Shabbir Ahmed
  • George L. Nemhauser
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming

    This paper develops a linear programming based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a higher dimensional or lifted polyhedral relaxation of conic quadratic constraints introduced by Ben-Tal and Nemirovski. The algorithm is different from other linear programming based branch-and-bound algorithms for mixed integer nonlinear programs in that, it … Read more