Search

We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set-cover problem. For these scheduling problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed linear programming relaxations. We show how a variant of alpha-point scheduling leads to the best known approximation ratios, including a guarantee of four for an interesting special case of the so-called generalized min-sum set-cover problem. We also make explicit the connection between the greedy algorithm for min-sum set cover and the concept of Sidney decomposition for precedence-constrained single-machine scheduling and show how this leads to a 4-approximation algorithm for single-machine scheduling with so-called bipartite OR-precedence constraints. Funding: This work has been supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research. [ABSTRACT FROM AUTHOR]

In this paper a new multicommodity flow mathematical model for the Job Sequencing and Tool Switching Problem (SSP) is presented. The proposed model has an LP relaxation lower bound equal to the number of tools minus the tool machine's capacity. Computational tests were performed comparing the new model with the models of the literature. The proposed model performed better, both in execution time and in the number of instances solved to optimality. [ABSTRACT FROM AUTHOR]

We study exact recovery conditions for the linear programming relaxation of the k-median problem in the stochastic ball model (SBM). In Awasthi et al. (Relax, no need to round: integrality of clustering formulations. arXiv:1408.4045, 2015; in: Proceedings of the 2015 conference on innovations in theoretical computer science, pp 191–200, 2015), the authors give a tight result for the k-median LP in the SBM, saying that exact recovery can be achieved as long as the balls are pairwise disjoint. We give a counterexample to their result, thereby showing that the k-median LP is not tight in low dimension. Instead, we give a near optimal result showing that the k-median LP in the SBM is tight in high dimension. We also show that, if the probability measure satisfies some concentration assumptions, then the k-median LP in the SBM is tight in every dimension. Furthermore, we propose a new model of data called extended stochastic ball model (ESBM), which significantly generalizes the well-known SBM. We then show that exact recovery can still be achieved in the ESBM. [ABSTRACT FROM AUTHOR]

Republic of Korea has unique geographical characteristics similar to those of an island, resulting in an isolated power system. For this reason, securing sufficient operating reserves for the system's stability and reliability in the face of the intermittency of increasing variable renewable energy (VRE) is paramount, and this will pave the way to achieving the nation's decarbonization target and carbon neutrality. However, the current reserve-operation method in Republic of Korea does not take into account energy-system conditions, such as the intermittency of the VRE. Therefore, this paper presents an analysis of the impact of changes in reserve-operation methods on the electricity market in the future Republic of Korean power system, with the increased levels of VRE that are currently envisioned. Specifically, three reserve-operation methods, including Korea's current reserve-power-operation standards, were applied to the two power-system plans announced by the Korean government to analyze the annual generator operation and costs. The analysis results show that securing reserves proportional to the VRE would exert negative effects, such as increased power-generation costs and the curtailment of nuclear and VRE generation. These results can contribute to the estimation of operational reserves needed for high levels of VRE and to the design of new the Korean reserve market, to be introduced in 2025. [ABSTRACT FROM AUTHOR]

The pollution traveling salesman problem (PTSP) and the energy minimization traveling salesman problem (EMTSP) generalize the well-known asymmetric traveling salesman problem by including environmental issues and the goal of reducing carbon emissions. Both problems call for determining a Hamiltonian tour that, in the PTSP, minimizes a function of fuel consumption and driver cost (where the fuel consumption depends on the distance traveled, the vehicle speed, and the vehicle load), while, in the EMTSP, minimizes a function depending on the vehicle load and the traveled distances. For both PTSP and EMTSP, we propose a matheuristic algorithm that uses the solution of the linear programming relaxation of a mixed integer linear programming model for the considered problem to determine good initial feasible solutions, applies a multioperator genetic algorithm to improve these solutions, and refines the best solution found through an iterated local search procedure. In order to evaluate the performance of the proposed matheuristics, we compare them with exact and heuristic algorithms from the literature on benchmark instances of both problems. [ABSTRACT FROM AUTHOR]

We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of twins, with a novel construction of a "good" cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem. [ABSTRACT FROM AUTHOR]

We study the relation between the linear programming relaxation of two classes of models for the Steiner tree problem with hop constraints. One class is characterized by having hop‐indexed arc variables. Although such models have proved to have a very strong linear programming bound, they are not easy to use because of the huge number of variables. This has motivated some studies with models involving fewer variables that use, instead of the hop‐indexed arc variables, hop‐indexed node variables. In this article, we contextualize the linear programming relaxation of these node‐based models in terms of the linear programming relaxation of known arc‐based models. We show that the linear programming relaxation of a general node‐based model is implied by the linear programming relaxation of a straightforward arc‐based model. [ABSTRACT FROM AUTHOR]

