Linear bilevel optimization problems are known to be strongly NP-hard and the computational techniques to solve these problems are often motivated by techniques from single-level mixed-integer optimization. Thus, during the last years and decades many branch-and-bound methods, cutting planes, or heuristics have been proposed. On the other hand, there is almost no literature on presolving … Read more
We give safe screening rules to eliminate variables from regression with L0 regularization or cardinality constraint. These rules are based on guarantees that a feature may or may not be selected in an optimal solution. The screening rules can be computed from a convex relaxation solution in linear time, without solving the L0 optimization problem. … Read more
In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolving techniques successfully is … Read more
This paper draws from our experience in developing the AMPL modeling language, to show where numerical issues have been crucial to modeling language design and where modeling language advances have strongly influenced the design of solvers. CitationProceedings of the 20th Biennial Conference on Numerical Analysis, Dundee, Scotland, D.F. Griffiths and G.A. Watson, eds., University of … Read more
AMPL is a language and environment for expressing and manipulating mathematical programming problems, i.e., minimizing or maximizing an algebraic objective function subject to algebraic constraints. AMPL permits separating a model, i.e., a symbolic representation of a class of problems, from the data required to specify a particular problem instance. Once AMPL has a problem instance, … Read more