We consider a bilevel integer programming model that extends the classic 0–1 knapsack problem in a very natural way. The model describes a Stackelberg game where the leader’s decision interdicts a subset of the knapsack items for the follower. As this interdiction of items substantially increases the difficulty of the problem, it prevents the application of the classical methods for bilevel programming and of the specialized approaches that are tailored to other bilevel knapsack variants. Motivated by the simple description of the model, by its complexity, by its economic applications, and by the lack of algorithms to solve it, we design a novel viable way for computing optimal solutions. Finally, we present extensive computational results that show the effectiveness of the new algorithm on instances from the literature and on randomly generated instances.

We reconsider the successful approaches that we adopted in the past to solve Train Timetabling, Train Platforming, Train‐Unit Assignment, and Crew Assignment problems arising in railway planning. We try to unify these approaches under a common framework, noting that they are all formulated as variants of a fairly general version of integer multicommodity flow, and discussing the solution methods and modelling issues that we found most relevant. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(1), 1–10 2015

We study a natural generalization of the knapsack problem, in which each item exists only for a given time interval. One has to select a subset of the items (as in the classical case), guaranteeing that for each time instant, the set of existing selected items has total weight no larger than the knapsack capacity. We focus on the exact solution of the problem, noting that prior to our work, the best method was the straightforward application of a general-purpose solver to the natural integer linear programming formulation. Our results indicate that much better results can be obtained by using the same general-purpose solver to tackle a nonstandard Dantzig-Wolfe reformulation in which subproblems are associated with groups of constraints. This is also interesting because the more natural Dantzig-Wolfe reformulation of single constraints performs extremely poorly in practice.

In this paper we study a railway optimization problem known as the Train Unit Assignment Problem. A train unit consists of a self-contained train with an engine and a set of wagons with passenger seats. Given a set of timetabled train trips, each with a required number of passenger seats, and a set of train units, each with a given number of available seats, the problem calls for the best assignment of the train units to the trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. We propose a heuristic algorithm based on the computation of a lower bound obtained by solving an Integer Linear Programming model that gives the optimal solution in a "peak period" of the day. The performance of the heuristic algorithm is computationally evaluated on real-world instances provided by a regional Italian Train Operator. The results are compared with those of existing methods from the literature, showing that the new method is able to obtain solutions of good quality in much shorter computing times.

Multimedia streaming applications running on next-generation parallel multiprocessor arrays in sub-45 nm technology face new challenges related to device and process variability, leading to performance and power variations across the cores. In this context, Quality of Service (QoS), as well as energy efficiency, could be severely impacted by variability. In this work, we propose a runtime variability-aware workload distribution technique for enhancing real-time predictability and energy efficiency based on an innovative Linear-Programming + Bin-Packing formulation which can be solved in linear time. We demonstrate our approach on the virtual prototype of a next-generation industrial multicore platform running representative multimedia applications. Experimental results confirm that our technique compensates variability, while improving energy-efficiency and minimizing deadline violations in presence of performance and power variations across the cores. The proposed policy can save up to 33 percent of energy with respect to the state-of-the-art policies and 65 percent of energy with respect to one variability-unaware task allocation policy while providing better QoS.

Frontmatter, Table of contents, Preface, Workshop Organization

The impact of variability on sub-45nm CMOS multimedia platforms makes hard to provide application QoS guarantees, as the speed variations across the cores may cause sub-optimal and sample-dependent utilization of the available resources and energy budget. These effects can be compensated by an efficient allocation of the workload at run-time. In the context of multimedia applications, a critical objective is to compensate core speed variability while matching time constraints without impacting the energy consumption. In this paper we present a new approach to compute optimal task allocations at run-time. The proposed strategy exploits an efficient and scalable implementation to find on-line the best possible solution in a tightly bounded time. Experimental results demonstrate the effectiveness of compensation both in terms of deadline miss rate and energy savings. Results have been compared with those obtained applying state-of-art techniques on a multithreaded MPEG2 decoder. The validation has been performed on a cycle-accurate virtual prototype of a next-generation industrial multicore platform that has been extended with process variability models.

