A Hierarchy of Relaxations Leading to the Convex Hull Representation for General Discrete Optimization Problems

We consider linear mixed-integer programs where a subset of the variables are restricted to take on a finite number of general discrete values. For this class of problems, we develop a reformulation-linearization technique (RLT) to generate a hierarchy of linear programming relaxations that spans the spectrum from the continuous relaxation to the convex hull representation. This process involves a reformulation phase in which suitable products using a defined set of Lagrange interpolating polynomials (LIPs) are constructed, accompanied by the application of an identity that generalizes x(1−x) for the special case of a binary variable x. This is followed by a linearization phase that is based on variable substitutions. The constructs and arguments are distinct from those for the mixed 0-1 RLT, yet they encompass these earlier results. We illustrate the approach through some examples, emphasizing the polyhedral structure afforded by the linearized LIPs. We also consider polynomial mixed-integer programs, exploitation of structure, and conditional-logic enhancements, and provide insight into relationships with a special-structure RLT implementation.     

Some Classes of Valid Inequalities and Convex Hull Characterizations for Dynamic Fixed-Charge Problems under Nested Constraints

This paper studies the polyhedral structure of dynamic fixed-charge problems that have nested relationships constraining the flow or activity variables. Constraints of this type might typically arise in hierarchical or multi-period models and capacitated lot-sizing problems, but might also be induced among choices of key variables via an LP-based post-optimality analysis. We characterize several classes of valid inequalities and inductively derive convex hull representations in a higher dimensional space using lifting constructs based on the Reformulation-Linearization Technique. Relationships with certain known classes of valid inequalities for single item capacitated lot-sizing problems are also identified.     

Enabling End-to-End QoS over Hybrid Wired-Wireless Networks

Providing end-to-end parameterized QoS is desirable for many network applications and has received a lot of attention in recent years. However, it remains a challenge, especially over hybrid networks involving both wired networks and wireless access segments (such as IEEE 802.11 Wireless Local Area Networks (WLANs)). The difficulty in achieving such QoS arises mainly because wireless segments often constitute “gaps" in terms of resource guarantee, due to the lack of efficient resource scheduling and management ability over shared wireless media, as well as the lack of an appropriate QoS signaling interface to seamlessly embed these wireless segments into an end-to-end QoS signaling system. In this paper, we consider the scenario where an IEEE 802.11 wireless node wishes to make an end-to-end resource reservation to a remote wired Internet node and vice versa. We propose Wireless Subnet Bandwidth Manager (Wireless SBM), an extension of SBM protocol to WLANs, to provide seamless end-to-end resource reservations. Wireless SBM utilizes the enhanced resource management ability provided by Hybrid Coordination Function (introduced in the upcoming IEEE 802.11e standard) to provide parameterized resource reservation and admission control.     

Spectrum Sharing for Multi-Hop Networking with Cognitive Radios

Cognitive radio (CR) capitalizes advances in signal processing and radio technology and is capable of reconfiguring RF and switching to desired frequency bands. It is a frequency-agile data communication device that is vastly more powerful than recently proposed multi-channel multi-radio (MC-MR) technology. In this paper, we investigate the important problem of multi-hop networking with CR nodes. For such a network, each node has a pool of frequency bands (typically of unequal size) that can be used for communication. The potential difference in the bandwidth among the available frequency bands prompts the need to further divide these bands into sub-bands for optimal spectrum sharing. We characterize the behavior and constraints for such a multi-hop CR network from multiple layers, including modeling of spectrum sharing and sub-band division, scheduling and interference constraints, and flow routing. We develop a mathematical formulation with the objective of minimizing the required network-wide radio spectrum resource for a set of user sessions. Since the formulated model is a mixed-integer non-linear program (MINLP), which is NP-hard in general, we develop a lower bound for the objective by relaxing the integer variables and using a linearization technique. Subsequently, we design a near-optimal algorithm to solve this MINLP problem. This algorithm is based on a novel sequential fixing procedure, where the integer variables are determined iteratively via a sequence of linear programs. Simulation results show that solutions obtained by this algorithm are very close to the lower bounds obtained via the proposed relaxation, thus suggesting that the solution produced by the algorithm is near-optimal.     

Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem

This paper deals with an unrelated machine scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. We present a zero-one integer programming formulation of this problem. The linear programming relaxation of this formulation affords a tight lower bound and often generates an integer optimal solution for the problem. By exploiting the special structures inherent in the formulation, we develop some classes of strong valid inequalities that can be used to tighten the initial formulation, as well as to provide cutting planes in the context of a branch-and-cut procedure. A major computational bottleneck is the solution of the underlying linear programming relaxation because of the extremely high degree of degeneracy inherent in the formulation. In order to overcome this difficulty, we employ a Lagrangian dual formulation to generate lower and upper bounds and to drive the branch-and-bound algorithm. As a practical instance of the unrelated machine scheduling problem, we describe a combinatorial naval defense problem. This problem seeks to schedule a set of illuminators (passive homing devices) in order to strike a given set of targets using surface-to-air missiles in a naval battle-group engagement scenario. We present computational results for this problem using suitable realistic data.     

