complementarity constraints

Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints

  • Alberto Del Pia
  • Jeff Linderoth
  • Haoran Zhu
    • Categories 0-1 Programming, Cutting Plane Approaches, Global Optimization Tags , , , ,

    We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and generalizes the extended reformulation-linearization technique of Nguyen, Richard, and Tawarmalani to instances with general complementarity conditions between variables. We demonstrate … Read more

    Modeling Design and Control Problems Involving Neural Network Surrogates

  • Dominic Yang
  • Prasanna Balaprakash
  • Sven Leyffer
    • Categories (Mixed) Integer Nonlinear Programming, Control Applications, Nonsmooth Optimization Tags , , , ,

    We consider nonlinear optimization problems that involve surrogate models represented by neural net-works. We demonstrate first how to directly embed neural network evaluation into optimization models, highlight a difficulty with this approach that can prevent convergence, and then characterize stationarity of such models. We then present two alternative formulations of these problems in the specific … Read more

    Different discretization techniques for solving optimal control problems with control complementarity constraints

  • Yu Deng
    • Categories Complementarity and Variational Inequalities, Infinite Dimensional Optimization Tags , , , ,

    There are first-optimize-then-discretize (indirect) and first-discretize-then-optimize (direct) methods to deal with infinite dimensional optimal problems numerically by use of finite element methods. Generally, both discretization techniques lead to different structures. Regarding the indirect method, one derives optimality conditions of the considered infinite dimensional problems in appropriate function spaces firstly and then discretizes them into suitable … Read more

    Nonlinear Optimization of District Heating Networks

  • Richard Krug
  • Volker Mehrmann
  • Martin Schmidt
    • Categories Applications - Science and Engineering, Nonlinear Optimization, Systems governed by Differential Equations Optimization Tags , , , , ,

    We develop a complementarity-constrained nonlinear optimization model for the time-dependent control of district heating networks. The main physical aspects of water and heat flow in these networks are governed by nonlinear and hyperbolic 1d partial differential equations. In addition, a pooling-type mixing model is required at the nodes of the network to treat the mixing … Read more

    An Enhanced Logical Benders Approach for Linear Programs with Complementarity

  • Francisco Jara-Moroni
  • John E. Mitchell
  • Jong-Shi Pang
    • Categories Complementarity and Variational Inequalities, Global Optimization, Nonlinear Optimization Tags , ,

    This work extends the ones of Hu et al. (2008) and Bai et al. (2013) of a logical Benders approach for globally solving Linear Programs with Complementarity Constraints. By interpreting the logical Benders method as a reversed branch-and-bound method, where the whole exploration procedure starts from the leaf nodes in an enumeration tree, we provide … Read more

    Complementarity-Based Nonlinear Programming Techniques for Optimal Mixing in Gas Networks

  • Falk M. Hante
  • Martin Schmidt
    • Categories Applications - Science and Engineering, Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , ,

    We consider nonlinear and nonsmooth mixing aspects in gas transport optimization problems. As mixed-integer reformulations of pooling-type mixing models already render small-size instances computationally intractable, we investigate the applicability of smooth nonlinear programming techniques for equivalent complementarity-based reformulations. Based on recent results for remodeling piecewise affine constraints using an inverse parametric quadratic programming approach, we … Read more

    On the Structure of Linear Programs with Overlapping Cardinality Constraints

  • Tobias Fischer
  • Marc E. Pfetsch
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , , ,

    Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid … Read more

    Computing Feasible Points for Binary MINLPs with MPECs

  • Lars Schewe
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities, Integer Programming Tags , , ,

    Nonconvex mixed-binary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use … Read more

    Monoidal Cut Strengthening and Generalized Mixed-Integer Rounding for Disjunctions and Complementarity Constraints

  • Tobias Fischer
  • Marc E. Pfetsch
    • Categories Integer Programming Tags , , ,

    In the early 1980s, Balas and Jeroslow presented monoidal disjunctive cuts exploiting the integrality of variables. This article investigates the relation of monoidal cut strengthening to other classes of cutting planes for general two-term disjunctions. We introduce a generalization of mixed-integer rounding cuts and show equivalence to monoidal disjunctive cuts. Moreover, we demonstrate the effectiveness … Read more

    Branch-and-Cut for Linear Programs with Overlapping SOS1 Constraints

  • Tobias Fischer
  • Marc E. Pfetsch
    • Categories Integer Programming Tags , , , , ,

    SOS1 constraints require that at most one of a given set of variables is nonzero. In this article, we investigate a branch-and-cut algorithm to solve linear programs with SOS1 constraints. We focus on the case in which the SOS1 constraints overlap. The corresponding conflict graph can algorithmically be exploited, for instance, for improved branching rules, … Read more