Optimal placement,scheduling, and routing to maximize lifetime in sensor networks

A wireless sensor network is a network consisting of distributed autonomouselectronic devices called sensors. Sensors have limited energy and capabilityfor sensing, data processing, and communicating, but they can collectivelybehave to provide an effective network that monitors an area and transmitinformation to gateway nodes or sinks, either directly or through other sensornodes. In most applications the network must operate for long periods of time,so the available energy resources of the sensors must be managed efficiently. Inthis paper, we first develop a mixed integer linear programming model tomaximize network lifetime by optimally determining locations of sensors andsinks, activity schedules of deployed sensors, and data flow routes from sensorsto sinks over a finite planning horizon subject to coverage, flow conservation,energy consumption, and budget constraints. Unfortunately, it is difficult tosolve this model exactly even for small instances. Therefore, we propose twoapproximate solution methods: a Lagrangean heuristic and a two-stage heuristicin which sensors are deployed and an activity schedule is found in the firststage, whereas sinks are located and sensor-to-sink data flow routes aredetermined in the second stage. Computational experiments performed on varioustest instances indicate that the Lagrangean heuristic is both efficient andaccurate and also outperforms the two-stage heuristic.     

Bilevel optimization applied to strategic pricing in competitive electricity markets

In this paper, we present a bilevel programming formulation for the problem of strategic bidding under uncertainty in a wholesale energy market (WEM), where the economic remuneration of each generator depends on the ability of its own management to submit price and quantity bids. The leader of the bilevel problem consists of one among a group of competing generators and the follower is the electric system operator. The capability of the agent represented by the leader to affect the market price is considered by the model. We propose two solution approaches for this non-convex problem. The first one is a heuristic procedure whose efficiency is confirmed through comparisons with the optimal solutions for some instances of the problem. These optimal solutions are obtained by the second approach proposed, which consists of a mixed integer reformulation of the bilevel model. The heuristic proposed is also compared to standard solvers for nonlinearly constrained optimization problems. The application of the procedures is illustrated in case studies with configurations derived from the Brazilian power system.     

A new exact discrete linear reformulation of the quadratic assignment problem

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.     

An efficient heuristic approach for a multi-period logistics network redesign problem

In this paper, a multi-period logistics network redesign problem arising in the context of strategic supply chain planning is studied. Several aspects of practical relevance are captured, namely, multiple echelons with different types of facilities, product flows between facilities in the same echelon, direct shipments to customers, and facility relocation. A two-phase heuristic approach is proposed to obtain high-quality feasible solutions to the problem, which is initially modeled as a large-scale mixed-integer linear program. In the first phase of the heuristic, a linear programming rounding strategy is applied to find initial values for the binary location variables. The second phase of the heuristic uses local search to correct the initial variable choices when a feasible solution is not identified, or to improve the initial feasible solution when its quality does not meet given criteria. The results of a computational study are reported for randomly generated instances comprising a variety of logistics networks.     

Solving a capacitated hub location problem

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders’ Decomposition approach outperforms the standard Benders’ Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly.     

Natural gas bilevel cash-out problem: Convergence of a penalty function method

This paper studies a special bi-level programming problem that arises from the dealings of a Natural Gas Shipping Company and the Pipeline Operator, with facilities of the latter used by the former. Because of the business relationships between these two actors, the timing and objectives of their decision-making process are different and sometimes even opposed. In order to model that, bi-level programming was traditionally used in previous works. Later, the problem was expanded and theoretically studied to facilitate its solution; this included extension of the upper level objective function, linear reformulation, heuristic approaches, and branch-and-bound techniques. In this paper, we present a linear programming reformulation of the latest version of the model, which is significantly faster to solve when implemented computationally. More importantly, this new formulation makes it easier to analyze the problem theoretically, allowing us to draw some conclusions about the nature of the solution of the modified problem. Numerical results concerning the running time, convergence, and optimal values, are presented and compared to previous reports, showing a significant improvement in speed without actual sacrifice of the solution’s quality.     

Minimizing the sum of a linear and a linear fractional function applying conic quadratic representation: continuous and discrete problems

This paper tries to minimize the sum of a linear and a linear fractional function over a closed convex set defined by some linear and conic quadratic constraints. At first, we represent some necessary and sufficient conditions for the pseudoconvexity of the problem. For each of the conditions, under some reasonable assumptions, an appropriate second-order cone programming (SOCP) reformulation of the problem is stated and a new applicable solution procedure is proposed. Efficiency of the proposed reformulations is demonstrated by numerical experiments. Secondly, we limit our attention to binary variables and derive a sufficient condition for SOCP representability. Using the experimental results on random instances, we show that the proposed conic reformulation is more efficient in comparison with the well-known linearization technique and it produces more eligible cuts for the branch and bound algorithm.     

