Motivated by settings such as medical treatments or aircraft maintenance, we consider a scheduling problem with jobs that consist of two operations, a test and a processing part. The time required to execute the test is known in advance while the time required to execute the processing part becomes known only upon completion of the test. We use competitive analysis to study algorithms for minimizing the sum of completion times for $n$ given jobs on a single machine. As our main result, we prove using a novel analysis technique that the natural 1-SORT algorithm has competitive ratio at most 1.861. For the special case of uniform test times, we show that a simple threshold-based algorithm has competitive ratio at most 1.585. We also prove a lower bound that shows that no deterministic algorithm can be better than $\sqrt{2}$-competitive even in the case of uniform test times.

In the Job Sequencing and Tool Switching Problem (SSP), a single flexible machine with a capacitated tool magazine has to process a set of jobs, each requiring a specific set of tools. The SSP aims to simultaneously determine the processing sequence and the subsets of tools present in the magazine for each job in order to minimize the total number of tool switches. We propose a new Quadratic Travelling Salesman Problem-based formulation for the SSP. We then develop an exact method, which decomposes the problem into a Master Problem (MP) for determining the processing sequence, and a Sub Problem (SP) for determining the subsets of tools present in the magazine for each job. Optimality cuts, generated by the SP, are dynamically added to the MP to gradually obtain a tighter approximation of the objective function at the optimal solution. Computational tests on instances from the literature were performed to evaluate the effectiveness of the proposed approach.

In the correlation clustering problem, we are given a complete graph
with each edge labeled as + (similar) or - (dissimilar). The goal is
to find a clustering (a partition) of the vertices that minimizes the
number of dissimilar intracluster edges and the number of similar
intercluster edges. Until recently, the best known approximation
guarantee was 2.06, based on a modification of the natural LP-based pivot
algorithm. We now know how to go below 1.5 using various new tools
and insights. In this talk, we will give an overview of these recent
developments for the correlation clustering problem.

Large-scale optimization algorithms frequently require sparse Hessian matrices that are not readily available. Existing methods for approximating large sparse Hessian matrices either do not impose sparsity or are computationally prohibitive. To try and overcome these limitations, we propose a novel approach that seeks to satisfy as many componentwise secant equations as necessary to define each row of the Hessian matrix. A naive application of this approach is prohibitively expensive on Hessian matrices that have some relatively dense rows, but by carefully taking into account the symmetry and connectivity of the Hessian matrix we are able devise an approximation algorithm that is fast and efficient with scope for parallelism. Example sparse Hessian matrices from the CUTEst test problem collection for optimization illustrate the effectiveness and robustness of our proposed method.