Nonlinear Combinatorial Optimization

In a wireless sensor network, a topology control problem aims to adjust power of sensors so that the topology supported by the power has some desirable property and the total power is as small as possible. In this chapter, we shall present studies on the topology control problem with the properties of containing a spanning tree, a strongly connected spanning digraph, and a broadcast tree. Minimum spanning tree plays an important role in all these studies, serving as a linearization method for these nonlinear problems.

Newton method is a classic and powerful method in continuous nonlinear optimization. However in this chapter, we introduce its counterpart in combinatorial optimization: discrete Newton method, and show that there exists a strong polynomial time algorithm for finding the root of a piecewise linear decreasing function, where the number of pieces is exponential. Then we show how to apply it in solving linear fractional combinatorial optimization problem, inverse combinatorial problem, and bottleneck expansion problem.

We offer an overview on submodular optimization for both single- and multiple-objectives, with the moderate goal to highlight the different angles in interpreting submodularity and associated concepts.

In supply chain management and other operations management applications, various discrete convexities are important tools in modeling complementary or supplementary behaviors. Furthermore, the discrete nature of many decision scenarios also requires optimization tools from discrete convex theory.

In this chapter, we aim at introducing the classical discrete convex theory from the perspective of supply chain applications. We illustrate some direct applications and connections in supply chain applications. Certain proofs are modified/shortened, to fit into the scope of this chapter.

Constrained submodular maximization (CSM) is widely used in numerous data mining and machine learning applications such as data summarization, network monitoring, exemplar-clustering, and nonparametric learning. The CSM can be described as: Given a ground set, a specified constraint, and a submodular set function defined on the power set of the ground set, the goal is to select a subset that satisfies the constraint such that the function value is maximized. Generally, the CSM is NP-hard, and cardinality constrained submodular maximization is well researched. The greedy algorithm and its variants have good performance guarantees for constrained submodular maximization. When dealing with large input scenario, it is usually formulated as streaming constrained submodular maximization (SCSM), and the classical greedy algorithm is usually inapplicable. The streaming model uses a limited memory to extract a small fraction of items at any given point of time such that the specified constraint is satisfied, and good performance guarantees are also maintained. In this chapter, we list the up-to-date popular algorithms for streaming submodular maximization with cardinality constraint and its variants, and summarize some problems in streaming submodular maximization that are still open.

The nonsubmodular optimization is a hot research topic in the study of nonlinear combinatorial optimizations. We discuss several approaches to deal with such optimization problems, including supermodular degree, curvature, algorithms based on DS decomposition, and sandwich method.

Integer programming in a variable dimension is a crucial research topic that has received a considerable attention in recent years. A series of fixed parameter tractable (FPT) algorithms have been developed for a variety of integer programming that has a special block structure, and such results were later applied successfully in many classical combinatorial optimization problems to derive FPT or approximation algorithms. From a theoretical point of view, it is important to understand the overall landscape, and distinguish the structures of integer programming that are tractable vs. intractable or unknown so far. From the application point of view, it is important to understand how the structure of such integer programming is related to the structure of concrete combinatorial optimization problems. The goal of this survey is to summarize recent progress in theory and application of integer programming that has a block structure and point to important open problems in this research direction.

We survey some recent progress on the design and the analysis of online algorithms for optimization problems with non-linear, usually convex, objectives. We focus on an extension of the online primal dual technique, and highlight its application in a number of applications, including an online matching problem with concave returns, an online scheduling problem with speed-scalable machines subjective to convex power functions, and a family of online covering and packing problems with convex objectives.