Minimum linear arrangement is a classical basic combinatorial optimization problem from the 1960s that turns out to be extremely challenging in practice. In particular, for most of its benchmark instances, even the order of magnitude of the optimal solution value is unknown, as testified by the surveys on the problem that contain tables in which the best-known solution value often has one more digit than the best-known lower bound value. In this paper, we propose a linear programming-based approach to compute lower bounds on the optimum. This allows us, for the first time, to show that the best-known solutions are indeed not far from optimal for most of the benchmark instances.

We summarize our experience in solving combinatorial optimization problems arising in railway planning, illustrating all of these problems as integer multicommodity flow ones and discussing the main features of the mathematical programming models that were successfully used in the 1990s and in recent years to solve them.

Train Routing is a problem that arises in the early phase of the passenger railway planning process, usually several months before operating the trains. The main goal is to assign each train a stopping platform and the corresponding arrival/departure paths through a railway station. It is also called Train Platforming when referring to the platform assignment task. Railway stations often represent bottlenecks and train delays can easily disrupt the routing schedule. Thereby railway stations are responsible for a large part of the delay propagation in the whole network. In this research we present different models to compute robust routing schedules and we study their power in an online context together with different re-scheduling strategies. We also design a simulation framework and use it to evaluate and compare the effectiveness of the proposed robust models and re-scheduling algorithms using real-world data from Rete Ferroviaria Italiana, the main Italian Railway Infrastructure Manager.

In this paper we introduce a new general approximation method for set covering problems, based on the combination of randomized rounding of the (near-) optimal solution of the linear programming (LP) relaxation, leading to a partial integer solution and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. For d-dimensional vector packing, we obtain a polynomial-time randomized algorithm with asymptotic approximation guarantee arbitrarily close to $\ln d + 1$. For $d=2$, this value is $1.693\dots$; i.e., we break the natural 2 “barrier” for this case. Moreover, for small values of d this is a notable improvement over the previously known $O(\ln d)$ guarantee by Chekuri and Khanna [SIAM J. Comput., 33 (2004), pp. 837–851]. For two-dimensional bin packing with and without rotations, we obtain polynomial-time randomized algorithms with asymptotic approximation guarantee $1.525\dots$, improving upon previous algorithms with asymptotic performance guarantees arbitrarily close to 2 by Jansen and van Stee [On strip packing with rotations, in Proceedings of the 37th Annual ACM Symposium on the Theory of Computing, 2005, pp. 755–761] for the problem with rotations and $1.691\ldots$ by Caprara [Math. Oper. Res., 33 (2008), pp. 203–215] for the problem without rotations. The previously unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker [Combinatorica, 1 (1981), pp. 349–355]. We prove that their approximation scheme is “subset oblivious,” which leads to numerous applications.

Embedding cuts into a branch-and-cut framework is a delicate task, especially when a large set of cuts is available. In this paper we describe a separation heuristic for {0, ½} cuts, a special case of Chvátal-Gomory cuts, that tends to produce many violated inequalities within relatively short time. We report computational results on a large testbed of integer linear programming (ILP) instances of combinatorial problems including satisfiability, max-satisfiability, and linear ordering problems, showing that a careful cut-selection strategy produces a considerable speedup with respect to the cases in which either the separation heuristic is not used at all, or all of the cuts it produces are added to the LP relaxation.

