Demand-Responsive Transport (DRT) has grown over the last decade as an ecological solution to both metropolitan and suburban areas. It provides a more efficient public transport service in metropolitan areas and satisfies the mobility needs in sparse and heterogeneous suburban areas. Traditionally, DRT operators build the plannings of their drivers by relying on myopic insertion heuristics that do not take into account the dynamic nature of such a service. We thus investigate in this work the potential of a Demand Prediction Framework used specifically to build more flexible routes within a Dynamic Dial-a-Ride Problem (DaRP) solver. We show how to obtain a Machine Learning forecasting model that is explicitly designed for optimization purposes. The prediction task is further complicated by the fact that the historical dataset is significantly sparse. We finally show how the predicted travel requests can be integrated within an optimization scheme in order to compute better plannings at the start of the day. Numerical results support the fact that, despite the data sparsity challenge as well as the optimization-driven constraints that result from the DaRP model, such a look-ahead approach can improve up to 3.5% the average insertion rate of an actual DRT service.

The Optimal Power Flow (OPF) problem is a central optimization problem in power systems. Its global resolution is a challenge since it is highly nonconvex and NP-hard. Semidefinite Programming (SDP) is a powerful tool to progress towards global optimality as semidefinite relaxations provide tight lower bounds for the OPF problem. However, solving semidefinite relaxations for large power networks is very costly, because it is required to exploit its sparsity for achieving this aim. One efficient way to exploit sparsity for the OPF problem is to use clique decomposition techniques along with state-of-the-art interior point algorithms. Yet many clique decompositions can be computed for the same sparse SDP problem, their performance can significantly varies in practice. In this context, it is crucial to identify a good decomposition, where by good we mean a decomposition that allows to solve the SDP relaxation of the OPF problem in a small amount of time. At the moment, it is not possible in the literature to find a systematic analysis that allows to characterize in detail the properties of a good decomposition, the works proposed so fare relies on the basic assumption that there is a trade-off between the size and the number of the cliques: a decomposition with only one large clique is problematic because of memory issues but a decomposition with many tiny cliques is not advisable either as it implies lots of linking constraints, which slows down the resolution. In this work, we propose to use machine learning techniques to understand what are the characteristics of a good clique decomposition. More precisely, we propose to identify the relevant features to describe a good clique decomposition, using both classification and regression approaches. The results show that the decomposition identified with the proposed techniques are comparable with the state of the art.

Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branch-and-bound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems to obtain a tailored coordinate-descent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both CPLEX and the related QCR method as well as the SDP-based software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem.