We construct sparse and structured generalized inverses, with application to the efficient computation of least-squares solutions of inconsistent systems of linear equations. Leveraging our earlier formulations to minimize the 1- and 2,1- norms of generalized inverses that satisfy important properties of the Moore–Penrose pseudoinverse, we develop efficient and scalable ADMM algorithms to address these norms minimization, and to limit the number of non-zero rows in the solution. We prove a 2,1-norm approximation result for a local-search procedure that we originally used for 1-norm minimization, and compare the ADMM algorithms with the local-search procedure and optimization solvers.

This work investigates the integration of machine scheduling and personnel allocation problems. In the machine scheduling problem one aims to find an optimal assignment of jobs to tasks in a given time horizon while only considering processing times and machine capacities in a time-discretized formulation. The goal of personnel allocation problems is to find the best employee allocation, considering business, regulatory, or satisfaction constraints (e.g., set the maximum time an employee can work in a specific activity, how long an employee can be in one particular activity without a period of rest, or which are the preferred days for work). Those two problems are intrinsically related and should ideally be considered together in a single monolithic formulation, though doing so is computationally challenging. This work presents a column generation-based algorithm (CG) used to find good quality solutions for an industrial-scale analytical services facility where integrated machine scheduling and personnel allocation decisions must be taken daily. Our computational results show that the proposed approach is able to consistently find high-quality solutions even when the size of the problem grows, and it outperforms other proposed approaches.

The study of triangulations of finite point configurations is a rich topic at the intersection of combinatorics, geometry, and optimization. It is well known that two point configurations A and B with identical oriented matroids (encoded by the set of circuits or cocircuits, equivalently) have the same set of triangulations. Given a triangulation T of A, we consider the coordinates of the points in A as parameters, and ask: which set of polynomial inequalities on the parameters ensures that T is a triangulation of A? That is, we are interested in the conditions under which A and B share a particular triangulation but not necessarily all triangulations. We show that, in low dimensions, a restricted set of cocircuits corresponding to hyperplanes spanned by facets of the simplices in T suffices. This gives convenient parametric volume formulas with few side conditions, with numerous obvious applications in cutting planes, computational biology and optimal control.

In the study of disjunctive programming, a critical aspect is the exploration of feasible regions formed by the union of multiple convex sets. The `big-M' method is well-established and often used (and abused) for formulating multiple-choice constraints. It is well-known that such formulations can be rather weak and also suffer from numerical instability, even when the big-M coefficients are chosen optimally. So, MILP/MINLP solvers often struggle with these formulations, while they are ubiquitous in MILP/MINLP applications. On the other hand, sometimes these formulations are best possible; that is, the inequalities can give a complete description of the convex-hull of the mixed-integer solutions, and we considered broad and useful situations where this is indeed the case. In such situations, the `big-M' inequalities can be derived by optimally lifting facet-describing inequalities of the disjunctive pieces.

Specifically, we study the natural extended-variable formulation for the disjunction of $n+1$ polytopes in $\mathbb{R}^d$. We demonstrate that the convex hull $D$ in the natural extended-variable space $\mathbb{R}^{d+n}$ is given by full optimal big-M lifting (i) when $d \leq 2$ (and that it is not generally true for $d \geq 3$), and also (ii) when the polytopes are all axis-aligned hyper-rectangles. We note that both of these cases are very natural for applications and within spatial branch-and-bound, the main algorithmic paradigm for mixed-integer nonlinear optimization. Additionally, we give further results on the polyhedral structure of $D$, giving very general conditions under which it is full dimensional and when the full optimal big-M liftings of the facet-describing inequalities for the individual polytopes describe facets of $D$.