Search

The relaxation complexity $${{\,\mathrm{rc}\,}}(X)$$ rc ( X ) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is a useful tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on $${{\,\mathrm{rc}\,}}_\mathbb {Q}(X)$$ rc Q ( X ) , a variant of $${{\,\mathrm{rc}\,}}(X)$$ rc ( X ) in which the polyhedra P are required to be rational, and we show that $${{\,\mathrm{rc}\,}}(X)$$ rc ( X ) can be computed in polynomial time if X is 2-dimensional. Further, we investigate computable lower bounds on $${{\,\mathrm{rc}\,}}(X)$$ rc ( X ) with the particular focus on the existence of a finite set $$Y \subseteq \mathbb {Z}^d$$ Y ⊆ Z d such that separating X and $$Y \setminus X$$ Y \ X allows us to deduce $${{\,\mathrm{rc}\,}}(X) \ge k$$ rc ( X ) ≥ k . In particular, we show for some choices of X that no such finite set Y exists to certify the value of $${{\,\mathrm{rc}\,}}(X)$$ rc ( X ) , providing a negative answer to a question by Weltge (2015). We also obtain an explicit formula for $${{\,\mathrm{rc}\,}}(X)$$ rc ( X ) for specific classes of sets X and present the first practically applicable approach to compute $${{\,\mathrm{rc}\,}}(X)$$ rc ( X ) for sets X that admit a finite certificate.

In the summer of 2020, Music Building Eindhoven (MBE) had to deal with the economic consequences of the COVID-19 pandemic for theater halls because governmental regulations were having a severe impact on the occupancy. In particular, MBE faced the challenge of determining how to maximize the number of guests in a theater hall while respecting social distancing rules. We have developed and implemented an optimization model based on trapezoid packings to address this challenge. The model showed that up to 40% of the normal capacity can be realized for a single show setting and up to 70% in cases where artists opt for two consecutive performances per evening without reusing seats. The solution was adopted by MBE with significant monetary and managerial benefits. History: This paper was refereed. This article has been selected for inclusion in the Special Issue on Analytics Remedies to COVID-19. Funding: The research of F. Spieksma is supported by Dutch Research Council (NWO) Gravitation Project NETWORKS [Grant 024.002.003].

We introduce the concept of codeterminantal graphs, which generalize the concepts of cospectral and coinvariant graphs. To do this, we investigate the relationship of the spectrum and the Smith normal form (SNF) with the determinantal ideals. We establish a necessary and sufficient condition for graphs to be codeterminantal on R[x], and we present some computational results on codeterminantal graphs up to 9 vertices. Finally, we show that complete graphs and star graphs are determined by the SNF of its distance Laplacian matrix.

Set systems can be visualized in various ways. An important distinction between techniques is whether the elements have a spatial location that is to be used for the visualization; for example, the elements are cities on a map. Strictly adhering to such location may severely limit the visualization and force overlay, intersections and other forms of clutter. On the other hand, completely ignoring the spatial dimension omits information and may hide spatial patterns in the data. We study layouts for set systems (or hypergraphs) in which spatial locations are displaced onto concentric circles or a grid, to obtain schematic set visualizations. We investigate the tractability of the underlying algorithmic problems adopting different optimization criteria (e.g. crossings or bends) for the layout structure, also known as the support of the hypergraph. Furthermore, we describe a simulated-annealing approach to heuristically optimize a combination of such criteria. Using this method in computational experiments, we explore the trade-offs and dependencies between criteria for computing high-quality schematic set visualizations.

Weight-equitable partitions of graphs, which are a natural extension of the well-known equitable partitions, have been shown to be a powerful tool to weaken the regularity assumption in several well-known eigenvalue bounds. In this work we aim to further our algebraic and computational understanding of weight-equitable partitions. We do so by showing several spectral properties and algebraic characterizations, and by providing a method to find coarse weight-equitable partitions.

In this work, we obtain the group inverse of the combinatorial Laplacian matrix of distance-biregular graphs. This expression can be obtained trough the so-called equilibrium measures for sets obtained by deleting a vertex. Moreover, we show that the two equilibrium arrays characterizing distance-biregular graphs can be expressed in terms of the mentioned equilibrium measures. As a consequence of the minimum principle, we provide a characterization of when the group inverse of the combinatorial Laplacian matrix of a distance-biregular graph is an M-matrix.