In this paper we introduce a new general framework for set covering problems, based on the combination of randomized rounding of the (near-)optimal solution of the linear programming (LP) relaxation, leading to a partial integer solution, and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. Applying our general framework we obtain a polynomial-time randomized algorithm for d-dimensional vector packing with approximation guarantee arbitrarily close to ln d + 1. For d = 2, this value is 1.693 ..., i.e., we break the natural 2 "barrier" for this case. Moreover, for small values of d this is a notable improvement over the previously-known O(ln d) guarantee by Chekuri and Khanna (2004). For 2-dimensional bin packing with and without rotations, we construct algorithms with performance guarantee arbitrarily close to 1.525..., improving upon previous algorithms with performance guarantee of 2 + epsiv by Jansen and Zhang (2004) for the problem with rotations and1.691... by Caprara (2002) for the problem without rotations. The previously-unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker (1981). We prove that their approximation scheme is "subset oblivious", which leads to numerous applications. Another byproduct of our paper is an algorithm that solves a well-known configuration LP for 2-dimensional bin packing within a factor of (1 + epsiv) for any epsiv gt; 0. Interestingly, we do it without using an approximate separation oracle, which would correspond to a well-known geometric 2-dimensional knapsack. Although separation and optimization are equivalent (M. Grotschel et al, 1988) and the existence of an approximation scheme for the separation problem remains open, we are able to design an approximation scheme for the configuration LP since its objective function is unweighed

Finding a linear layout of a graph having minimum bandwidth is a combinatorial optimization problem that has been studied since the 1960s. Unlike other classical problems, the approach based on stating a suitable integer linear program and solving the associated linear-programming relaxation seems to be useless in this case. This makes it nontrivial to design algorithms capable of solving to optimality instances of reasonable size. In this paper, we illustrate a new simple lower bound on the optimal bandwidth and its extension within an enumerative algorithm, leading to integer linear-programming relaxations that can be solved efficiently and provide effective lower bounds if part of the layout is fixed. Keeping the integrality constraints in these relaxations is essential for this purpose. We show that the resulting method can solve to proven optimality 24 out of the 30 instances from the literature with less than 200 nodes, each in less than a minute on a personal computer. The new approach is also analyzed on randomly generated instances with up to 1,000 nodes. Moreover, we propose a method to compute the well-known density lower bound on the optimal bandwidth, which succeeds in finding this bound within minutes for most instances in the literature with up to 250 nodes.

Focusing on embedded applications, scratchpad memories (SPMs) look like a best-compromise solution when taking into account performance, energy consumption, and die area. The main challenge in SPM design is to optimally map memory locations to scratchpad locations. This paper describes an algorithm to solve such a mapping problem by means of dynamic programming applied to a synthesizable hardware architecture. The algorithm works by mapping segments of external memory to physically partitioned banks of an on-chip SPM; this architecture provides significant energy savings. The algorithm does not require any user-set bound on the number of partitions and takes into account partitioning overhead. Improving on previous solutions, execution time is polynomial in the number of memory locations, even in the most general solving policy. This has the major practical advantage of allowing an arbitrary number of scratchpad segments, something that was impossible with previous methods, whose running time is exponential to this number. Strategies to optimize memory requirements and speed of the algorithm are exploited. Additionally, we integrate this algorithm in a complete and automated design, simulation, and synthesis flow.

Abstract We illustrate efficient algorithms to find a maximum stable set and a maximum matching in a graph with n nodes given by the edge union of d threshold graphs on the same node set, in case the d graphs in the union are known. Actually, because the edge set of a threshold graph can be implicitly represented by assigning values to the nodes, we assume that we know these values for each of the d graphs in the union. We present an O(n log n + nd−1) time algorithm to find a maximum stable set and an O(n2) time algorithm to find a maximum matching, in case d is constant. For the case d = 2, the running time of the latter is reduced to O(n log n) provided an additional technical condition is satisfied. The natural application of our results is the fast computation of lower bounds for the d‐dimensional bin packing problem, for which the compatibility relations between items are represented by the edge union of d threshold graphs with one node for each item, the value of the node for the i‐th graph being equal to the size of the item on the i‐th dimension. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 266–280 2004

