Dipartimento di Ingegneria informatica, automatica e gestionale

Titolo: "A Dual Step for Improving Alternating Augmented Lagrangian Methods for Semidefinite Programming"

Speaker:  Marianna De Santis
(Joint work with Franz Rendl e Angelika Wiegele)

Abstract:
"It is well known that SDP problems are solvable in polynomial time by interior point methods (IPMs). However, if the number of constraints m in an SDP is of order O(n^2), when the unknown positive semidefinite matrix is n × n, interior point methods become impractical both in terms of the time and the amount of memory required at each iteration. As a matter of fact, in order to compute the search direction, IPMs need to form the m × m positive definite Schur complement matrix M and find its Cholesky factorization.
On the other hand, first-order methods typically require much less computation effort per iteration, as they do not form or factorize these large dense matrices.Furthermore, some first-order methods are able to take advantage of problem structure such as sparsity. Hence, they are often more suitable, and sometimes the only practical choice for solving large-scale SDPs.
Most existing first-order methods for SDP are based on the augmented Lagrangian method. Alternating direction augmented Lagrangian (ADAL) methods usually perform a projection onto the cone of semidefinite matrices at each iteration.
With the aim of improving the convergence rate of ADAL methods, we propose to update the dual variables before the projection step. Numerical results are shown on both random instances and on instances for the computation of the Lovàsz theta number, giving some insights on the benefits of the approach."

Titolo: "A heuristic method to solve the challenging Sales Based Integer Program for Network Airlines Revenue Management"

Abstract:
"Revenue Management (RM) has been playing over recent years an increasingly crucial role in both strategic and tactical decisions of Airlines business. Successful RM processes aim to achieve the maximization of revenue by leveraging huge amount of data, upcoming technologies and more sophisticated approaches to measure the RM performances. Multiple phases of RM processes, as well as different components of RM systems, are based on the solution of large integer programming models, like the well-known Sales Based Integer Program (SBIP), whose instances turn out to be challenging, or even not solvable in practice by the state-of-art MIP solvers.
Our work aims to investigate useful polyhedral properties and introduce a practical heuristic method to find a good solution of hard instances of SBIP. We use a LP-based branch-and-bound paradigm. Firstly, we strengthen the linear relaxations of subproblems by introducing effective Chvátal-Gomory cuts, exploiting the structure of the polytope.
Our main contribution consists in the decomposition of the SBIP into two stage MINLP smaller problems. The basic idea is to separate the optimal allocation of the capacity to the markets and then to split it among the different travel options on each market, differently from the traditional leg-based decomposition. This leads to the formulation of the market subproblems as piecewise linear problem. We define a concave approximation of the piecewise linear objective function in order to reach a good solution in reasonable time. Decomposition ensures a radical reduction of the dimension of the problem instances, both the number of variables and of constraints, while the concave approximation reduces computational times for the solution of each subproblems. Computational results are reported. "