Quality of service models for heterogeneous networks: overview and challenges

The proliferation and convergence of different types of wired, wireless and mobile networks (such as WiMAX, Wireless Mesh Networks, WPANs, WLANs, etc) and cellular-based networks are crucial for the success of next-generation networks. Traditional wired/wireless networks can hardly meet the requirements of future integrated-service networks which are expected to carry multimedia traffic with various quality of service (QoS) requirements. Therefore, it is necessary to develop efficient global control mechanisms that can maintain QoS requirements to maximize network resources utilization, and minimize operational costs on all the types of wireless mobile networks. In this paper, we present an overview of QoS paradigms for heterogeneous networks and focus on those based on deterministic and probabilistic QoS.     

ElectroBlocks: A blockchain‐based energy trading scheme for smart grid systems

Smart grid systems are widely used across the world for providing demand response management between users and service providers. In most of the energy distributions scenarios, the traditional grid systems use the centralized architecture, which results in large transmission losses and high overheads during power generation. Moreover, owing to the presence of intruders or attackers, there may be a mismatch between demand and supply between utility centers (suppliers) and end users. Thus, there is a need for an automated energy exchange to provide secure and reliable energy trading between users and suppliers. We found, from the existing literature, that blockchain can be an effective solution to handle the aforementioned issues. Motivated by these facts, we propose a blockchain‐based smart energy trading scheme, ElectroBlocks, which provides efficient mechanisms for secure energy exchanges between users and service providers. In ElectroBlocks, nodes in the network validate the transaction using two algorithms that are cost aware and store aware. The cost‐aware algorithm locates the nearest node that can supply the energy, whereas the store‐aware algorithm ensures that the energy requests go to the node with the lowest storage space. We evaluated the performance of the ElectroBlocks using performance metrics such as mining delay, network exchanges, and storage energy. The simulation results obtained demonstrate that ElectroBlocks maintains a secure trade‐off between users and service providers when using the proposed cost‐aware and store‐aware algorithms.     

Fuzzy-based techniques for clustering in wireless sensor networks (WSNs): Recent advances,challenges, and future directions

A wireless sensor network (WSN) is a network of tiny sensors deployed to collect data. These sensors are powered with batteries that have limited power. Recharging and/or replacement of these batteries, however, are not always feasible. Over the past few years, WSN applications are being deployed in diverse fields such as military, manufacturing, healthcare, agriculture, and so on. With the ever-increasing applications of WSNs, improving the energy efficiency of the WSNs still remains to be a challenge. Applying fuzzy logic to the problem of clustering exploits the uncertainty associated with the factors that affect the lifetime of these sensors and enables the development of models that would improve their performance in real-world applications. We present a comprehensive review of various fuzzy-based techniques for clustering in WSNs whose main goal is to optimize energy usage in WSNs while simultaneously improving their overall performance.     

Models and algorithms for the scheduling of a doubles tennis training tournament

We address a doubles tennis scheduling problem in the context of a training tournament, and develop a 0–1 mixed-integer programming model that attempts to balance the partnership and the opponentship pairings among the players. We propose effective symmetry-defeating strategies that impose certain decision hierarchies within the model, which serve to significantly enhance algorithmic performance via their pruning effect. We also discuss the concept of symmetry compatible formulations, and highlight the importance of crafting formulations in discrete optimization in a fashion that enhances the interplay between the original model structure, branch-and-bound algorithms (as implemented in commercial packages such as CPLEX), and the structure of specific symmetry-defeating hierarchical constraints. Finally, various specialized heuristics are devised and are computationally evaluated along with the exact solution schemes using a set of realistic practical test problems.     

Mixed-integer programming models for an employee scheduling problem with multiple shifts and work locations

This paper is concerned with the problem of assigning employees to gas stations owned by the Kuwait National Petroleum Corporation (KNPC), which hires a firm to prepare schedules for assigning employees to about 86 stations distributed all over Kuwait. Although similar employee scheduling problems have been addressed in the literature, certain peculiarities of the problem require novel mathematical models and algorithms to deal with the specific nature and size of this problem. The problem is modeled as a mixed-integer program, and a problem size analysis based on real data reveals that the formulation is too complex to solve directly. Hence, a two-stage approach is proposed, where the first stage assigns employees to stations, and the second stage specifies shifts and off-days for each employee. Computational results related to solving the two-stage models directly via CPLEX and by specialized heuristics are reported. The two-stage approach provides daily schedules for employees for a given time horizon in a timely fashion, taking into consideration the employees’ expressed preferences. This proposed modeling approach can be incorporated within a decision support system to replace the current manual scheduling practice that is often chaotic and has led to feelings of bias and job dissatisfaction among employees.