Abstract We address the problem of finding the largest collection of edge‐disjoint cuts in an undirected graph, dubbed CUT PACKING, focusing on its complexity, about which very little is known. We show a very close relationship with INDEPENDENT SET, namely, for the same graph G , the size of the largest cut packing of G is at least the independence number of G , and at most twice that number. This implies that any approximation guarantee for INDEPENDENT SET immediately extends to CUT PACKING within a factor of 2. In particular, this yields a 2‐approximation algorithm for CUT PACKING in perfect graphs. We then present polynomial‐time algorithms for several classes of perfect (and related) graphs, including triangulated graphs and their complements, bipartite graphs and their complements, and Seymour graphs. Finally, we discuss various linear programming relaxations for the problem, finding combinatorial dual problems of CUT PACKING and characterizing the cases in which duality is strong. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 1–11 2004

Focusing on embedded applications, scratchpad memories (SPMs) look like a best-compromise solution when taking into account performance, energy consumption and die area. The main challenge in SPM design is mapping memory locations to scratchpad locations. This paper describes an algorithm to optimally solve such a mapping problem by means of Dynamic Programming applied to a synthesizable hardware architecture. The algorithm works by mapping segments of external memory to physically partitioned banks of an on-chip SPM; this architecture provides significant energy savings. The algorithm does not require any user-set bound on the number of partitions and takes into account partitioning overhead. Improving on previous solutions, execution time is polynomial in the input size. Strategies to optimize memory requirements and speed of the algorithm are exploited. Additionally, we integrate this algorithm in a complete and automated design, simulation and synthesis flow.

In this paper, we study the Reversal Median Problem (RMP), which arises in computational biology as a basic model for the reconstruction of evolutionary trees. Given q genomes, RMP calls for another genome such that the sum of the reversal distances between this genome and the given ones is minimized. So far, the problem has been considered too complex to derive mathematical models useful for its analysis and solution. We provide a powerful graph-theoretic relaxation of RMP, essentially calling for a perfect matching in a graph that forms the maximum number of cycles jointly with q given perfect matchings. By using this relaxation, we can show the complexity of RMP as well as design effective algorithms for its exact and heuristic solution. We report the solution of a few hundred instances associated with real-world genomes.

We consider 2-Dimensional (Finite) Bin Packing (2BP), which is one of the most important generalizations of the well-known Bin Packing (BP) and calls for orthogonally packing a given set of rectangles (that cannot be rotated) into the minimum number of unit size squares. There are many open questions concerning the approximability of 2BP, whereas the situation for the 2-stage case, in which the items must first be packed into shelves that are then packed into bins, is essentially settled. For this reason, we study the asymptotic worst-case ratio between the optimal solution values of the 2-stage and general 2BP, showing that it is equal to T/sub /spl infin//=1.691..., the well-known worst-case ratio of the Harmonic algorithm for BP. This ratio is achieved by packing the items into shelves by decreasing heights as in the Harmonic algorithm and then optimally packing the resulting shelves into bins. This immediately yields polynomial time approximation algorithms for 2BP whose asymptotic worst-case ratio is arbitrarily close to T/sub /spl infin//, i.e. substantially smaller than 2+/spl epsi/, that was the best ratio achievable so far and constituted the first (recent) improvement over the 2.125 ratio shown in the early 80s. In particular, we manage to push the approximability threshold below 2, which is often a critical value in approximation. The main idea in our analysis is to use the fact that the fractional and integer BP solutions have almost the same value, which is implicit in the approximation schemes for the problem, as a stand-alone structural result. This implies the existence of modified heights for the shelves whose sum yields approximately the number of bins needed to pack them. With this in mind, our proof can easily be adapted to different cases. For instance, we can derive new upper bounds on the worst-case ratio of several shelf heuristics for 2BP, among which a bound of (17/10)(11/9)=2.077... (rather than 2.125) on the 20-years-lasting champion mentioned above. Moreover, we can easily derive the asymptotic worst-case ratio between the 2-stage and general 2BP solution values as a function of the maximum width of the rectangles, showing that this ratio is independent of the maximum height. Finally, under a conjecture that appears to be supported by experimental evidence, we show that our main heuristic has an asymptotic worst-case ratio in the interval (1.490,1.507) when all the rectangles to be packed are squares. This would improve the current best worst-case ratio of 14/9=1.555... for this special case.

