Journées de l'optimisation 2007 Optimizations days

Let A(n,d) denote the largest possible average diameter of a bounded cell of a simple arrangement defined by n hyperplanes in dimension d. We have A(n,2) less or equal than 2n/(n-1) in the plane, and A(n,3) less or equal than (3n+1)/(n-1) in dimension 3. In general, the average diameter of a bounded cell of a simple arrangement is conjectured to be less than the dimension; that is, A(n,d) less or equal than d. We propose a hyperplane arrangement with (n-d choose d) cubical cells for n>2d-1. It implies that the dimension d is an asymptotic lower bound for A(n,d) for fixed d. In particular, we propose line and plane arrangements with large average diameter yielding that A(n,2) is greater or equal than 2-(n+1)/(n-1)(n-2) and A(n,3) is greater or equal than 3(n-3)/(n-1)+3(n-4)/(n-1)(n-2)(n-3).

Open pit optimization typically involves two phases: designing the ultimate pit, then breaking up the ultimate pit into smaller more manageable pieces known as pushbacks. Existing methods for designing pushbacks suffer from large size differences between pushbacks. We discuss complexity results related to the pushback design problem.

The concept of data depth in non-parametric multivariate descriptive statistics is the generalization of the univariate rank method to multivariate data. Halfspace depth is a measure of data depth. Given a set S of points and a point p, the halfspace depth (or rank) k of p is defined as the minimum number of points of S contained in any closed halfspace with p on its boundary. Computing halfspace depth is NP-hard, and it is equivalent to the Maximum Feasible Subsystem problem. In this thesis a mixed integer program is formulated with the big-M method for the halfspace depth problem. We suggest a branch and cut algorithm. In this algorithm, Chinneck's heuristic algorithm is used to find an upper bound and a related technique based on sensitivity analysis is used for branching. Irreducible Infeasible Subsystem (IIS) hitting set cuts are applied. We also suggest a binary search algorithm which may be more stable numerically. The algorithms are implemented with the BCP framework from the COIN-OR project.