Discrete midpoint convexity: a unifying framework for convexity on the integer lattice (joint work with S. Moriguchi, K. Murota and A. Tamura)

01.04.2019 17:00 - 18:00 | HS 7 OMP1 (#1.303)

For a function defined on a convex set in a Euclidean space, midpoint convexity is the property requiring that the value of the function at the midpoint of any line segment is not greater than the average of its values at the endpoints of the segment. Under very mild assumptions, midpoint convexity is a well-known characterization of ordinary convexity. A discrete version of midpoint convexity is proposed here for functions defined on the integer lattice. A discrete midpoint point convex function is characterized by a discrete version of midpoint convexity where the value of the function at the (possibly noninteger) midpoint is replaced by the average of the function values at the integer round-up and round-down of the midpoint. We show that discrete midpoint convexity has nice theoretical and algorithmic properties, including (pseudo) polynomial-time minimization under appropriate assumptions. Furthermore, by restricting the distance between the endpoints in the discrete midpoint convexity definition, one obtains new classes of discretely convex functions and a unifying framework for several well-known notions of discrete convexity and for the notion of submodularity over the integer lattice. 

 Turnpike properties and strict dissipativity for linear optimal control problems

29.04.2019 16:45 - 18:00 | HS 7 OMP1 (#1.303)

 

Abstract: In the talk we present some recent results on the connection between turnpike behaviors and strict dissipativity properties for finite dimensional linear quadratic (LQ) optimal control problems. The focus is on providing characterizations of strict dissipativity and the newly introduced property of strict predissipativity in terms of the system matrices related to the LQ problem. These characterizations then lead to new necessary conditions for the turnpike properties under consideration, and thus eventually to necessary and sufficient conditions in terms of spectral criteria and matrix inequalities. In particular, the techniques allow to encompass the presence of state and input constraints. Finally, several examples illustrate the different turnpike behaviors of the system in the presence or absence of constraints. The talk is based on joint works with Lars Grüne from University ofBayreuth [1,2].

[1] L. Grüne and R. Guglielmi. Turnpike properties and strict dissipativity for discrete time linear quadratic optimal control problems. SIAM Journal on Control and Optimization (SICON), 1–21, 2018.

[2] L. Grüne and R. Guglielmi. Turnpike and strict dissipativity properties for continuous time linear quadratic optimal control problems. preprint, 2019.

 Stable Matching Models with Applications to Junior Doctor Allocation and Children Adoption

06.05.2019 17:00 - 17:45 | HS 7 OMP1 (#1.303)

In a stable matching problem, we are given two sets of agents, each of whom ranks some (or all) the members of the other set in order of preference, indicating their level of desire to be matched to each other. A solution to the problem is a pairing of all agents such that no two agents form a blocking pair, that is, a pair that are not currently matched together, but would prefer to be matched to each other rather than to their currently assigned partners. In this talk I will introduce new models for the Stable Marriage problem with Ties and Incomplete lists, with applications to pairing children with adoptive families, and for its many-to-one generalization, the Hospitals/Residents Problem with Ties, with applications to the allocation of junior doctors. 

 An Exact Solution Framework for Multi-Trip Vehicle Routing Problems with Time Windows

13.05.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)

Multi-Trip Vehicle Routing Problems (MTVRP) generalize the well-known VRP by allowing vehicles to perform multiple trips per day. MTVRPs have received a lot of attention lately because of their relevance in real-life applications, e.g., in city logistics and last-mile delivery. Several variants of the MTVRP have been investigated in the literature, and a number of exact methods have been proposed. Nevertheless, the computational results currently available suggest that MTVRPs with different side-constraints require ad-hoc formulations and solution methods to be solved. Moreover, solving instances with just 25 customers can be out of reach for such solution methods. In this talk, we proposed an exact solution framework to address four different MTVRPs proposed in the literature. The exact solution framework is based on a novel formulation that has an exponential number of variables and constraints. It relies on column generation, column enumeration, and cutting plane. We show that this solution framework can solve instances with up to 50 customers of four MTVRP variants and outperforms the state-of-the-art methods from the literature.

 A Kernel Search Heuristic for the Multi-Vehicle Inventory Routing Problem (joint work with G. Guastaroba, D. L. Huerta-Muñoz, M. Grazia Speranza)

20.05.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)

We study an inventory routing problem where the goal is to determine an opti-mal distribution plan to replenish a set of customers, by routing a limited fleet ofcapacitated vehicles over a discrete planning horizon. Each customer consumes aper period quantity of products and have a maximum inventory capacity. Productscan be distributed by a supplier to the customers in advance compared to theirconsumption, provided that their inventory capacity is not violated. The goal is tominimize the total distribution cost, that comprises the routing and the inventorycosts. We develop a novel matheuristic approach to solve this problem. The algo-rithm is based on Kernel Search (KS), a heuristic framework that has been shownto find high-quality solutions for a number of combinatorial optimization problems.The basic idea of KS is to identify subsets of the decision variables and then solving,using a general-purpose solver, a sequence of Mixed-Integer linear Programs (MIPs),each one restricted to a subset of variables. Extensive computational experimentsare conducted on a very large set of benchmark instances. The results show thatKS outperforms state-of-the-art heuristic algorithms. It finds 103 new best-knownsolutions out of 240 large-scale instances. 

 Two Resource Allocation Problems in Global Health

27.05.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)

This talk will focus on a resource allocation of healthcare resources in low and middle income countries. The talk is stimulated by consultancy work for a major donor of development aid. We will discuss two problems - one of balancing "vertical" investments in disease programmes (such as purchasing bednets for malaria) with investments which strengthen the health system as a whole (e.g. improving systems for vital registration); the other of deciding the correct balance of funding between a donor and a recipient. We will model these problems with quadratic and bilevel programmes respectively and discuss the structural behaviour of such models. 

 On mixed integer nonlinear optimization to interpret and visualize complex datasets

17.06.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)

Extracting knowledge from data, such as dependencies, global underlying patterns or unusual behaviors, has become a crucial task for analysts to improve decision making. Nevertheless, the increase in data complexity has made, in some cases, the classic statistical models obsolete, and more sophisticated frameworks are thus needed. In this context, Mathematical Optimization plays an important role, both developing new models and algorithmic approaches as well as creating new frameworks, which gain insight into specific datasets' features and cope with nowadays requirements. In this talk, we discuss how mixed integer nonlinear programming helps to interpret and visualize data involving time-varying frequencies and proximities. 

INFORMS TSL Workshop 2019

Date: July 15-18, 2019
Location: Sky Lounge at the Faculty of Business, Economics and Statistics

The next INFORMS TSL Workshop will be held from July 15-18, 2019 at the University of Vienna. The topic of the workshop is "Transportation in the sharing economy". Sharing economy refers to collaborative consumption. It is typically organized through platforms that facilitate the exchange of goods or services. Given an increasing pressure to act economically and ecologically efficient, mechanisms that help to benefit from idle capacities are on the rise. Both transportation companies and heavy users of transportation services need to learn how to play in a world of shared idle capacities. We anticipate talks on various types of collaborations, crowd delivery, carsharing, carpooling, ridesharing, etc.