Shattering Inequalities for Learning Optimal Decision Trees

Recently, mixed-integer programming (MIP) techniques have been applied to learn optimal decision trees. Empirical research has shown that optimal trees typically have better out-of-sample performance than heuristic approaches such as CART. However, the underlying MIP formulations often suffer from weak linear programming (LP) relaxations. Many existing MIP approaches employ big-M constraints to ensure observations are … Read more

Recycling Valid Inequalities for Robust Combinatorial Optimization with Budget Uncertainty

Robust combinatorial optimization with budget uncertainty is one of the most popular approaches for integrating uncertainty into optimization problems. The existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is quite poor when … Read more

Constraint qualifications and strong global convergence properties of an augmented Lagrangian method on Riemannian manifolds

In the past years, augmented Lagrangian methods have been successfully applied to several classes of non-convex optimization problems, inspiring new developments in both theory and practice. In this paper we bring most of these recent developments from nonlinear programming to the context of optimization on Riemannian manifolds, including equality and inequality constraints. Many research have … Read more

Regularized methods via cubic subspace minimization for nonconvex optimization

\(\) The main computational cost per iteration of adaptive cubic regularization methods for solving large-scale nonconvex problems is the computation of the step \(s_k\), which requires an approximate minimizer of the cubic model. We propose a new approach in which this minimizer is sought in a low dimensional subspace that, in contrast to classical approaches, … Read more

A novel algorithm for a broad class of nonconvex optimization problems

In this paper, we propose a new global optimization approach for solving nonconvex optimization problems in which the nonconvex components are sums of products of convex functions. A broad class of nonconvex problems can be written in this way, such as concave minimization problems, difference of convex problems, and fractional optimization problems. Our approach exploits … Read more

Playing Stackelberg security games in perfect formulations

Protecting critical infrastructure from intentional damage requires foreseeing the strategies of possible attackers. The problem faced by the defender of such infrastructure can be formulated as a Stackelberg security game. A defender must decide what specific targets to protect with limited resources, maximizing their expected utility (e.g., minimizing damage value) and considering that a second … Read more

Integrating Order-to-Delivery Time Sensitivity in E-Commerce Middle-Mile Consolidation Network Design

This paper proposes an approach that leverages data on customer purchasing sensitivity to quoted order-to-delivery times (ODTs) when designing middle-mile consolidation networks to maximize the profit of e-commerce retailers. Our approach integrates quoted ODT-dependent sales volume predictions into a new mixed-integer program (MIP) that simultaneously determines ODT quotes and a consolidation plan, characterized by the … Read more

Exploiting user-supplied Decompositions inside Heuristics

Many mixed-integer models are sparse and can, therefore, usually be decomposed into weakly connected blocks. Such decompositions could be determined algorithmically or be specified by the user. We limit ourselves to the later, as the user usually has a very precise idea of which decomposition makes sense for structural reasons. In the present work, we … Read more

The Vehicle Routing Problem with Access Restrictions

To mitigate the negative effect of freight vehicles on urban areas, many cities have implemented road accessibility restrictions, including limited traffic zones, which restrict access to specific areas during certain times of the day. Implementing these zones creates a trade-off between the delivery cost and time, even under the assumption of equal traversal time and … Read more