Time: Wednesday, 04/Sept/2024: 4:30pm - 6:00pm Session Chair: Elisabeth Gaar |
Location: Wirtschaftswissenschaften Z536 External Resource for This Session |
Leveraging Semi-Definite Programming for Multi-Objective Single-Row Facility Layout Problems
1Johannes Kepler University Linz, Austria; 2Universtiy of Augsburg, Germany
In the single-row facility layout problem (SRFLP), the goal is to arrange a set of facilities along a single line to minimize the sum of the weighted distance between facilities.
The SRFLP is a well-known combinatorial optimization problem with many practical applications in industrial engineering, health care, office design, and other fields.
In these fields, the SRFLP is often extended to a multi-objective optimization problem, where multiple conflicting objectives need to be considered simultaneously, such as the total
material handling cost, flow distance or CO2 emissions.
For the single objective SRFLP semi-definite programs (SDP) have been proven to be a powerful tool to solve the problem. In this work, we propose a novel approach that leverages the power of SDP to solve the multi-objective SRFLP. In particular, we combine objective space techniques, such as the weighted sum method and the epsilon-constraint method with SPDs. We conduct a computational study to compare our approach with objective space methods using integer programming formulations on modified benchmark instances from
the literature.
On solving submodular interdiction games via branch-and-cut
1Institute of Business Analytics and Technology Transformation, Johannes Kepler University Linz, Austria; 2Department of Industrial Engineering, Koc University, Istanbul, Turkey
Many relevant applications from diverse areas such as marketing, wildlife conservation, and defending critical infrastructure can be modeled as interdiction games. In this talk, we consider interdiction games whose objective function is a monotone and submodular set function. Given a ground set of items, the follower seeks to maximize this function subject to knapsack constraints. Given an interdiction budget, the leader interdicts the usage of some of the items of the follower and the follower can only use the non-interdicted items in her maximization. The goal of the leader is to select the items to interdict in such a way that the objective value achievable by the follower is minimized. We present an exact branch-and-cut algorithm for this kind of interdiction game. The algorithm is based on interdiction cuts, which exploit the submodularity of the objective function and allow the leader to capture the follower's objective function value for a given interdiction decision of the leader. We also discuss extensions and liftings of these cuts and additional preprocessing procedures. We present a computational study on the weighted maximal covering interdiction game and the bipartite inference interdiction game.
Tackling a class of integer bilevel nonlinear programs with disjunctive cuts based on SOCP
1University of Augsburg, Germany; 2University of Michigan, Ann Arbor, Michigan, USA; 3ESSEC Business School of Paris, France; 4Institute of Business Analytics and Technology Transformation, Johannes Kepler University Linz, Austria; 5Department of Industrial Engineering, Koc University, Istanbul, Turkey
We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. Using these DCs, we propose a branch-and-cut algorithm for the problem class we study, and a cutting-plane method for the problem variant with only binary variables. A computational study demonstrates that both of our approaches outperform a state-of-the-art generic solver.