Monday, August 29, Deterministic Optimization
Workshop Chair: Santanu Dey
Time: 9:00 – 10:25
Speaker: George Lan
Title: Introduction to stochastic gradient descent.
Abstract: We provide a brief introduction to stochastic gradient descent (SGD) meth- ods, including mirror-descent stochastic approximation and accelerated stochastic ap- proximation, for solving both convex and nonconvex problems. We show that these methods have evolved into popular algorithms for machine learning, including deep learning.
Time: 10:35 – 12:00
Speaker: Natashia Boland
Title: Multiobjective Integer Programming
Abstract: In the last few years, there has been increased interest in algorithms for solving general multiobjective integer linear programs, especially those with a small number of objectives (2 or 3). The aim of these algorithms is to find the complete efficient frontier: the points at which no one objective can be improved without worsening another. Such problems are of great interest in many fields, where trade-offs must be made, between, for example, reliability and cost, or environmental impact and quality of service, or quality of life and cost of treatment. Decision-makers wish to see the efficient frontier in order to select a desirable trade-off point, since the efficient frontier identifies the set of trade-offs that are achievable. This talk provides an introduction to the concepts of multiobjective integer linear programming, and gives an overview of recent algorithms, with an emphasis on algorithms that operate in the space of the objectives (criterion space), rather than in the space of the decision variables. While the latter have great potential, algorithms that operate in the criterion space can ex- ploit the power of modern integer programming solvers, and have, to date, proved most effective.
Time: 12:00 – 13:30 – Lunch
Time: 13:30 – 14:00
Speaker: Roberto Pinto
Title: A derivative free method for a profit satisfying objective problem
Abstract: The talk discusses a rationing problem with a profit satisficing objective in a company operating many retail stores through a centralized procurement. General rationing problems arise when the available stock or capacity cannot guarantee the possibility to satisfy the demand in full, and different decisions about the allocation of the available resources may lead to different profit results. Therefore, the appropriate allocation of the stock or capacity can have a substantial impact on the companys profit. Unlike other works in the rationing area, the talk considers a profit satisficing objective, which entails maximizing the probability of achieving a pre-specified profit target. This type of objective is sometimes preferable to maximizing the expected profit. The problem is modelled in an analytical form, for which closed-form solutions can be hard to compute. Thus, the conditions for achieving the satisficing objective are discussed, and two heuristic procedures are compared: one exploiting the structure of the problem and resulting in a greedy, marginal unit allocation; the other, based on the Nelder Mead derivative-free method.
Time: 14:00 – 14:30
Speaker: Andy Sun
Title: Optimal Power flow problem
Abstract: The AC optimal power flow (OPF) problem is a key optimization prob- lem in the area of electrical power systems operations. We compare the strength of linear programing (LP), second order cone programming (SOCP) and semi-definite relaxations (SDP) of two formulations of the OPF formulation. Then we present a few families of cutting-planes to strengthen the (standard) SOCP relaxation of this problem. The strengthened SOCP relaxation is incomparable to the (standard) SDP relaxation. Extensive computational experiments show that these relaxations have nu- merous advantages over existing convex relaxations in the literature: (i) their solution quality is extremely close to that of the SDP relaxations and consistently outperforms previously proposed convex quadratic relaxations of the OPF problem, and (ii) in terms of computation times, the strengthened SOCP relaxations can be solved an order of magnitude faster than standard SDP relaxations.
Time: 14:45 – 15:15
Speaker: Maria-Teresa Vespucci
Title: Optimal operation of medium-voltage AC networks with distributed generation and storage devices
Abstract: A Distribution System Operator (DSO) will be in charge of operating power distribution networks, in order to compensate generation-load imbalances with respect to a previously determined scheduling, while guaranteeing constraints on currents in lines for security and voltages at nodes for power quality. Internal (i.e. owned by DSO) regulation resources will be electricity storage devices and on-load tap changers. DSO’s external regulation resources (i.e. owned by third parties) will be the dispatch of active and reactive power of generation plants and the exchange of active and reactive power
with the high voltage transmission network. Costs associated to the use of internal regulation resources reflect device deterioration; costs associated to the use of external regulation resources are to be defined by the Regulator, so as to allow a technically efficient operation of the network. The optimal redispatch minimizes the total costs for using internal and external resources, constrained by power flow equations, balance equation for the batteries and local control constraints. Active losses are also considered and penalized in the objective function. The problem is modeled by using a non linear sparse formulation and solved using a primal-dual interior point method. The procedure allows finding efficient configurations of the network and can be used as a simulation tool by the Regulator to analyze the impact of different costs associated to external regulation resources.
Time: 15:15 – 15:45
Speaker: Santanu S. Dey
Title: Aggregation-based cutting-planes for packing and covering integer programs
Abstract: We study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: Given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined by this single inequality with variable bounds, and finally use the inequalities describing the integer hull as cutting-planes. Our first main result is to show that for packing and covering IPs, the CG and aggregation closures can be 2- approximated by simply generating the respective closures for each of the original formulation constraints, without using any aggregations. On the other hand, we use computational experiments to show that aggregation cuts can be arbitrarily stronger than cuts from individual constraints for general IPs. The proof of the above stated results for the case of covering IPs with bounds require the development of some new structural results, which may be of independent interest. Finally, we examine the strength of cuts based on k different aggregation inequalities simultaneously, the so-called multi-row cuts, and show that every packing or covering IP with a large integrality gap also has a large k-aggregation closure rank. In particular, this rank is always at least of the order of the logarithm of the integrality gap.
Time: 16:00 – 16:30
Speaker: Renato Monteiro Title:
Time: 16:30 – 17:30
Speaker: Merve Bodur
Title: Decomposition for loosely coupled integer programs: A multiobjective perspec- tive
Abstract: We consider integer programming (IP) problems consisting of (possibly a large number of) interrelated subsystems and a small number of coupling constraints which link blocks of variables that correspond to different subsystems. Such problems are called loosely coupled or nearly-decomposable. Motivated by recent developments in multiobjective programming (MOP), we develop a MOP-based decomposition al- gorithm to solve loosely coupled IPs. More specifically, we reformulate the problem in such a way that it can be decomposed into a (resource-directive) master problem and a set of MOP subproblems. The proposed algorithm is a column generation algo- rithm. However, it is based on a new lower bounding problem (which is an IP), and considers a more structured (and usually smaller) set of columns than a traditional col- umn generation algorithm. We provide preliminary computational results on instances with knapsack structure in the subsystems, demonstrating the potential benefits of our approach.