Mixed Integer Nonlinear Optimization. Applications to Competitive Location and Supervised Classification

This PhD dissertation focuses on the study of Mixed Integer Nonlinear Programming (MINLP) problems [34] for two important and current applications: competitive location on networks [59, 64] and Support Vector Machines (SVM) [56, 152, 153]. Location problems on a network in a competitive environment were first introduced in [82]. They have been deeply studied in operations research and applied in problems such as market area analysis [122], demand estimation [123], or location of retail centres [78]. The SVM has proved to be one of the state-of-the-art methods for Supervised Classification [2, 6, 85, 160]. Successful applications of the SVM are found, for instance, in health care [22, 46, 81], fraud detection [43], credit scoring [113] and cancellations forecasting [138]. In its general form, an MINLP problem can be represented as: min f(x1, x2) s.t. gi(x1, x2) ≤ 0 ∀i = 1, . . . , I x1 ∈ Z n1 x2 ∈ R n2 , where n1 is the number of integer variables, n2 is the number of continuous variables, I is the number of constraints and f, gi are arbitrary functions such that f, gi : Z n1 ×R n2 → R. The general class of MINLP problems is composed by particular cases such as Mixed Integer Linear Programming (MILP) problems, when f, gi ∀i = 1, . . . , I are linear functions, Mixed Integer Quadratic Programming (MIQP) problems, when f is quadratic or Quadratically Constrained Quadratic Programming (QCQP) problems, when f, gi are quadratic functions. There are two main lines of research to solve this kind of problems: to develop packages for general MINLP problems [32, 55] or to exploit the specific structure of the problem. In this PhD dissertation we focus on the latter. Concerning the first application, we study the problem of locating one or several facilities on a competitive environment in order to maximize the market share. We study the single and p-facility Huff location model on a network and the single Huff origin-destination trip model [95]. Both models are formulated as MINLP problems and solved by a specialized branch and bound, where bounding rules are designed using DC (difference of convex) and Interval Analysis tools. In relation to the second application, we present three different SVM-type classifiers, focused either on robustness or interpretability. In order to build the classifier, different approaches are proposed based on the solution of MINLP problems, or particular cases of it such as MILP, MIQP or QCQP problems, and globally optimized using a commercial branch and bound solver [55, 100, 101]