preprocessing

Cover-based inequalities for the single-source capacitated facility location problem with customer preferences

  • Christina Büsing
  • Markus Leitner
  • Sophia Wrede
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    The single-source capacitated facility location problem with customer preferences (SSCFLPCP) is known to be strongly NP-hard and computational tests imply that state-of-the-art solvers struggle with computing exact solutions. In this paper, we contribute two novel preprocessing methods, which reduce the size of the considered integer programming formulation, and introduce sets of valid inequalities, which decrease the … Read more

    Mixed-Integer Linear Optimization for Cardinality-Constrained Random Forests

  • Jan Pablo Burgard
  • Maria Eduarda Pinheiro
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Optimization in Data Science Tags , , , ,

    Random forests are among the most famous algorithms for solving classification problems, in particular for large-scale data sets. Considering a set of labeled points and several decision trees, the method takes the majority vote to classify a new given point. In some scenarios, however, labels are only accessible for a proper subset of the given … Read more

    An efficient solution methodology for the airport slot allocation problem with preprocessing and column generation

  • Paula Fermín Cueto
  • Sergio García
  • Miguel F. Anjos
    • Categories Airline Optimization, Scheduling, Transportation Tags , , , ,

    Airport coordination is a demand control mechanism that maximizes the use of existing infrastructure at congested airports. Aircraft operators submit a list of regular flights that they wish to operate over a five to seven-month period and a designated coordinator is responsible for allocating the available airport slots, which represent the permission to operate a … Read more

    Revisiting Degeneracy, Strict Feasibility, Stability, in Linear Programming

  • Haesol Im
  • Henry Wolkowicz
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , , , , , ,

    Currently, the simplex method and the interior point method are indisputably the most popular algorithms for solving linear programs, LPs. Unlike general conic programs, LPs with a finite optimal value do not require strict feasibility in order to establish strong duality. Hence strict feasibility is seldom a concern, even though strict feasibility is equivalent to … Read more

    New algorithms for hierarchical optimisation in kidney exchange programmes

  • Maxence Delorme
  • Jacek Gondzio
  • William Pettersson
  • Sergio García
  • Joerg Kalcsics
  • David Manlove
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , , ,

    Kidney exchange programmes (KEPs) across the world help match donors and recipients to identify kidney transplantations. Almost all KEPs use a hierarchical set of objectives to determine an optimal set of transplants to perform, and integer linear programming is often used to find such optimal matchings. In this work, we identify the barriers in existing … Read more

    Improving solve times of stable matching problems through preprocessing

  • Maxence Delorme
  • Jacek Gondzio
  • William Pettersson
  • Sergio García
  • Joerg Kalcsics
  • David Manlove
    • Categories Combinatorial Optimization, Integer Programming, Optimization Software Benchmark Tags , , ,

    We present new theory, heuristics and algorithms for preprocessing instances of the Stable Marriage with Ties and Incomplete lists (SMTI), the Hospitals/Residents with Ties (HRT), and the Worker-Firms with Ties (WFT) problems. We show that instances of these problems can be preprocessed by removing from the preference lists of some agents entries that correspond to … Read more

    Preprocessing and Reduction for Degenerate Semidefinite Programs

  • Yuen-Lam Cheung
  • Simon P. Schurr
  • Henry Wolkowicz
    • Categories Optimization Software and Modeling Systems, Semi-definite Programming Tags , , ,

    This paper presents a backward stable preprocessing technique for (nearly) ill-posed semidefinite programming, SDP, problems, i.e.,~programs for which Slater’s constraint qualification, existence of strictly feasible points, (nearly) fails. Current popular algorithms for semidefinite programming rely on \emph{primal-dual interior-point, p-d i-p} methods. These algorithms require Slater’s constraint qualification for both the primal and dual problems. This … Read more

    New Turnpike Theorems for the Unbounded Knapsack Problem

  • Ping H. Huang
  • Thomas L. Morin
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We develop sharp bounds on turnpike theorems for the unbounded knapsack problem. Turnpike theorems specify when it is optimal to load at least one unit of the best item (i.e., the one with the highest “bang-for-buck” ratio) and, thus can be used for problem preprocessing. The successive application of the turnpike theorems can drastically reduce … Read more

    Constraint propagation on quadratic constraints

  • Ferenc Domes
  • Arnold Neumaier
    • Categories Bound-constrained Optimization, Quadratic Programming Tags , , , , , , , ,

    This paper considers constraint propagation methods for continuous constraint satisfaction problems consisting of linear and quadratic constraints. All methods can be applied after suitable preprocessing to arbitrary algebraic constraints. The basic new techniques consist in eliminating bilinear entries from a quadratic constraint, and solving the resulting separable quadratic constraints by means of a sequence of … Read more

    Rigorous enclosures of ellipsoids and directed Cholesky factorizations

  • Ferenc Domes
  • Arnold Neumaier
    • Categories Constrained Nonlinear Optimization Tags , , , , , , , , ,

    This paper discusses the rigorous enclosure of an ellipsoid by a rectangular box, its interval hull, providing a convenient preprocessing step for constrained optimization problems. A quadratic inequality constraint with a positive definite Hessian defines an ellipsoid. The Cholesky factorization can be used to transform a strictly convex quadratic constraint into a norm inequality, for … Read more