We illustrate a new approach to the Contact Map Overlap problem for the comparison of protein structures. The approach is based on formulating the problem as an integer linear program and then relaxing in a Lagrangian way a suitable set of constraints. This relaxation is solved by computing a sequence of simple alignment problems, each in quadratic time, and near--optimal Lagrangian multipliers are found by subgradient optimization. By our approach we achieved a substantial speedup over the best existing methods. We were able to solve optimally for the first time instances for PDB proteins with about 1000 residues and 2000 contacts. Moreover, within a few hours we compared 780 pairs in a testbed of 40 large proteins, finding the optimal solution in 150 cases. Finally, we compared 10,000 pairs of proteins from a test set of 269 proteins in the literature, which took a couple of days on a PC.

We describe an exact algorithm for the problem of sorting a permutation by the minimum number of reversals, originating from evolutionary studies in molecular biology. Our approach is based on an integer linear programming formulation of a graph-theoretic relaxation of the problem, calling for a decomposition of the edge set of a bicolored graph into the maximum number of alternating cycles. The formulation has one variable for each alternating cycle, and the associated linear programming relaxation is solved by column generation. A major advantage with respect to previous approaches is that the subproblem to face in the column-generation phase no longer requires the solution of min-cost general matching problems, but of min-cost bipartite matching problems. Experiments show that there is a tremendous speed-up in going from general matching to bipartite matching, although the best-known algorithms for the two problems have the same theoretical worst-case complexity. We also show the worst-case ratio between the lower bound value obtained by our new method and previous ones. We illustrate the effectiveness of our approach through extensive computational experiments. In particular, we can solve to proven optimality the largest real-world instances from the literature in a few seconds, and the other (smaller) real-world instances within a few milliseconds on a workstation. Moreover, we can solve to optimality random instances with n + 100 within 3 seconds, and with n + 200 within 15 minutes, where n is the size of the permutation, whereas the size of the instances solvable by previous approaches was at most 100. We also describe a polynomial-time heuristic algorithm that consistently finds solutions within 2% of the optimum for random instances with n up to 1000.

We consider two generalizations of signed Sorting Bg Reversals (SBR), both aimed at formalizing the problem of reconstructing the evolutionary history of a set of species.In particular, we address Multiple SBR, calling for a signed permutation at minimum reversal distance from a given set of signed permutations, and Dee SBR, calling for a tree with the minimum number of edges spanning a given set of nodes in the complete graph where each node corresponds to a signed permutation and there is an edge between each pair of signed permutations one reversal away from each other.We describe a graph-theoretic relaxation of MSBR, which is the counterpart of the so-called alternating-cycle decomposition relaxation for SBR., illustrating a convenient mathematical formulation for this relaxation.Moreover, we use this relaxation to show that, even if the number of given permutations equals 3, MSBR is NP-hard, and hence so is nee SBR.In fact, we show that the two problems are APX-hard, i.e. they do not have a polynomial-time approximation scheme unless P=NP.Finally, we mention known Zapproximation algorithms for two general problems which generalize MSBR and Tree SBR, respectively.To our knowledge, this work is the f?rst one discussing the complexity of MBSR (and Tree SBR), as well as potential solution approaches to the problem based on the use of a tight relaxation.

