We consider binary integer programming problems with the min-max regret objective function under interval objective coefficients. We propose a heuristic framework, the iterated dual substitution (iDS) algorithm, which iteratively invokes a dual substitution heuristic and excludes from the search space any solution already checked in previous iterations. In iDS, we use a best scenario–based lemma to improve performance. We apply iDS to four typical combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the generalized assignment problem, and the set covering problem. For the multidimensional knapsack problem, we compare the iDS approach with two algorithms widely used for problems with the min-max regret criterion: a fixed-scenario approach, and a branch-and-cut approach. The results of computational experiments on a broad set of benchmark instances show that the proposed iDS approach performs best on most tested instances. For the knapsack problem, the generalized assignment problem, and the set covering problem, we compare iDS with state-of-the-art results. The iDS algorithm successfully updates best-known records for a number of benchmark instances. Summary of Contribution: This paper proposes a heuristic framework for binary integer programming (BIP) problems with the min-max regret objective function under interval objective coefficients. We selected four representative NP-hard combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the set covering problem, and the generalized assignment problem. We show the effectiveness and efficiency of the approach by comparing with state-of-the-art results.

We consider a generalization of the 0–1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The interval min–max regret knapsack problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the second level of the polynomial hierarchy hence it is most probably not in 𝒩𝒫. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an 𝒩𝒫-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm and evaluate their performance through extensive computational experiments.

In IEEE 802.16, the wireless resources are logically partitioned into 5-ms frames, which extend in two dimensions: time and frequency. To break down the complexity of resource allocation at the base station, a split approach has been proposed in the literature, where the tasks of scheduling packets and allocating them into frames are solved in separate and subsequent stages. In this paper, we focus on the allocation task alone, which is addressed in its full complexity, i.e., by considering that data within the frame must be allocated as bursts with rectangular shape, each consisting of a set of indivisible sub-bursts, and that a variable portion of the frame is reserved for in-band signaling. After proving that the resulting allocation problem is NP-hard, we develop an efficient heuristic algorithm, called Recursive Tiles and Stripes (ℜTS), to solve it. ℜTS, in addition to handling a more general problem, is shown to perform better than state-of-the-art solutions via numerical analysis with realistic system parametrization. Furthermore, an extensive evaluation of the interaction between the scheduler and the allocator is carried out in a wide variety of network scenarios .

The IEEE 802.16 standard uses Orthogonal Frequency Division Multiple Access (OFDMA) for mobility support. Therefore, the medium access control frame extends in two dimensions, i.e., time and frequency. At the beginning of each frame, i.e., every 5 ms, the base station is responsible both for scheduling packets, based on the negotiated quality of service requirements, and for allocating them into the frame, according to the restrictions imposed by 802.16 OFDMA. To break down the complexity, a split approach has been proposed in the literature, where the two tasks are solved in separate and subsequent stages. In this paper we focus on the allocation task alone, which is addressed in its full complexity, i.e., by considering that data within the frame must be allocated as bursts with rectangular shape, each consisting of a set of indivisible sub-bursts, and that a variable portion of the frame is reserved for in-band signaling. After proving that the resulting allocation problem is NP-hard, we develop an efficient heuristic algorithm, called Recursive Tiles and Stripes (RTS), to solve it. RTS, in addition to handle a more general problem, is shown to perform better than state-of-the-art solutions via numerical analysis with realistic system parametrization.

Given a set of jobs with associated processing times, and a set of identical machines, each of which can process at most one job at a time, the parallel machine scheduling problem is to assign each job to exactly one machine so as to minimize the maximum completion time of a job. The problem is strongly NP-hard and has been intensively studied since the 1960s. We present a metaheuristic and an exact algorithm and analyze their average behavior on a large set of test instances from the literature. The metaheuristic algorithm, which is based on a scatter search paradigm, computationally proves to be highly effective and capable of solving to optimality a very high percentage of the publicly available test instances. The exact algorithm, which is based on a specialized binary search and a branch-and-price scheme, was able to quickly solve to optimality all remaining instances.