Telecommunication Link Restoration Planning with Multiple Facility Types

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting (restoring) traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network to permit link restoration of steady-state traffic. We present a planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances that nearly achieve these worst-case bounds. In tests on three real-world problems and numerous randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. However, for small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, and our heuristic solutions are closer to optimality than implied by the gaps.     

A mathematical formulation and complexity considerations for the blocks relocation problem

The blocks relocation problem (BRP) may be defined as follows: given a set of homogeneous blocks stored in a two-dimensional stock, which relocations are necessary to retrieve the blocks from the stock in a predefined order while minimizing the number of those relocations? In this paper, we first prove NP-hardness of the BRP as well as a special case, closing open research questions. Moreover, we propose different solution approaches. First, a mathematical model is presented that provides optimal solutions to the general BRP in cases where instances are small. To overcome such limitation, some realistic assumption taken from the literature is introduced, leading to the definition of a binary linear programming model. In terms of computational time, this approach is reasonably fast to be used to solve medium-sized instances. In addition, we propose a simple heuristic based upon a set of relocation rules. This heuristic is used to generate “good” quality solutions for larger instances in very short computational time, and, consequently, is proposed for tackling problem instances where solutions are required (almost) immediately. Solution quality of the heuristic is measured against optimal solutions obtained using a state-of-the-art commercial solver and both of them are compared with reference results from literature.     

An improved decomposition-based heuristic to design a water distribution network for an irrigation system

In this paper the authors address a pressurized water distribution network design problem for irrigation purposes. Two mixed binary nonlinear programming models are proposed for this NP-hard problem. Furthermore, a heuristic algorithm is presented for the problem, which considers a decomposition sequential scheme, based on linearization of the second model, coupled with constructive and local search procedures designed to achieve improved feasible solutions. To evaluate the robustness of the method we tested it on several instances generated from a real application. The best solutions obtained are finally compared with solutions provided by standard software. These computational experiments enable the authors to conclude that the decomposition sequential heuristic is a good approach to this difficult real problem.     

A penalty function heuristic for the resource constrained shortest path problem

The resource constrained shortest path problem (RCSP) consists of finding the shortest path between two nodes of an assigned network, with the constraint that traversing an arc of the network implies the consumption of certain limited resources. In this paper we propose a new heuristic for the solution of the RCSP problem in medium and large scale networks. It is based on the extension to the discrete case of the penalty function heuristic approach for the fast ε-approximate solution of difficult large-scale continuous linear programming problems. Computational experience on test instances has shown that the proposed penalty function heuristic (PFH) is very effective in the solution of medium and large scale RCSP instances. For all the tests reported it provides very good upper bounds (in many cases the optimal solution) in less than 26 iterations, where each iteration requires only the computation of a shortest path.     

A neural network for the linear complementarity problem

An artificial neural network is proposed in this paper for solving the linear complementarity problem. The new neural network is based on a reformulation of the linear complementarity problem into the unconstrained minimization problem. Our new neural network can be easily implemented on a circuit. On the theoretical aspect, we analyze the existence of the equilibrium points for our neural network. In addition, we prove that if the equilibrium point exists for the neural network, then any such equilibrium point is both asymptotically and bounded (Lagrange) stable for any initial state. Furthermore, linear programming and certain quadratical programming problems (not necessarily convex) can be also solved by the neural network. Simulation results on several problems including a nonconvex one are also reported.     

A single machine scheduling problem with availability constraints and sequence-dependent setup costs

We study a single machine scheduling problem with availability constraints and sequence-dependent setup costs, with the aim of minimizing the makespan. To the authors’ knowledge, this problem has not been treated as such in the operations research literature. We derive in this paper a mixed integer programming model to deal with such scheduling problem. Computational tests showed that commercial solvers are capable of solving only small instances of the problem. Therefore, we propose two ways for reducing the execution time, namely a valid inequality that strengthen the linear relaxation and an efficient heuristic procedure that provides a starting feasible solution to the solver. A substantial gain is achieved both in terms of the linear programming relaxation bound and in terms of the time to obtain an integer optimum when we use the enhanced model in conjunction with providing to the solver the solution obtained by the proposed heuristic.     

考虑泊位疏浚的连续型泊位和动态岸桥联合调度

