The two-dimensional bin packing problem calls for packing a set of rectangular items into a minimal set of larger rectangular bins. Items must be packed with their edges parallel to the borders of the bins, cannot be rotated, and cannot overlap among them. The problem is of interest because it models many real-world applications, including production, warehouse management, and transportation. It is, unfortunately, very difficult, and instances with just 40 items are unsolved to proven optimality, despite many attempts, since the 1990s. In this paper, we solve the problem with a combinatorial Benders decomposition that is based on a simple model in which the two-dimensional items and bins are just represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but we enrich it with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The resulting algorithm behaved very well on the benchmark sets of instances, improving on average on previous algorithms from the literature and solving for the first time a number of open instances. Summary of Contribution: We address the two-dimensional bin packing problem (2D-BPP), which calls for packing a set of rectangular items into a minimal set of larger rectangular bins. The 2D-BPP is a very difficult generalization of the standard one-dimensional bin packing problem, and it has been widely studied in the past because it models many real-world applications, including production, warehouse management, and transportation. We solve the 2D-BPP with a combinatorial Benders decomposition that is based on a model in which the two-dimensional items and bins are represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but it is enriched with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The algorithm we developed has been extensively tested on the most well-known benchmark set from the literature, which contains 500 instances. It behaved very well, improving on average upon previous algorithms, and solving for the first time a number of open instances. We analyzed in detail several configurations before obtaining the best one and discussed several insights from this analysis in the manuscript.

Although small cells (SC) densification approach plays a prominent role in achieving the data rate and coverage requirements in 5G networks, it poses serious challenges concerning the flexible and cost efficient backhauling solutions. The traditional terrestrial backhauling hubs are subject to limited line of sight probabilities in such dense networks. Having this challenge in hand, and recognizing the increasing interest in the unmanned aerial vehicle (UAV) enabled communication systems, we address the problem of wireless multihop backhauling of SCs using UAV hubs. We present two linear optimization programs that optimize the SC-UAV association and the SC-SC formation in order to maximize the total backhaul flow. Some practical constraints are considered, such as backhaul reliability, association criteria, SC relaying capacity and the number of available links at each SC. Numerical simulations show that the approach allowing partial demand fulfillment of the SCs outperforms the binary one in terms of accumulated rate and the percentage of associated SCs, even at low number of maximum hops and links allowed.

Network densification is promising to achieve higher data rates and higher network capacity, while causing new backhauling challenges especially when the network is highly dense. The flexible and cost efficient backhauling solutions are among the most concerning issues. Due to the high density of the next generation networks, the terrestrial wired backhauling approaches are not cost efficient. Having this challenge in hand, and recognizing the advantages of the networked flying platform (NFP)-enabled communications, we address in this paper the problem of wireless multi-hop backhauling of small cells (SC) using NFP hubs. We propose an efficient iterative heuristic algorithm that jointly optimize the SCNFP association and the SC-SC formation in order to maximize the total backhaul flow, with practical constraints in consideration, such as backhaul reliability, hardware and processing limitations in the SCs and the NFPs. Numerical simulations show that the proposed algorithm can achieve close to optimal solution at a much faster convergence rate.

This paper introduces a novel class of generalized assignment problems with location/allocation considerations that arises in several applications including retail shelf space allocation. We consider a set of items where each item may represent a family of products and a set of variable-sized knapsacks that may represent shelves, which comprise contiguous segments having distinct attractiveness. The decision-maker seeks to assign the set of items to these knapsacks, specify their segment assignments within knapsacks, and determine their total allocated space within predetermined lower/upper bounds in a fashion that maximizes a reward-based objective function. We develop an effective optimization-based very large-scale neighborhood search (VLNS), which greatly outperforms the best solution identified by CPLEX within one CPU hour, whereas general-purpose solver heuristics failed to provide feasible solutions to most of the larger instances within a time limit comparable to the VLNS algorithm run times. Our computational study was carried out on randomly generated computationally challenging instances with up to 210 items and 42 knapsacks and on a case study motivated by a shelf space allocation problem. Our results demonstrate that the proposed approach consistently produces high-quality solutions.

We investigate modeling approaches and exact solution methods for a generalized assignment problem with location/allocation (GAPLA) considerations. In contrast with classical generalized assignment problems, each knapsack in GAPLA is discretized into consecutive segments having different levels of attractiveness. To maximize a total reward function, the decision maker decides not only about item knapsack assignments, but also the specific location of items within their assigned knapsacks and their total space allocation within prespecified lower and upper bounds. Mathematical programming formulations are developed for single and multiple knapsack variants of this problem along with valid inequalities, preprocessing routines, and model enhancements. Further, a branch-and-price algorithm is devised for a set partitioning reformulation of GAPLA, and is demonstrated to yield substantial computational savings over solving the original formulation using branch-and-bound/cut solvers such as CPLEX over challenging problem instances.

The main airline operations consist of schedule planning, fleet assignment, aircraft routing, and crew scheduling. To improve profitability, we present in this paper an integrated fleet assignment model with schedule planning by simultaneously considering optional flight legs to select along with the assignment of aircraft types to all scheduled legs. In addition, we consider itinerary-based demands for multiple fare classes. A polyhedral analysis is conducted of the proposed mixed-integer programming model to tighten its representation via several classes of valid inequalities. Solution approaches are developed by applying Benders' decomposition method to the resulting lifted model, and computational results are presented using real data obtained from a major U.S. airline to demonstrate the efficacy of the proposed procedures.

The ant colony optimization is a meta-heuristic inspired by knowledge sharing amongst ants using pheromone, which serves as a kind of collective memory. Since the past few years, there have been several successful applications of this new approach for finding approximate solutions for computationally difficult problems in reasonable times. In this paper, we study the generalized minimum spanning tree problem that involves the design of a minimum weight connected network spanning at least one node out of every disjoint subset of the nodes in a graph. This problem has a wealth of pertinence to a wide range of applications in different areas. As the problem is known as computationally challenging, we adopt the ant colony optimization strategy and present a new solution method, called Ant-Tree, to develop approximate solutions. As an initial attempt, our study aims to provide an investigation of the ant colony optimization approach for coping with tree optimization problems. Through computational experiments, we compare the performances of our approach and the method available in the literature. Numerical results indicate that the proposed method is effective in producing quality approximate solutions.