Abstract This article addresses the well‐known Capacitated Vehicle Routing Problem (CVRP), in the special case where the demand of a customer consists of a certain number of two‐dimensional weighted items. The problem calls for the minimization of the cost of transportation needed for the delivery of the goods demanded by the customers, and carried out by a fleet of vehicles based at a central depot. In order to accommodate all items on the vehicles, a feasibility check of the two‐dimensional packing (2L) must be executed on each vehicle. The overall problem, denoted as 2L‐CVRP, is NP‐hard and particularly difficult to solve in practice. We propose a Tabu Search algorithm, in which the loading component of the problem is solved through heuristics, lower bounds, and a truncated branch‐and‐bound procedure. The effectiveness of the algorithm is demonstrated through extensive computational experiments. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

for the Vehicle Routing Problem with Two-Dimensional Loading Constraints" by M. Gendreau et al., which appeared in the January issue of Networks (Networks 51 (2008), 4-18), the last author's name was misspelled. Silvano Martello's

We consider the problem of orthogonally packing a given set of rectangular-shaped boxes into the minimum number of three-dimensional rectangular bins. The problem is NP-hard in the strong sense and extremely difficult to solve in practice. We characterize relevant subclasses of packing and present an algorithm which is able to solve moderately large instances to optimality. Extensive computational experiments compare the algorithm for the three-dimensional bin packing when solving general orthogonal packings and when restricted to robot packings.

We consider the problem of orthogonally packing a given set of rectangular items into a given strip, by minimizing the overall height of the packing. The problem is NP-hard in the strong sense, and finds several applications in cutting and packing. We propose a new relaxation that produces good lower bounds and gives information to obtain effective heuristic algorithms. These results are used in a branch-and-bound algorithm, which was able to solve test instances from the literature involving up to 200 items.

Two-dimensional bin packing problems consist of allocating, without overlapping, a given set of small rectangles (items) to a minimum number of large identical rectangles (bins), with the edges of the items parallel to those of the bins. According to the specific application, the items may either have a fixed orientation or they can be rotated by 90°. In addition, it may or not be imposed that the items are obtained through a sequence of edge-to-edge cuts parallel to the edges of the bin. In this article, we consider the class of problems arising from all combinations of the above requirements. We introduce a new heuristic algorithm for each problem in the class, and a unified tabu search approach that is adapted to a specific problem by simply changing the heuristic used to explore the neighborhood. The average performance of the single heuristics and of the tabu search are evaluated through extensive computational experiments.

We consider the classical problem of scheduling n tasks with given processing time on m identical parallel processors so as to minimize the maximum completion time of a task. We introduce lower bounds, approximation algorithms and a branch-and-bound procedure for the exact solution of the problem. Extensive computational results show that, in many cases, large-size instances of the problem can be solved exactly. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

article Free AccessArtifacts AvailableArtifacts Evaluated & ReusableAlgorithm 632: A program for the 0–1 multiple knapsack problem Authors: Silvano Martello DEIS, University of Bologna, Viale Risorgimento 2, Bologne, Italy DEIS, University of Bologna, Viale Risorgimento 2, Bologne, ItalyView Profile , Paolo Toth University of Florence University of FlorenceView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 11Issue 2pp 135–140https://doi.org/10.1145/214392.214397Published:01 June 1985Publication History 15citation1,386DownloadsMetricsTotal Citations15Total Downloads1,386Last 12 Months38Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Additional Key Words and Phrases Hamfltoman circuit

Abstract The problem considered is that of removing the maximum number of edges from a digraph without affecting its reachability properties. The worst‐case performance of algorithms from the related literature is analyzed; it is found that Hsu's method contains some mistakes. A new algorithm is presented, based on a reduction procedure and on a branch and bound search; its efficiency is studied both theoretically and through computational experiments.