针对集装箱码头泊位需要定期维护的实际特征,研究了泊位疏浚情况下连续型泊位和动态岸桥联合调度问题。首先,建立了一个以船舶周转时间最小为目标的整数线性规划模型;其次,针对问题特性设计了三种启发式算法。为了分析泊位疏浚对码头工作的影响并验证模型正确性和算法有效性,分别对未考虑泊位疏浚和考虑泊位疏浚两种调度情形,进行了小规模与大规模问题输入的多组测试。三种算法在小规模输入上均取得了相同于CPLEX的精确解,从而验证了算法的有效性;进一步通过对比分析这些算法在大规模输入中的运行结果,验证其有效性能。     

A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints

In this paper we propose a dual ascent heuristic for solving the linear relaxation of the generalized set partitioning problem with convexity constraints, which often models the master problem of a column generation approach. The generalized set partitioning problem contains at the same time set covering, set packing and set partitioning constraints. The proposed dual ascent heuristic is based on a reformulation and it uses Lagrangian relaxation and subgradient method. It is inspired by the dual ascent procedure already proposed in literature, but it is able to deal with right hand side greater than one, together with under and over coverage. To prove its validity, it has been applied to the minimum sum coloring problem, the multi-activity tour scheduling problem, and some newly generated instances. The reported computational results show the effectiveness of the proposed method.     

A piecewise linearization for retail shelf space allocation problem and a local search heuristic

Retail shelf space allocation problem is well known in literature. In this paper, we make three contributions to retail shelf space allocation problem considering space elasticity (SSAPSE). First, we reformulate an existing nonlinear model for SSAPSE to an integer programming (IP) model using piecewise linearization. Second, we show that the linear programming relaxation of the proposed IP model produces tight upper bound. Third, we develop a heuristic that consistently produces near optimal solutions for randomly generated instances of problems with size (products, shelves) varying from (25, 5) to (200, 50) within a minute of CPU time.     

An Augmented Lagrangian Algorithm for Large Scale Multicommodity Routing

The linear multicommodity network flow (MCNF) problem has many applications in the areas of transportation and telecommunications. It has therefore received much attention, and many algorithms that exploit the problem structure have been suggested and implemented. The practical difficulty of solving MCNF models increases fast with respect to the problem size, and especially with respect to the number of commodities. Applications in telecommunications typically lead to instances with huge numbers of commodities, and tackling such instances computationally is challenging.In this paper, we describe and evaluate a fast and convergent lower-bounding procedure which is based on an augmented Lagrangian reformulation of MCNF, that is, a combined Lagrangian relaxation and penalty approach. The algorithm is specially designed for solving very large scale MCNF instances. Compared to a standard Lagrangian relaxation approach, it has more favorable convergence characteristics. To solve the nonlinear augmented Lagrangian subproblem, we apply a disaggregate simplicial decomposition scheme, which fully exploits the structure of the subproblem and has good reoptimization capabilities. Finally, the augmented Lagrangian algorithm can also be used to provide heuristic upper bounds.The efficiency of the augmented Lagrangian method is demonstrated through computational experiments on large scale instances. In particular, it provides near-optimal solutions to instances with over 3,600 nodes, 14,000 arcs and 80,000 commodities within reasonable computing time.     

A GENERATOR AND A SIMPLEX SOLVER FOR NETWORK PIECEWISE LINEAR PROGRAMS

ＡＧＥＮＥＲＡＴＯＲＡＮＤＡＳＩＭＰＬＥＸＳＯＬＶＥＲＦＯＲＮＥＴＷＯＲＫＰＩＥＣＥＷＩＳＥＬＩＮＥＡＲＰＲＯＧＲＡＭＳＳＵＮＪＩＥ（孙捷）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉ...     

Optimization scheme for sensor coverage scheduling with bandwidth constraints

Wireless Sensor Network has attracted a lot of attentions due to its broad applications in recent years and also introduces many challenges. Network lifetime is a critical issue in Wireless Sensor Networks. It is possible to extend network lifetime by organizing the sensors into a number of sensor covers. However, with the limited bandwidth, coverage breach (i.e, targets that are not covered) can occur if the number of available time-slots/channels is less than the number of sensors in a sensor cover. In this paper, we study a joint optimization problem in which the objective is to minimize the coverage breach as well as to maximize the network lifetime. We show a “trade-off” scheme by presenting two strongly related models, which aim to tradeoffs between the two conflicting objectives. The main approach of our models is organizing sensors into non-disjoint sets, which is different from the current most popular approach and can gain longer network lifetime as well as less coverage breach. We proposed two algorithms for the first model based on linear programming and greedy techniques, respectively. Then we transform these algorithms to solve the second model by revealing the strong connection between the models. Through numerical simulation, we showed the good performance of our algorithms and the pictures of the tradeoff scheme in variant scenarios, which coincide with theoretical analysis very well. It is also showed that our algorithms could obtain less breach rate than the one proposed in (Cheng et al. in INFOCOM’ 05, 2005).