On Sparse Canonical Correlation Analysis

The classical Canonical Correlation Analysis (CCA) identifies the correlations between two sets of multivariate variables based on their covariance, which has been widely applied in diverse fields such as computer vision, natural language processing, and speech analysis. Despite its popularity, CCA can encounter challenges in explaining correlations between two variable sets within high-dimensional data contexts. … Read more

A widespread belief about county splits in political districting plans is wrong

Consider the task of dividing a state into k contiguous political districts whose populations must not differ by more than one person, following current practice for congressional districting in the USA. A widely held belief among districting experts is that this task requires at least k-1 county splits. This statement has appeared in expert testimony, … Read more

Optimal counterfactual explanations for k-Nearest Neighbors using Mathematical Optimization and Constraint Programming

\(\) Within the topic of explainable AI, counterfactual explanations to classifiers have received significant recent attention. We study counterfactual explanations that try to explain why a data point received an undesirable classification by providing the closest data point that would have received a desirable one. Within the context of one the simplest and most popular … Read more

A Family of Spanning-Tree Formulations for the Maximum Cut Problem

We present a family of integer programming formulations for the maximum cut problem. These formulations encode the incidence vectors of the cuts of a connected graph by employing a subset of the odd-cycle inequalities that relate to a spanning tree, and they require only the corresponding edge variables to be integral explicitly. They so describe … Read more

QUBO Dual Bounds via SDP Plane Projection Method

In this paper, we present a new method to solve a certain type of Semidefinite Programming (SDP) problems. These types of SDPs naturally arise in the Quadratic Convex Reformulation (QCR) method and can be used to obtain dual bounds of Quadratic Unconstrained Binary Optimization (QUBO) problems. QUBO problems have recently become the focus of attention … Read more

Approximating the Pareto frontier for bi-objective preventive maintenance and workshop scheduling. A Lagrangean lower bounding methodology for evaluating contracting forms

Effective planning of preventive maintenance plays an important role in maximizing the operational readiness of any industrial system. We consider an operating system and a maintenance workshop governed by two stakeholders who collaborate based on a mutual contract: components of the operating system that need maintenance are sent to the maintenance workshop, where necessary maintenance … Read more

Computational Guarantees for Restarted PDHG for LP based on “Limiting Error Ratios” and LP Sharpness

In recent years, there has been growing interest in solving linear optimization problems – or more simply “LP” – using first-order methods in order to avoid the costly matrix factorizations of traditional methods for huge-scale LP instances. The restarted primal-dual hybrid gradient method (PDHG) – together with some heuristic techniques – has emerged as a … Read more

On the Relation Between LP Sharpness and Limiting Error Ratio and Complexity Implications for Restarted PDHG

There has been a recent surge in development of first-order methods (FOMs) for solving huge-scale linear programming (LP) problems. The attractiveness of FOMs for LP stems in part from the fact that they avoid costly matrix factorization computation. However, the efficiency of FOMs is significantly influenced – both in theory and in practice – by … Read more

Convergence Rate of Projected Subgradient Method with Time-varying Step-sizes

We establish the optimal ergodic convergence rate for the classical projected subgradient method with time-varying step-sizes. This convergence rate remains the same even if we slightly increase the weight of the most recent points, thereby relaxing the ergodic sense. Article Download View Convergence Rate of Projected Subgradient Method with Time-varying Step-sizes

Convergence of the Chambolle–Pock Algorithm in the Absence of Monotonicity

The Chambolle-Pock algorithm (CPA), also known as the primal-dual hybrid gradient method (PDHG), has surged in popularity in the last decade due to its success in solving convex/monotone structured problems. This work provides convergence results for problems with varying degrees of (non)monotonicity, quantified through a so-called oblique weak Minty condition on the associated primal-dual operator. … Read more