Operations Research Proceedings 2015

Inhaltsverzeichnis

1. Frontmatter

2. Award Winners

   1. Frontmatter

   2. Exploiting Solving Phases for Mixed-Integer Programs

      Gregor Hendel

      Abstract

      Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.

   3. An Extended Formulation for the Line Planning Problem

      Heide Hoppmann

      Abstract

      In this paper we present a novel extended formulation for the line planning problem that is based on what we call “configurations” of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.

   4. Improving the Performance of MIP and MINLP Solvers by Integrated Heuristics

      Timo Berthold

      Abstract

      This article provides an overview of the author’s dissertation (Berthold, Heuristic algorithms in global MINLP solvers, 2014, [4]). We study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. This comprises generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP.

3. Discrete Optimization, Integer Programming, Graphs and Networks

   1. Frontmatter

   2. An Experimental Study of Algorithms for Controlling Palletizers

      Frank Gurski, Jochen Rethmann, Egon Wanke

      Abstract

      We consider the FIFO Stack-Up problem which arises in delivery industry, where bins have to be stacked-up from conveyor belts onto pallets. Given k sequences \(q_1, \ldots , q_k\) of labeled bins and a positive integer p. The goal is to stack-up the bins by iteratively removing the first bin of one of the k sequences and put it onto a pallet located at one of p stack-up places. Each of these pallets has to contain bins of only one label, bins of different labels have to be placed on different pallets. After all bins of one label have been removed from the given sequences, the corresponding stack-up place becomes available for a pallet of bins of another label. The FIFO Stack-Up problem is computational intractable (Gurski et al., Math. Methods Oper. Res., [3], ACM Comput. Res. Repos. (CoRR), 2013, [4]). In this paper we consider two linear programming models for the problem and compare the running times of our models for randomly generated sequences using GLPK and CPLEX solvers. We also draw comparisons with a breadth first search solution for the problem (Gurski et al.,Modelling, Computation and Optimization in Information Systems and Management Sciences, 2015, [7]).

   3. Robust Two-Stage Network Problems

      Adam Kasperski, Paweł Zieliński

      Abstract

      In this paper a class of network optimization problems is discussed. It is assumed that a partial solution can be formed in the first stage, when the arc costs are precisely known, and completed optimally in the second stage, after a true second-stage cost scenario occurs. The robust min-max criterion is used to compute an optimal solution. Several complexity results for the interval and discrete uncertainty representations are provided.

   4. Composed Min-Max and Min-Sum Radial Approach to the Emergency System Design

      Marek Kvet, Jaroslav Janáček

      Abstract

      This paper deals with the emergency service system design, where not only the disutility of an average user is minimized, but also the disutility of the worst situated user must be considered. Optimization of the average user disutility is often related to the weighted p-median problem. To cope with both objectives, we have suggested a composed method. In the first phase, the disutility of the worst situated user is minimized. The second phase is based on the min-sum approach to optimize the average user’s disutility. The result of the first phase is used here to reduce the model size. We focus on effective usage of the reduction and explore the possibility of a trade-off between a little loss of optimality and computational time.

   5. LP-Based Relaxations of the Skiving Stock Problem—Improved Upper Bounds for the Gap

      John Martinovic, Guntram Scheithauer

      Abstract

      We consider the one-dimensional skiving stock problem (SSP) which is strongly related to the dual bin-packing problem in literature. In the classical formulation, different (small) item lengths and corresponding availabilities are given. We aim at maximizing the number of objects with a certain minimum length that can be constructed by connecting the items on hand. Such computations are of high interest in many real world application, e.g. in industrial recycling processes, wireless communications and politico-economic questions. For this optimization problem, we give a short introduction by outlining different modelling approaches, particularly the pattern-based standard model, and mentioning their relationships. Since the SSP is known to be NP-hard a common solution approach consists in solving an LP-based relaxation and the application of (appropriate) heuristics. Practical experience and computational simulations have shown that there is only a small difference (called gap) between the optimal objective values of the relaxation and the SSP itself. In this paper, we will present some new results and improved upper bounds for the gap of the SSP that are based on the theory of residual instances of the skiving stock problem.

   6. Creating Worst-Case Instances for Upper and Lower Bounds of the Two-Dimensional Strip Packing Problem

      Torsten Buchwald, Guntram Scheithauer

      Abstract

      We present a new approach to create instances with large performance ratio, i.e., worst-case instances, of common heuristics for the two-dimensional Strip Packing Problem. The idea of this new approach is to optimise the width and the height of all items aiming to find an instance with maximal performance ratio with respect to the considered heuristic. Therefore, we model the pattern obtained by the heuristic as a solution of an ILP problem and merge this model with a Padberg-type model of the two-dimensional Strip Packing Problem. In fact, the composed model allows to compute the absolute worst-case performance ratio of the heuristic with respect to a limited number of items. We apply the new approach for the Next-Fit Decreasing-Height, the First-Fit Decreasing-Height, and the Best-Fit Decreasing-Height heuristic. Furthermore, we provide an opportunity to use this idea to create worst-case instances for lower bounds.

   7. The Maximum Scatter TSP on a Regular Grid

      Isabella Hoffmann, Sascha Kurz, Jörg Rambau

      Abstract

      In the Maximum Scatter Traveling Salesman Problem the objective is to find a tour that maximizes the shortest distance between any two consecutive nodes. This model can be applied to manufacturing processes, particularly laser melting processes. We extend an algorithm by Arkin et al. that yields optimal solutions for nodes on a line to a regular (\(m \times n\))-grid. The new algorithm \(\textsc {Weave}(m,n)\) takes linear time to compute an optimal tour in some cases. It is asymptotically optimal and a (\(\frac{\sqrt{10}}{5}\))-approximation for the (\(3\times 4\))-grid, which is the worst case.

   8. Using Contiguous 2D-Feasible 1D Cutting Patterns for the 2D Strip Packing Problem

      Isabel Friedow, Guntram Scheithauer

      Abstract

      We consider the 2D rectangular strip packing problem without rotation. A relaxation of that problem is the 1D horizontal bar relaxation, the LP relaxation of the 1D binary cutting stock problem. To represent a solution of the strip packing problem, a solution of the horizontal bar relaxation has to satisfy, among others, the vertical contiguous condition. To strengthen the bar relaxation with respect to that vertical contiguity, we investigate a cutting plane approach. Furthermore, a solution of the bar relaxation must ensure constant location of items. Because 1D cutting patterns do not provide any information about the location of the items contained, we investigate methods to provide 2D feasibility of patterns in the column generation and cutting plane process, respectively. Some computational results are also reported.

   9. Computing Partitions with Applications to Capital Budgeting Problems

      Frank Gurski, Jochen Rethmann, Eda Yilmaz

      Abstract

      We consider the following capital budgeting problem. A firm is given a set of investment opportunities \(X=\{x_1,\ldots ,x_n\}\) and a number m of portfolios. Every investment \(x_i\), \(1\le i\le n\), has a return of \(r_i\) and a price of \(p_{i}\). Further for every portfolio j there is capacity \(c_j\). The task is to choose m disjoint portfolios \(X'_1,\ldots , X'_m\) from X such that for every \(1\le j\le m\) the prices in \(X'_j\) do not exceed the capacity \(c_j\) and the total return of this selection is maximized. From a computational point of view this problem is intractable, even for \(m=1\) [8]. Since the problem is defined on inputs of various informations, in this paper we consider the fixed-parameter tractability for several parameterized versions of the problem. For a lot of small parameter values we obtain efficient solutions for the partitioning capital budgeting problem. We also consider the connection to pseudo-polynomial algorithms.

   10. Upper Bound for the Capacitated Competitive Facility Location Problem

       V. L. Beresnev, A. A. Melnikov

       Abstract

       We consider the capacitated competitive facility location problem (CCFLP) where two competing firms open facilities to maximize their profits obtained from customer service. The decision making process is organized as a Stackelberg game. Both the set of candidate sites where firms may open facilities and the set of customers are finite. The customer demands are known, and the total demand covered by each of the facilities can not exceed its capacity. We propose the upper bound for the leader’s objective function based on solving of the estimating MIP.

   11. The Onset of Congestion in Charging of Electric Vehicles for Proportionally Fair Network Management Protocol

       Ľuboš Buzna

       Abstract

       With the expected uptake of electric vehicles in the near future, we are likely to observe overloading in the local distribution networks more frequently. Such development suggests that a congestion management protocol will be a crucial component of future technological innovations in low voltage networks. An important property of a suitable network capacity management protocol is to balance network efficiency and fairness requirements. Assuming a stochastic model, we study the proportional fairness (PF) protocol managing the network capacity in charging of electric vehicles. We explore the onset of congestion by analysing the critical arrival rate, i.e. the largest possible vehicle arrival rate that can still be fully satisfied by the network. We compare the proportionally fair management protocol with the max-flow (MF) management protocol. By numerical simulations on realistic networks, we show that proportional fairness leads not only to more equitable distribution of power allocations, but it can also serve slightly larger arrival rate of vehicles. We consider simplified setup, where the power allocations are dependent on the occupation of network nodes, but they are independent of the exact number of vehicles, and to validate numerical results, we analyse the critical arrival rate on a network with two edges, where the optimal power allocations can be calculated analytically.

   12. A Comparison of Heuristic Methods for the Prize-Collecting Steiner Tree Problem and Their Application in Genomics

       Murodzhon Akhmedov, Ivo Kwee, Roberto Montemanni

       Abstract

       The prize-collecting Steiner tree (PCST) problem is a broadly studied problem in combinatorial optimization. It has been used to model several real world problems related to utility networks. More recently, researchers have started using PCSTs to study biological networks. Biological networks are typically very large in size. This can create a considerable challenge for the available PCST solving methods. Taking this fact into account, we have developed methods for the PCST that efficiently scale up to large biological network instances. Namely, we have devised a heuristic method based on the Minimum Spanning Tree and a matheuristic method composed of a heuristic clustering phase and a solution phase. In this work, we provide a performance comparison for these methods by testing them on large gene interaction networks. Experimental results are reported for the methods, including running times and objective values of the solutions.

   13. A Benders Decomposition Approach for Static Data Segment Location to Servers Connected by a Tree Backbone

       Goutam Sen, Mohan Krishnamoorthy, Vishnu Narayanan, Narayan Rangaraj

       Abstract

       We consider the problem of allocating database segments to the locations of a content distribution network (CDN). Many other decisions such as server location, query routing, user assignment and network topology are also addressed simultaneously. We consider the problem with the backbone (server network) being restricted to be a tree. Although it is an extremely hard problem to solve in its original form, prior information on the segment allocation, server location, and the tree backbone, reduces the original problem to a simple assignment problem, and therefore, indicates the suitability of a decomposition approach. We formulate the problem and develop a Benders decomposition approach. Due to the hardness of the master problem, we solve it heuristically to obtain a reasonable upper bound on the original problem in a short period of time. The success of the algorithm is particularly significant in large problems, for which CPLEX struggles to obtain even a feasible integer solution.

   14. Mathematical Optimization of a Magnetic Ruler Layout with Rotated Pole Boundaries

       Marzena Fügenschuh, Armin Fügenschuh, Marina Ludszuweit, Aleksandar Mojsic, Joanna Sokół

       Abstract

       Magnetic rulers for measuring systems are either based on incremental or absolute measuring methods. Incremental methods need to initialize a measurement cycle at a reference point. From there, the position is determined by counting increments of a periodic graduation. Absolute methods do not need reference points, since the position can be read directly from the ruler. In the state of the art approach the absolute position on the ruler is encoded using two tracks with different graduation. To use only one track for position encoding in absolute measuring a pattern of trapezoidal magnetic areas is considered instead of the common rectangular ones. We present a mixed integer programming model for an optimal placement of the trapezoidal magnetic areas to obtain the longest possible ruler under constraints conditioned by production techniques, physical limits as well as mathematical approximation of the magnetic field.

   15. A New Exact Approach to the Space-Free Double Row Layout Problem

       Anja Fischer, Frank Fischer, Philipp Hungerländer

       Abstract

       Given a set of departments, two rows with a common left origin and pairwise connectivities between the departments, the Space-Free Double-Row Facility Layout Problem (SF-DRFLP) looks for permutations of the departments in both rows such that the weighted sum of the center-to-center distances between all pairs of departments is minimized. In this paper we present a new mixed-integer linear programming formulation for the (SF-DRFLP) with given assignment of the departments to both rows that combines distance and betweenness variables. Furthermore, we analyze the combinatorial structure of optimal solutions, which allows us to prove a certain balancing condition. We then use this formulation in an enumeration scheme for solving the (SF-DRFLP). Indeed, we test all possible row assignments, where some assignments are excluded by our new combinatorial investigations. This approach allows us to solve (SF-DRFLP) instances with up to 16 departments to optimality for the first time.