Ted K. Ralphs

A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation

  • S.T. DeNegre
  • Ted K. Ralphs
  • S. Tahernejad
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems Tags , , ,

    In this paper, we describe an algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) by a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range … Read more

    A Complete Characterization of Disjunctive Conic Cuts for Mixed Integer Second Order Cone Optimization

  • Pietro Belotti
  • Julio C. Góez
  • Imre Pólik
  • Ted K. Ralphs
  • Tamás Terlaky
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming Tags , ,

    We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization problem. We extend our prior work on disjunctive conic cuts, which has thus far been restricted to the case in which the intersection of the hyperplanes and … Read more

    A Generalization of Benders’ Algorithm for Two-Stage Stochastic Optimization Problems With Mixed Integer Recourse

  • Anahita Hassanzadeh
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags ,

    We describe a generalization of Benders’ method for solving two-stage stochastic linear optimization problems in which there are both continuous and integer variables in the first and second stages. Benders’ method relies on finding effective lower approximations for the value function of the second-stage problem. In this setting, the value function is a discontinuous, non-convex, … Read more

    On the Value Function of a Mixed Integer Linear Optimization Problem and an Algorithm for its Construction

  • Anahita Hassanzadeh
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , ,

    This paper addresses the value function of a general mixed integer linear optimization problem (MILP). The value function describes the change in optimal objective value as the right-hand side is varied and understanding its structure is central to solving a variety of important classes of optimization problems. We propose a discrete representation of the MILP … Read more

    On Families of Quadratic Surfaces Having Fixed Intersections with Two Hyperplanes

  • Pietro Belotti
  • Julio C. Góez
  • Imre Pólik
  • Ted K. Ralphs
  • Tamás Terlaky
    • Categories Second-Order Cone Programming Tags , , ,

    We investigate families of quadrics that have fixed intersections with two given hyper-planes. The cases when the two hyperplanes are parallel and when they are nonparallel are discussed. We show that these families can be described with only one parameter. In particular we show how the quadrics are transformed as the parameter changes. This research … Read more

    A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization

  • Pietro Belotti
  • Julio C. Góez
  • Imre Pólik
  • Ted K. Ralphs
  • Tamás Terlaky
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming Tags , ,

    We study the convex hull of the intersection of a convex set E and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction … Read more

    Bilevel Programming and the Separation Problem

  • Andrea Lodi
  • Ted K. Ralphs
  • Gerhard J. Woeginger
    • Categories Cutting Plane Approaches, Integer Programming Tags , , ,

    In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is … Read more

    What Could a Million Cores Do To Solve Integer Programs?

  • Thorsten Koch
  • Ted K. Ralphs
  • Yuji Shinano
    • Categories Integer Programming, Parallel Algorithms Tags , ,

    Given the steady increase in cores per CPU, it is only a matter of time until supercomputers will have a million or more cores. In this article, we investigate the opportunities and challenges that will arise when trying to utilize this vast computing power to solve a single integer linear optimization problem. We also raise … Read more

    Interdiction Branching

  • Andrea Lodi
  • Ted K. Ralphs
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories 0-1 Programming, Branch and Cut Algorithms Tags , , , , , ,

    This paper introduces interdiction branching, a new branching method for binary integer programs that is designed to overcome the difficulties encountered in solving problems for which branching on variables is inherently weak. Unlike traditional methods, selection of the disjunction in interdiction branching takes into account the best feasible solution found so far. In particular, the … Read more

    Solution Methods for the Multi-trip Elementary Shortest Path Problem with Resource Constraints

  • Z. Akca
  • Ted K. Ralphs
  • R.T. Berger
    • Categories 0-1 Programming, Combinatorial Optimization, Transportation Tags , ,

    We investigate the multi-trip elementary shortest path problem (MESPPRC) with resource constraints in which the objective is to find a shortest path between a source node and a sink node such that nodes other than the specified replenishment node are visited at most once and resource constraints are not violated. After each visit to the … Read more