We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous work failed to achieve a near-linear runtime in the number of edges m. We propose an algorithm with near-linear runtime Õ(m(Wmax/ε)²) for computing an e additive approximation on graphs with polylogarithmic diameter and weights of magnitude at most Wmax. In particular, this is the first algorithm whose runtime scales in the number of vertices n as Õ(n²) for the complete graph. Moreover--unconditionally on the diameter--the algorithm uses only O(n) memory beyond reading the input, making it "memory-optimal". Our approach is based on solving a linear programming (LP) relaxation using entropic regularization, which reduces the LP to a Matrix Balancing problem--à la the popular reduction of Optimal Transport to Matrix Scaling. We then round the fractional LP solution using a variant of the classical Cycle-Canceling algorithm that is sped up to near-linear runtime at the expense of being approximate, and implemented in a memory-optimal manner. The algorithm is simple to implement and is competitive with the state-of-the-art methods in practice. [ABSTRACT FROM AUTHOR]

Republic of Korea has unique geographical characteristics similar to those of an island, resulting in an isolated power system. For this reason, securing sufficient operating reserves for the system’s stability and reliability in the face of the intermittency of increasing variable renewable energy (VRE) is paramount, and this will pave the way to achieving the nation’s decarbonization target and carbon neutrality. However, the current reserve-operation method in Republic of Korea does not take into account energy-system conditions, such as the intermittency of the VRE. Therefore, this paper presents an analysis of the impact of changes in reserve-operation methods on the electricity market in the future Republic of Korean power system, with the increased levels of VRE that are currently envisioned. Specifically, three reserve-operation methods, including Korea’s current reserve-power-operation standards, were applied to the two power-system plans announced by the Korean government to analyze the annual generator operation and costs. The analysis results show that securing reserves proportional to the VRE would exert negative effects, such as increased power-generation costs and the curtailment of nuclear and VRE generation. These results can contribute to the estimation of operational reserves needed for high levels of VRE and to the design of new the Korean reserve market, to be introduced in 2025.

Nuclear Magnetic Resonance (NMR) Spectroscopy is the second most used technique (after X-ray crystallography) for structural determination of proteins. A computational challenge in this technique involves solving a discrete optimization problem that assigns the resonance frequency to each atom in the protein. This paper introduces LIAN (LInear programming Assignment for NMR), a novel linear programming formulation of the problem which yields state-of-the-art results in simulated and experimental datasets. [ABSTRACT FROM AUTHOR]

For an integer programming model with fixed data, the linear programming relaxation gap is considered one of the most important measures of model quality. There is no consensus, however, on appropriate measures of model quality that account for data variation. In particular, when the right-hand side is not known exactly, one must assess a model based on its behavior over many right-hand sides. Gap functions are the linear programming relaxation gaps parametrized by the right-hand side. Despite drawing research interest in the early days of integer programming, the properties and applications of these functions have been little studied. In this paper, we construct measures of integer programming model quality over sets of right-hand sides based on the absolute and relative gap functions. In particular, we formulate optimization problems to compute the expectation and extrema of gap functions over finite discrete sets and bounded hyperrectangles. These optimization problems are linear programs (albeit of an exponentially large size) that contain at most one special ordered-set constraint. These measures for integer programming models, along with their associated formulations, provide a framework for determining a model's quality over a range of right-hand sides. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this article, we discuss an alternative method for deriving conservative approximation models for two-stage robust optimization problems. The method mainly relies on a linearization scheme employed in bilinear programming; therefore, we will say that it gives rise to the linearized robust counterpart models. We identify a close relation between this linearized robust counterpart model and the popular affinely adjustable robust counterpart model. We also describe methods of modifying both types of models to make these approximations less conservative. These methods are heavily inspired by the use of valid linear and conic inequalities in the linearization process for bilinear models. We finally demonstrate how to employ this new scheme in location-transportation and multi-item newsvendor problems to improve the numerical efficiency and performance guarantees of robust optimization. [ABSTRACT FROM AUTHOR]

