joint work with Nikolaos Sahinidis, Nikolaos Samaras
This paper addresses the computation of an initial basis for the simplex algorithm for linear programming. We propose six algorithms for constructing an initial basis that is sparse and will reduce the fill-in and computational effort during LU factorization and updates. Over a set of 62 large benchmarks, the best proposed algorithm produces remarkably sparse starting bases. Taking into account only the hard instances, the proposed algorithm results in 23% and 30% reduction of the geometric mean of the execution time of CPLEX's primal and dual simplex algorithm, respectively.
joint work with Ramzi Ben Mhenni, Sebastien Bourguignon
Finding low-cardinality solutions to least-squares problems has found many applications in signal processing. We propose a branch-and-bound algorithm for global optimization of cardinality-constrained and cardinality-penalized least-squares, and cardinality minimization under quadratic constraints. A tree-search exploration strategy is built based on forward selection heuristics, and the continuous relaxation problems are solved with a dedicated algorithm inspired by homotopic methods. On all conducted experiments, our algorithms at least equal and often outperform the MIP solver CPLEX.
joint work with Ahdam Stoltz
The special and unique features of this problem are then shown to be: the need to perform scheduling on a batch basis every day, without knowledge of what will occur the following day and also the requirement that resources (call centre capacity) are fully utilized and not exceeded. The result of the research is that a new mathematical model called the Critical Time Window Resource Levelling Problem (CTWRLP) with the Continual Rescheduling method is developed and proposed as a method for solving the real world scheduling problem.