Dynamic vehicle routing problems (DVRPs) arise in several applications such as technician routing, meal delivery, and parcel shipping. We consider the DVRP with stochastic customer requests (DVRPSR), in which vehicles must be routed dynamically with the goal of maximizing the number of served requests. We model the DVRPSR as a multi-stage optimization problem, where the first-stage decision defines route plans for serving scheduled requests. Our main contributions are knapsack-based linear models to approximate accurately the expected reward-to-go, measured as the number of accepted requests, at any state of the stochastic system. These approximations are based on representing each vehicle as a knapsack with a capacity given by the remaining service time available along the vehicle's route. We combine these approximations with optimal acceptance and assignment decision rules and derive efficient and high-performing online scheduling policies. We further leverage good predictions of the expected reward-to-go to design initial route plans that facilitate serving dynamic requests. Computational experiments on very large instances based on a real street network demonstrate the effectiveness of the proposed methods in prescribing high-quality offline route plans and online scheduling decisions., Comment: 44 pages

Gerhard Woeginger has passed away. His colleagues Jan Karel Lenstra, Franz Rendl, Frits Spieksma and Marc Uetz commemorate a great scientist and dear friend.

We introduce the problem of selecting patient-donor pairs in a kidney exchange program to undergo a crossmatch test, and we model this selection problem as a two-stage stochastic integer programming problem. The optimal solutions of this new formulation yield a larger expected number of realized transplants than previous approaches based on internal recourse or subset recourse. We settle the computational complexity of the selection problem by showing that it remains NP-hard even for maximum cycle length equal to two. Furthermore, we investigate to what extent different algorithmic approaches, including one based on Benders decomposition, are able to solve instances of the model. We empirically investigate the computational efficiency of this approach by solving randomly generated instances and study the corresponding running times as a function of maximum cycle length, and of the presence of nondirected donors. Summary of Contribution: This paper deals with an important and very complex issue linked to the optimization of transplant matchings in kidney exchange programs, namely, the inherent uncertainty in the assessment of compatibility between donors and recipients of transplants. Although this issue has previously received some attention in the optimization literature, most attempts to date have focused on applying recourse to solutions selected within restricted spaces. The present paper explicitly formulates the maximization of the expected number of transplants as a two-stage stochastic integer programming problem. The formulation turns out to be computationally difficulty, both from a theoretical and from a numerical perspective. Different algorithmic approaches are proposed and tested experimentally for its solution. The quality of the kidney exchanges produced by these algorithms compares favorably with that of earlier models.

Motivated by evidence that parliament seatings are relevant for decision making, we consider the problem to assign seats in a parliament to members of parliament. We prove that the resulting seating assignment problem is strongly NP-hard in several restricted settings. We present a Mixed Integer Programming formulation of the problem, we describe two families of valid inequalities and we discuss symmetry-breaking constraints. Further, we design a heuristic. Finally, we compare the outcomes of the Mixed Integer Programming formulation with the outcomes of the heuristic in a computational study.