To formulate a real-world optimization problem, it is sometimes necessary to adopt a set of non-linear terms in the mathematical formulation to capture specific operational characteristics of that decision problem. However, the use of non-linear terms generally increases computational complexity of the optimization model and the computational time required to solve it. This motivates the scientific community to develop efficient transformation and linearization approaches for the optimization models that have non-linear terms. Such transformations and linearizations are expected to decrease the computational complexity of the original non-linear optimization models and, ultimately, facilitate decision making. This study provides a detailed state-of-the-art review focusing on the existing transformation and linearization techniques that have been used for solving optimization models with non-linear terms within the objective functions and/or constraint sets. The existing transformation approaches are analyzed for a wide range of scenarios (multiplication of binary variables, multiplication of binary and continuous variables, multiplication of continuous variables, maximum/minimum operators, absolute value function, floor and ceiling functions, square root function, and multiple breakpoint function). Furthermore, a detailed review of piecewise approximating functions and log-linearization via Taylor series approximation is presented. Along with a review of the existing methods, this study proposes a new technique for linearizing the square root terms by means of transformation. The outcomes of this research are anticipated to reveal some important insights to researchers and practitioners, who are closely working with non-linear optimization models, and assist with effective decision making.

We study the setting of channel coding over a family of channels whose state is controlled by an adversarial jammer by viewing it as a zero-sum game between a finite blocklength encoder-decoder team, and the jammer. The encoder-decoder team choose stochastic encoding and decoding strategies to minimize the average probability of error in transmission, while the jammer chooses a distribution on the state-space to maximize this probability. The min-max value of the game is equivalent to channel coding for a compound channel - we call this the Shannon solution of the problem. The max-min value corresponds to finding a mixed channel with the largest value of the minimum achievable probability of error. When the min-max and max-min values are equal, the problem is said to admit a saddle-point or von Neumann solution. While a Shannon solution always exists, the communicating team’s problem is nonconvex for finite blocklengths, whereby a von Neumann solution may not exist. Despite this, we show that the min-max and max-min values become equal asymptotically in the large blocklength limit, for all but finitely many rates. We explicitly characterize this limiting value as a function of the rate and obtain tight finite blocklength bounds on the min-max and max-min value. As a corollary we get an explicit expression for the $\epsilon $ -capacity of a compound channel under stochastic codes - the first such result, to the best of our knowledge. Our results demonstrate a deeper relation between the compound channel and mixed channel than was previously known. They also show that the conventional information-theoretic viewpoint, articulated via the Shannon solution, coincides asymptotically with the game-theoretic one articulated via the von Neumann solution. Key to our results is the derivation of new finite blocklength upper bounds on the min-max value of the game via a novel achievability scheme, and lower bounds on the max-min value obtained via the linear programming relaxation based approach we introduced in. [ABSTRACT FROM AUTHOR]

The Steiner tree problem (STP) is a classical NP‐hard combinatorial optimization problem with applications in computational biology and network wiring. The objective of this problem is to find a minimum cost subgraph of a given undirected graph G with edge costs, that spans a subset of vertices called terminals. We present currently used linear programming formulations of the problem based on two different approaches—the bidirected cut relaxation (BCR) and the hypergraphic formulations (HYP), the former offering better computational performance, and the latter better bounds on the integrality gap. As our contribution, we propose a new hierarchy of path‐based extended formulations for STP. We show that this hierarchy provides better integrality gaps on graph instances used to define the worst‐case lower bounds on the integrality gap for both BCR and HYP. We prove that each consecutive level of our hierarchy is at least as strong as the previous one. Additionally, we also present numerical results showing that several difficult STP instances can be solved to integer optimality by using this hierarchy. Our approach can be adapted to variants of STP or applied to hypergraphic formulations for further potential improvement on the integrality gap bounds, in exchange for additional computational effort. [ABSTRACT FROM AUTHOR]

In this study, we consider the multi resource agent bottleneck generalised assignment problem. Our aim is to minimise the maximum load over all agents. We take our motivation from an assignment problem faced in heating, ventilating and air conditioning sector. We study the linear programming (LP) relaxation of the problem. We use the optimal LP relaxation solutions in our branch and bound algorithm while defining bounding and branching schemes. We find that our branch and bound algorithm returns optimal solutions to the problems with up to 60 jobs when the number of agents is 5, and up to 30 jobs when the number of agents is 10, in less than 20 minutes. To find approximate solutions, we define a tabu search algorithm and α approximation algorithm. Our computational results have revealed that both algorithms can find high quality solutions to large sized instances very quickly. To the best of our knowledge our study is the first reported attempt to solve the problem. We hope our study fills an important gap in the literature. [ABSTRACT FROM AUTHOR]