The Quadratic Knapsack Problem (QKP) calls for maximizing a quadratic objective function subject to a knapsack constraint, where all coefficients are assumed to be nonnegative and all variables are binary. The problem has applications in location and hydrology, and generalizes the problem of checking whether a graph contains a clique of a given size. We propose an exact branch-and-bound algorithm for QKP, where upper bounds are computed by considering a Lagrangian relaxation that is solvable through a number of (continuous) knapsack problems. Suboptimal Lagrangian multipliers are derived by using subgradient optimization and provide a convenient reformulation of the problem. We also discuss the relationship between our relaxation and other relaxations presented in the literature. Heuristics, reductions, and branching schemes are finally described. In particular, the processing of each node of the branching tree is quite fast: We do not update the Lagrangian multipliers, and use suitable data structures to compute an upper bound in linear expected time in the number of variables. We report exact solution of instances with up to 400 binary variables, i.e., significantly larger than those solvable by the previous approaches. The key point of this improvement is that the upper bounds we obtain are typically within 1% of the optimum, but can still be derived effectively. We also show that our algorithm is capable of solving reasonable-size Max Clique instances from the literature.

We analyze the strong relationship among three combinatorial problems, namely, the problem of sorting a permutation by the minimum number of reversals (MIN-SBR), the problem of finding the maximum number of edge-disjoint alternating cycles in a breakpoint graph associated with a given permutation (MAX-ACD), and the problem of partitioning the edge set of an Eulerian graph into the maximum number of cycles (MAX-ECD). We first illustrate a nice characterization of breakpoint graphs, which leads to a linear-time algorithm for their recognition. This characterization is used to prove that MAX-ECD and MAX-ACD are equivalent, showing the latter to be NP-hard. We then describe a transformation from MAX-ACD to MIN-SBR, which is therefore shown to be NP-hard as well, answering an outstanding question which has been open for some years. Finally, we derive the worst-case performance of a well-known lower bound for MIN-SBR, obtained by solving MAX-ACD, discussing its implications on approximation algorithms for MIN-SBR.

In this paper, we investigate the possibility of integrating Artificial Intelligence (AI) and Operations Research (OR) techniques for solving the Crew Rostering Problem (CRP). CRP calls for the optimal sequencing of a given set of duties into rosters satisfying a set of constraints. The optimality criterion requires the minimization of the number of crews needed to cover the duties. This kind of problem has been traditionally solved by OR techniques. In recent years, a new programming paradigm based on Logic Programming, named Constraint Logic Programming (CLP), has been successfully used for solving hard combinatorial optimization problems. CLP maintains all the advantages of logic programming such as declarativeness, non-determinism and an incremental style of programming, while overcoming its limitations, mainly due to the inefficiency in exploring the search space. CLP achieves good results on hard combinatorial optimization problems which, however, are not comparable with those achieved by OR approaches. Therefore, we integrate both techniques in order to design an effective heuristic algorithm for CRP which fully exploits the advantages of the two methodologies: on the one hand, we maintain the declarativeness of CLP, its ease of representing knowledge and its rapid prototyping; on the other hand, we inherit from OR some efficient procedures based on a mathematical approach to the problem. Finally, we compare the results we achieved by means of the integration with those obtained by a pure OR approach, showing that AI and OR techniques for hard combinatorial optimization problems can be effectively integrated. © 1998 John Wiley & Sons, Ltd.

The index selection problem (ISP) is an important optimization problem in the physical design of databases. The aim of this paper is to show that ISP, although NP-hard, can in practice be solved effectively through well-designed algorithms. We formulate ISP as a 0-1 integer linear program and describe an exact branch-and-bound algorithm based on the linear programming relaxation of the model. The performance of the algorithm is enhanced by means of procedures to reduce the size of the candidate index set. We also describe heuristic algorithms based on the solution of a suitably defined knapsack subproblem and on Lagrangian decomposition. Finally, computational results on several classes of test problems are given. We report the exact solution of large-scale ISP instances involving several hundred indexes and queries. We also evaluate one of the heuristic algorithms we propose on very large-scale instances involving several thousand indexes and queries and show that it consistently produces very tight approximate (and sometimes provably optimal) solutions. Finally, we discuss possible extensions and future directions of research.