We provide a combinatorial and self-contained proof that for all graphs $G$ embedded on a surface $S$, the Colin de Verdi\`ere parameter $\mu(G)$ is upper bounded by $7-2\chi(S)$.

We describe an implementation of a computer search for the "small" excluded minors for a class of matroids representable over a partial field. Using these techniques, we enumerate the excluded minors on at most 15 elements for both the class of dyadic matroids, and the class of 2-regular matroids. We conjecture that there are no other excluded minors for the class of 2-regular matroids; whereas, on the other hand, we show that there is a 16-element excluded minor for the class of dyadic matroids., 20 pages, 3 figures

Given a complete graph with an even number of vertices, and with each edge colored with one of two colors (say red or blue), an equitable Hamiltonian cycle is a Hamiltonian cycle that can be decomposed into two perfect matchings such that both perfect matchings have the same number of red edges. We show that, for any coloring of the edges, in any complete graph on at least 6 vertices, an equitable Hamiltonian cycle exists.

We investigate a new tournament format that consists of a series of individual knockout tournaments; we call this new format a Serial Knockout Competition (SKC). This format has recently been adopted by the Professional Darts Corporation. Depending on the seedings of the players used for each of the knockout tournaments, players can meet in the various rounds (eg first round, second round, ..., semi-final, final) of the knockout tournaments. Following a fairness principle of treating all players equal, we identify an attractive property of an SKC: each pair of players should potentially meet equally often in each of the rounds of the SKC. If the seedings are such that this property is indeed present, we call the resulting SKC stable. In this note we formalize this notion, and we address the question: do there exist seedings for each of the knockout tournaments such that the resulting SKC is stable? We show, using a connection to the Fano plane, that the answer is yes for 8 players. We show how to generalize this to any number of players that is a power of 2, and we provide stable schedules for competitions on 16 and 32 players

International audience; Given a graph, we wish to find a maximum number of vertex-disjoint paths of length 2. We propose a series of local improvement algorithms for this problem, and present a linear-programming based method for analyzing their performance.

We consider a time-indexed formulation for the unrelated parallel machine scheduling problem. We show that all polyhedral knowledge known from the single machine problem (in particular, valid inequalities) is applicable to this formulation. We present new facet-inducing valid inequalities and a preprocessing technique involving fixing variables based on reduced costs. We combine both techniques in a basic cutting-plane algorithm and test the performance of the resulting algorithm by running it on randomly generated instances.

International audience; We consider the so-called periodically aggregated resource-constrained project scheduling problem. This problem, introduced by Morin et al. 2017, is a variant of the well-known resource-constrained project scheduling problem that allows for a more flexible usage of the resource constraints. While the start and completion times of the activities can be arbitrary moments in time, the limitations on the resource usage are considered on average over aggregated periods of parameterized length. This paper presents new theoretical and experimental results for this problem. First, we settle the complexity status of the problem by proving NP-hardness of a number of special cases of the problem. Second, we propose a new mixed-integer programming formulation of the problem by disaggregating the precedence constraints over the periods. A theoretical comparison shows that the new formulation dominates the previously proposed one in terms of relaxation strength. Finally, we carry out computational experiments on instances from the literature to compare the merits of the different formulations.

Motivated by the celebrated Beck-Fiala conjecture, we consider the random setting where there are n elements and m sets and each element lies in t randomly chosen sets. In this setting, Ezra and Lovett showed an O((tlogt)1/2) discrepancy bound in the regime when n ≤ m and an O(1) bound when n≫mt. In this paper, we give a tight O(√t) bound for the entire range of n and m, under a mild assumption that t=Ω(log log m)2. The result is based on two steps. First, applying the partial coloring method to the case when n=mlogO(1)m and using the properties of the random set system we show that the overall discrepancy incurred is at most O(√t). Second, we reduce the general case to that of n≤mlogO(1)m using LP duality and a careful counting argument.

A well known upper bound for the independence number $\alpha(G)$ of a graph $G$, due to Cvetkovi ́c, is that \begin{equation*}\alpha(G) \le n^0 + \min\{n^+ , n^-\}\end{equation*}where $(n^+, n^0, n^-)$ is the inertia of $G$. We prove that this bound is also an upper bound for the quantum independence number $\alpha_q$(G), where $\alpha_q(G) \ge \alpha(G)$ and for some graphs $\alpha_q(G) \gg \alpha(G)$. We identify numerous graphs for which $\alpha(G) = \alpha_q(G)$, thus increasing the number of graphs for which $\alpha_q$ is known. We also demonstrate that there are graphs for which the above bound is not exact with any Hermitian weight matrix, for $\alpha(G)$ and $\alpha_q(G)$. Finally, we show this result in the more general context of spectral bounds for the quantum $k$-independence number, where the $k$-independence number is the maximum size of a set of vertices at pairwise distance greater than $k$.

For k≥1, the k-independence number αk of a graph is the maximum number of vertices that are mutually at distance greater than k. The well-known inertia and ratio bounds for the (1-)independence number α(=α1) of a graph, due to Cvetković and Hoffman, respectively, were generalized recently for every value of k. We show that, for graphs with enough regularity, the polynomials involved in such generalizations are closely related and give exact values for αk, showing a new relationship between the inertia and ratio type bounds. Additionally, we investigate the existence and properties of the extremal case of sets of vertices that are mutually at maximum distance for walk-regular graphs. Finally, we obtain new sharp inertia and ratio type bounds for partially walk-regular graphs by using the predistance polynomials. The research of Aida Abiad is partially supported by the FWO, Belgium grant 1285921N. The research of Cristina Dalfó and Miquel Àngel Fiol has been partially supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00.

Several image rotation operators are introduced as novel rotation variants of John Conway’s Game of Life. The main idea of the Game of Life is to simulate real-life processes such as birth, survival and death. The discrete model operates on a two-dimensional array of black and white square cells. In this paper, we study the development of patterns in image rotation using different rotation methods. Moreover, the quality of the rotation and the applicability of image rotation to the Game of Life are investigated.

Several researchers have recently explored various graph parameters that can or cannot be characterized by the spectrum of a matrix associated with a graph. In this paper, we show that several NP-hard zero forcing numbers are not characterized by the spectra of several types of associated matrices with a graph. In particular, we consider standard zero forcing, positive semidefinite zero forcing, and skew zero forcing and provide constructions of infinite families of pairs of cospectral graphs, which have different values for these numbers. We explore several methods for obtaining these cospectral graphs including using graph products, graph joins, and graph switching. Among these, we provide a construction involving regular adjacency cospectral graphs; the regularity of this construction also implies cospectrality with respect to several other matrices including the Laplacian, signless Laplacian, and normalized Laplacian. We also provide a construction where pairs of cospectral graphs can have an arbitrarily large difference between their zero forcing numbers.

The independence number, coloring number and related parameters are investigated in the setting of oriented hypergraphs using the spectrum of the normalized Laplace operator. For the independence number, both an inertia--like bound and a ratio--like bound are shown. A Sandwich Theorem involving the clique number, the vector chromatic number and the coloring number is proved, as well as a lower bound for the vector chromatic number in terms of the smallest and the largest eigenvalue of the normalized Laplacian. In addition, spectral partition numbers are studied in relation to the coloring number., Comment: Linear Algebra and Its Applications, To appear

A shootout is a popular mechanism to identify a winner of a match between two teams. It consists of rounds in which each team gets, sequentially, an opportunity to score a point. It has been shown empirically that shooting first or shooting second in a round has an impact on the scoring probability. This raises a fairness question: is it possible to specify a sequence such that identical teams have equal chance of winning? We show that, for a sudden death, no repetitive sequence can be fair. In addition, we show that the so-called Prohuet–Thue–Morse sequence is not fair. There is, however, an algorithm that outputs a fair sequence whenever one exists. We also analyze the popular best-of-$k$ shootouts and show that no fair sequence exists in this situation. In addition, we find explicit expressions for the degree of unfairness in a best-of-$k$ shootout; this allows sports administrators to asses the effect of the length of the shootout on the degree of unfairness.

A Neumaier graph is a non-complete edge-regular graph containing a regular clique. A Neumaier graph that is not strongly regular is called a strictly Neumaier graph. In this work we present a new construction of strictly Neumaier graphs, and using Jacobi sums, we show that our construction produces infinitely many instances. Moreover, we prove some necessary conditions for the existence of (strictly) Neumaier graphs that allow us to show that several parameter sets are not admissible.

Testing rationality of decision-making and choice by evaluating the mathematical property of transitivity has a long tradition in biology, economics, psychology, and zoology. This paradigm is fraught with conceptual, mathematical, and statistical pitfalls. In this overview, we tackle five major obstacles. One challenge lies in spelling out what transitivity of latent preferences really says and what it actually implies about observable choice behavior. Most notably, this step is fraught with aggregation artifacts, in that aggregated behavior can be profoundly misleading about individual behavior. Another hurdle comes from hard mathematical problems associated with characterizing the properties of heterogeneous transitive populations. A third challenge is the prevalence of straw man hypotheses in this area of research. The fourth difficulty is associated with adopting appropriate statistical inference tools that correctly accommodate the idiosyncratic mathematical properties of order-constrained statistical hypotheses. The fifth hurdle arises with the role of scientific parsimony in rationality research. We walk readers through key concepts, mathematical models, and statistical techniques for testing rationality. Throughout, we provide examples using the methods and data of two prominent published papers on animal choice behavior as our case studies. We explain how these papers tackled the five hurdles to varying degrees of success.

Dirac’s theorem (1952) is a classical result of graph theory, stating that an n-vertex graph (n≥3n≥3) is Hamiltonian if every vertex has degree at least n/2. Both the value n/2 and the requirement for every vertex to have high degree are necessary for the theorem to hold. In this work we give efficient algorithms for determining Hamiltonicity when either of the two conditions are relaxed. More precisely, we show that the Hamiltonian Cycle problem can be solved in time ck⋅nO(1)ck⋅nO(1), for a fixed constant c, if at least n−kn−k vertices have degree at least n/2, or if all vertices have degree at least n/2−kn/2−k. The running time is, in both cases, asymptotically optimal, under the exponential-time hypothesis (ETH). The results extend the range of tractability of the Hamiltonian Cycle problem, showing that it is fixed-parameter tractable when parameterized below a natural bound. In addition, for the first parameterization we show that a kernel with O(k) vertices can be found in polynomial time.

Motivated by the application of scheduling a sequence of locks along a waterway, we consider a scheduling problem where multiple parallel batching machines are arranged in a sequence and process jobs that travel along this sequence. We investigate the computational complexity of this problem. More specifically, we show that minimizing the sum of completion times is strongly NP-hard, even for two identical machines and when all jobs travel in the same direction. A second NP-hardness result is obtained for a different special case where jobs all travel at an identical speed. Additionally, we introduce a class of so-called synchronized schedules and investigate special cases where the existence of an optimum solution which is synchronized can be guaranteed. Finally, we reinforce the claim that bidirectional travel contributes fundamentally to the computational complexity of this problem by describing a polynomial time procedure for a setting with identical machines and where all jobs travel in the same direction at equal speed.

We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((t log n)1/2), matching the best known nonconstructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t1/2 log n) bound. The result also extends to the more general Komlós setting and gives an algorithmic O(log1/2n) bound.

The sport teams grouping problem (STGP) concerns the assignment of sport teams to round-robin tournaments. The objective is to minimize the total travel distance of the participating teams while simultaneously respecting fairness constraints. The STGP is an NP-Hard combinatorial optimization problem highly relevant in practice. This paper investigates the performance of some complimentary optimization approaches to the STGP. Three integer programming formulations are presented and thoroughly analyzed: two compact formulations and another with an exponential number of variables, for which a branch-and-price algorithm is proposed. Additionally, a meta-heuristic method is applied to quickly generate feasible high-quality solutions for a set of real-world instances. By combining the different approaches’ results, solutions within 1.7% of the optimum values were produced for all feasible instances. Additionally, to support further research, the considered STGP instances and corresponding solutions files were shared online.

We investigate a problem inspired by the practical setting of scheduling a lock with parallel chambers. We show how this problem relates to known interval scheduling problems, as well as to a particular graph coloring problem on multiple unit interval graphs. We explore the relationships between these problems and discuss the complexity of different problem variants. In particular, for a lock consisting of two chambers we are able to characterize the feasible instances and use this result to obtain efficient algorithms. We also provide an efficient algorithm for the special case with identical lock chambers. Furthermore, we describe a dynamic programming approach for the more general case with arbitrary chambers, and prove that the problem is strongly NP-complete when the number of chambers is part of the input.

The complex multi-criteria optimisation problems arising in Kidney Exchange Programmes have received considerable attention both in practice and in the scientific literature. Whereas theoretical advancements are well reviewed and synthesised, this is not the case for practice. We present a synthesis of models and methods applied in present European Kidney Exchange Programmes, which is based on detailed descriptions we created for this purpose. Most descriptions address national programmes, yet we also present findings on emerging cross-national programmes. The synthesis provides a systematic and detailed description of the models and methods the programmes use, revealing important commonalities as well as considerable variation among them. Rather than distilling a single best practice from these results, we find that the variation in models and methods arises because of variation in country characteristics, policies, and ethics. The synthesised state of the art may benefit future national and cross-national initiatives and direct future theoretical contributions within and across the boundaries of the Operations Research discipline.

Kidney Exchange Programs (KEP) are valuable tools to increase the options of living donor kidney transplantation for patients with end-stage kidney disease with an immunologically incompatible live donor. Maximising the benefits of a KEP requires an information system to manage data and to optimise transplants. The data input specifications of the systems that relate to key information on blood group and Human Leukocyte Antigen (HLA) types and HLA antibodies are crucial in order to maximise the number of identified matched pairs while minimising the risk of match failures due to unanticipated positive crossmatches. Based on a survey of eight national and one transnational kidney exchange program, we discuss data requirements for running a KEP. We note large variations in the data recorded by different KEPs, reflecting varying medical practices. Furthermore, we describe how the information system supports decision making throughout these kidney exchange programs. ispartof: HEALTH INFORMATICS JOURNAL vol:27 issue:2 ispartof: location:England status: published

We consider a spectrum of geometric optimization problems motivated by contexts such as satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs, we are given a graph G that is embedded in Euclidean space. The edges of G need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex incurs some cost in terms of energy or rotation time that is proportional to the corresponding rotation angle. Our goal is to compute schedules that minimize the following objective functions: (i) in Minimum Makespan Scan Cover (MSC-MS), this is the time until all edges are scanned; (ii) in Minimum Total Energy Scan Cover (MSC-TE), the sum of all rotation angles; (iii) in Minimum Bottleneck Energy Scan Cover (MSC-BE), the maximum total rotation angle at one vertex. Previous theoretical work on MSC-MS revealed a close connection to graph coloring and the cut cover problem, leading to hardness and approximability results. In this paper, we present polynomial-time algorithms for 1D instances of MSC-TE and MSC-BE, but NP-hardness proofs for bipartite 2D instances. For bipartite graphs in 2D, we also give 2-approximation algorithms for both MSC-TE and MSC-BE. Most importantly, we provide a comprehensive study of practical methods for all three problems. We compare three different mixed-integer programming and two constraint programming approaches, and show how to compute provably optimal solutions for geometric instances with up to 300 edges. Additionally, we compare the performance of different meta-heuristics for even larger instances., LIPIcs, Vol. 190, 19th International Symposium on Experimental Algorithms (SEA 2021), pages 4:1-4:16

The development of practically well-behaved integer programming formulations is an important aspect of solving linear optimization problems over a set X ⊆ { 0 , 1 } n . In practice, one is often interested in strong integer formulations with additional properties, e.g., bounded coefficients to avoid numerical instabilities. This article presents a lower bound on the size of coefficients in any strong integer formulation of X and demonstrates that certain integer sets X require (exponentially) large coefficients in any strong integer formulation. We also show that strong integer formulations of X ⊆ { 0 , 1 } n may require exponentially many inequalities while linearly many inequalities may suffice in weak formulations.

Kitamura and Stoye (2018) recently proposed a nonparametric statistical test for random utility models of consumer behavior. The test is formulated in terms of linear inequality constraints and a quadratic objective function. While the nonparametric test is conceptually appealing, its practical implementation is computationally challenging. In this paper, we develop a column generation approach to operationalize the test. These novel computational tools generate considerable computational gains in practice, which substantially increases the empirical usefulness of Kitamura and Stoye's statistical test., SCOPUS: ar.j, info:eu-repo/semantics/published

In this paper, a few models for optical router nodes are considered. The stations (ports) of such a node try to transmit packets. Successful transmission of a packet of type j at station i gives a profit γ i j , but there is also a positive probability that such a packet is dropped, causing a penalty θ i j . Consider one fixed cycle (frame), in which each station is assigned some visit time. The goal is to choose the visit times in such a way that the revenue is maximized. In our first model there is only one wavelength, and we take the finiteness of buffers into account. The revenue maximization problem is shown to be separable concave, thus allowing application of a very efficient algorithm. In our second model we allow multiple wavelengths. We aim to maximize the revenue by optimally assigning stations to wavelengths and, for each wavelength, by optimally choosing the visit times of the allocated stations within the cycle. This gives rise to a mixed integer linear programming problem (MILP) which is NP-hard. To solve this problem fast and efficiently we provide a three-step heuristic. It consists of (i) solving a separable concave optimization problem, then (ii) allocating the stations to wavelengths using a simple bin packing algorithm, and finally (iii) solving another set of separable concave optimization problems. We present numerical results to investigate the effectiveness of the heuristic and the advantages of having multiple wavelengths. Finally, some model variants are briefly discussed.

This paper explores the use of Column Generation (CG) techniques in constructing univariate binary decision trees for classification tasks. We propose a novel Integer Linear Programming (ILP) formulation, based on root-to-leaf paths in decision trees. The model is solved via a Column Generation based heuristic. To speed up the heuristic, we use a restricted instance data by considering a subset of decision splits, sampled from the solutions of the well-known CART algorithm. Extensive numerical experiments show that our approach is competitive with the state-of-the-art ILP-based algorithms. In particular, the proposed approach is capable of handling big data sets with tens of thousands of data rows. Moreover, for large data sets, it finds solutions competitive to CART.

We consider the simultaneous scheduling of multiple sport leagues, with interdependencies arising from teams in different leagues belonging to the same club. Teams from the same club share the same venue with limited capacity. We minimize the total capacity violation in polynomial time when each league has the same, even number of teams. We introduce two generalizations: one where teams from a club have to play according to the same pattern, and one where club capacities differ throughout the season.

© 2022 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ The k-thpower of a graph G=(V,E), G^k, is the graph whose vertex set is V and in which two distinct vertices are adjacent if and only if their distance in G is at most k. This article proves various eigenvalue bounds for the independence number and chromatic number of G^k which purely depend on the spectrum of G, together with a method to optimize them. Our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well. The research of A. Abiad is partially supported by the FWO grant 1285921N. A. Abiad and M.A. Fiol gratefully acknowledge the support from DIAMANT. This research of M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. B. Nogueira acknowledges grant PRPQ/ADRC from UFMG. The authors would also like to thank Anurag Bishnoi for noticing a tight family for our bound (19).

We study a natural variant of scheduling that we call partial scheduling: In this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f(k)n^𝒪(1) or n^𝒪(f(k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in 𝖯, NP-complete and fixed-parameter tractable by k, or 𝖶[1]-hard parameterized by k. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an 𝒪(8^k k(|V|+|E|)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G = (V,E) is the graph with precedence constraints., LIPIcs, Vol. 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), pages 25:1-25:17

For many algorithmic problems on graphs of treewidth t , a standard dynamic programming approach gives an algorithm with time and space complexity 2O(t)⋅nO(1) . It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form 2O(d)⋅nO(1) , where d is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity 2O(tlogt)⋅nO(1) on graphs of treewidth t , but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. (FOCS’11) introduced the Cut&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity 2O(t)⋅nO(1) . Recently, Hegerfeld and Kratsch (STACS’20) showed that, for some of those problems, the Cut&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time 2O(d)⋅nO(1) and polynomial space usage. However, a number of important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper we clarify the situation by showing that Hamiltonian Cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit 5d⋅nO(1) -time and polynomial space algorithms on graphs of treedepth d . The algorithms are randomized Monte Carlo with only false negatives.

Motivated by applications in ride-sharing and truck-delivery, we study the problem of matching a number of requests and assigning them to cars. A number of cars are given, each of which consists of a location and a speed, and a number of requests are given, each of which consists of a pick-up location and a drop-off location. Serving a request means that a car must first visit the pick-up location of the request and then visit the drop-off location. Each car can only serve at most c requests. Each assignment can yield multiple different serving routes and corresponding serving times, and our goal was to serve the maximum number of requests with the minimum travel time (called CSsum) and to serve the maximum number of requests with the minimum total latency (called CSlat). In addition, we studied the special case where the pick-up and drop-off locations of a request coincide. Both problems CSsum and CSlat are APX-hard when c ≥ 2. We propose an algorithm, called the transportation algorithm (TA), which is a (2c − 1)-approximation (resp. c-approximation) algorithm for CSsum (resp. CSlat); these bounds are shown to be tight. We also considered the special case where each car serves exactly two requests, i.e., c = 2. In addition to the TA, we investigated another algorithm, called the match-and-assign algorithm (MA). Moreover, we call the algorithm that outputs the best of the two solutions found by the TA and MA the CA. We show that the CA is a two-approximation (resp. 5/3) for CSsum (resp. CSlat), and these ratios are better than the ratios of the individual algorithms, the TA and MA.

This paper studies the mid-term production planning of high-tech low-volume industries. Mid-term production planning (6 to 24 months) allocates the capacity of production resources to different products over time and coordinates the associated inventories and material inputs so that known or predicted demand is met in the best possible manner. High-tech low-volume industries can be characterized by the limited production quantities and the complexity of the supply chain. To model this, we introduce a mixed integer linear programming model that can handle general supply chains and production processes that require multiple resources. Furthermore, it supports semi-flexible capacity constraints and multiple production modes. Because of the integer production variables, size of realistic instances and complexity of the model, this model is not easily solved by a commercial solver. Applying Benders’ decomposition results in alternative capacity constraints and a second formulation of the problem. Where the first formulation assigns resources explicitly to release orders, the second formulation assures that the available capacity in any subset of the planning horizon is sufficient. Since the number of alternative capacity constraints is exponential, we first solve the second formulation without capacity constraints. Each time an incumbent is found during the branch and bound process a maximum flow problem is used to find missing constraints. If a missing constraint is found it is added and the branch and bound process is restarted. Results from a realistic test case show that utilizing this algorithm to solve the second formulation is significantly faster than solving the first formulation.

© 2018, Springer-Verlag GmbH Germany, part of Springer Nature and EURO - The Association of European Operational Research Societies. An instance of a balanced optimization problem with vector costs consists of a ground set X, a cost-vector for every element of X, and a system of feasible subsets over X. The goal is to find a feasible subset that minimizes the so-called imbalance of values in every coordinate of the underlying vector costs. Balanced optimization problems with vector costs are equivalent to the robust optimization version of balanced optimization problems under the min-max criterion. We regard these problems as a family of optimization problems; one particular member of this family is the known balanced assignment problem. We investigate the complexity and approximability of robust balanced optimization problems in a fairly general setting. We identify a large family of problems that admit a 2-approximation in polynomial time, and we show that for many problems in this family this approximation factor 2 is best-possible (unless P = NP). We pay special attention to the balanced assignment problem with vector costs and show that this problem is NP-hard even in the highly restricted case of sum costs. We conclude by performing computational experiments for this problem. ispartof: EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION vol:6 issue:3 pages:239-266 status: published

In so-called random preference models of probabilistic choice, a decision maker chooses according to an unspecified probability distribution over preference states. The most prominent case arises when preference states are linear orders or weak orders of the choice alternatives. The literature has documented that actually evaluating whether decision makers’ observed choices are consistent with such a probabilistic model of choice poses computational difficulties. This severely limits the possible scale of empirical work in behavioral economics and related disciplines. We propose a family of column generation based algorithms for performing such tests. We evaluate our algorithms on various sets of instances. We observe substantial improvements in computation time and conclude that we can efficiently test substantially larger data sets than previously possible.

We study the Double Coverage (DC) algorithm for the k-server problem in tree metrics in the (h, k)-setting, i.e., when DC with k servers is compared against an offline optimum algorithm with h ≤ k servers. It is well-known that in such metric spaces DC is k-competitive (and thus optimal) for h = k. We prove that even if k > h the competitive ratio of DC does not improve; in fact, it increases slightly as k grows, tending to h + 1. Specifically, we give matching upper and lower bounds of k(h+1)k+1 on the competitive ratio of DC on any tree metric.

We present enumeration results on the number of connected graphs up to 10 vertices for which there is at least one other graph with the same spectrum (a cospectral mate), or at least one other graph with the same Smith normal form (coinvariant mate) with respect to several matrices associated to a graph. The present data give some indication that possibly the Smith normal form of the distance Laplacian and the signless distance Laplacian matrices could be a finer invariant to distinguish graphs in cases where other algebraic invariants, such as those derived from the spectrum, fail. Finally, we show a new graph characterization using the Smith normal form of the signless distance Laplacian matrix.