With the development of machine learning in various fields, it can also be applied to combinatorial optimization problems, automatically discovering generic and fast heuristic algorithms based on training data, and requires fewer theoretical and empirical knowledge. Pointer network improves the attention mechanism, instead of allocating different attention to hidden states of encoder to generate context vectors, using attention as a pointer to select an element of the input sequence at every step of decoding, which solves the problem of variable dictionary size of the output sequence. Pointer net (Ptr-Net) applied to three combinatorial optimization problems, convex hull, Delaunay triangulation, and traveling salesman problem (TSP), obtains good approximate solutions. Point matching is also a special kind of combinatorial optimization problems that is to obtain the optimal corresponding references, which can be modeled by Ptr-Net. However, Ptr-Net can’t be used to solve point matching problem because it doesn’t take full advantage of the correspondences between the two point sets. We propose multi-pointer network, which draws the idea from multi-label classification, to address this limitation by pointing out a set of input elements. These applications are all based on supervised learning to approximate expected known solutions. However, high-quality labeled data is often expensive, unreliable, or simply unavailable and may be infeasible for new problem statements, making supervised learning being unpractical. Reinforcement learning, as another research hotspot in the field of machine learning, does not require labeled sample data. It interacts with the environment through trial-and-error mechanism and focuses more on learning problem-solving strategies. We introduce a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning, focusing on the traveling salesman problem. We also introduce a framework, a unique combination of reinforcement learning and graph embedding network, to solve graph optimization problems, focusing on maximum cut (MAXCUT) and minimum vertex cover (MVC) problems.

Modeling malware propagation dynamics and developing prevention methods are very imperative with flourishing and advancement of WSN technologies in a variety of fields, such as smart cities. In the last decade, a lot of effort has been put into designing effective models to characterize the propagation dynamics of malware and developing effective prevention methods, with different focuses such as spatial–temporal model, pulse immunization, trade-off model between prevention cost and network utility, etc. This chapter reviews the state-of-the-art malware modeling and prevention method to present a comprehensive guide on how to choose a more appropriate approach for different applications. First, the application background and definitions of WSNs and malware are introduced, followed by the challenges of modeling malware propagation dynamics and developing prevention methods. Second, the recent advances in modeling and prevention methods are summarized. Third, four recently published papers that focus on spatial–temporal modeling, pulse immunization, and cost-efficiency trade-off are introduced. Finally, this chapter is ended by pointing out some possible future research directions.

Influence maximization has been studied extensively in the literature. Its mathematical formulation is a monotone nondecreasing submodular maximization. However, when composed influence is considered, the corresponding problem becomes a nonsubmodular maximization. A composed influence results from a combination of at least two active members in the social network. To study this problem, a hypergraph model is introduced and hence different methodologies are involved.

The friending is a popular and important operation in online social networks. In this article, we discuss various optimization problems about friending. They can be formulated into nonlinear combinatorial optimization problems.

With the rapid growth of online social networks, people change the way of generating, sharing, and spreading various social contents. The contagiousness of social content is highly depending on the size of of seed nodes and connectivity of the network. In this study, we propose the optimization problems of information content diffusion over social networks. The content here can be either useful information such as news, innovation ideas, and marketing purpose content or negative content such as misinformation and malicious rumors. We show that the optimization problem on information diffusion has been discussed in previous researches from different aspects using different approaches. In our study, we formulate two optimization problems—content spread maximization and misinformation minimization—which are both NP-hard and non-submodular. To tackle the difficulty of these problems we sandwich approximation which has data-dependent guarantees.

Influence maximization problem is among the most important topics in the area of social networking, it has attracted a lot of research work. Recently, the influence maximization problem has been extended to practical scenarios. In this chapter, we present one cutting-edge problem named interaction-aware influence maximization, which involves nonsubmodular optimization.

Multi-document summarization deals with finding the core theme presented in multiple documents. This can be done by selecting the important information from the text in the multiple documents. Extractive summarization selects and extracts such sentences which represent the gist of the documents. In this paper, we have surveyed how research in multi-document summarization has evolved from simple sentence-based techniques like sentence position to complex neural network based supervised learning techniques. In recent years, more and more supervised learning methods are proposed to tackle this problem along with some unsupervised approaches described in LSA (Deerwester et al. J Am Soc Inf Sci 41(6): 391–407, 1990) and TextRank (Mihalcea et al. Textrank: Bringing order into text. In: Proceedings of the 2004 conference on empirical methods in natural language processing, 2004). In this chapter, we have proposed an alternative unsupervised method where the problem of multi-document summarization can be viewed as a non-linear combinatorial optimization problem. We have formulated the problem and discussed possible solution to this problem.

When you purchase a product in internet, a recommendation may appear “the customer who buys A may also buy B.” When you purchase both products A and B, another recommendation may appear “the customer who buys A and B may also buy C.” Products A, B, and C are complementary. Both recommendations are established based on historical data and statistical analysis. Here, complementary products are those that tend to be purchased together, for example, iPhone and its accessories, computer and monitor, etc. In this article, we would like to address this issue in viral marketing.