In this letter, we investigate the application of the subgradient method to design efficient algorithm for linear programming (LP) decoding of binary linear codes. A major drawback of the original formulation of LP decoding is that the description complexity of the feasible region is exponential in the check node degrees of the code. In order to tackle the problem, we propose a processing technique for LP decoding with the subgradient method, whose complexity is linear in the check node degrees. Consequently, a message-passing type decoding algorithm can be obtained, whose per-iteration complexity is extremely low. Moreover, if the algorithm converges to a valid codeword, it is guaranteed to be a maximum likelihood codeword. Simulation results on several binary linear codes with short lengths suggest that the performances of LP decoding based on the subgradient method and the state-of-art LP decoding implementation approach are comparable.

In Variant 4 of the one-way trading game [El-Yaniv, Fiat, Karp, and Turpin, 2001], a player has one dollar at the beginning and wants to convert it to yen only by one-way conversion. The exchange rate is guaranteed to fluctuate between m and M, and only the maximum fluctuation ratio φ = M/m is informed to the player in advance. The performance of an algorithm for this game is measured by the competitive ratio. El-Yaniv et al. derived the best possible competitive ratio over all algorithms for this game. However, it seems that the behavior of the best possible algorithm itself has not been explicitly described. In this paper we reveal the behavior of the best possible algorithm by solving a linear optimization problem. The behavior turns out to be quite different from that of the best possible algorithm for Variant 2 in which the player knows m and M in advance.

Industrial networks need to provide reliable communication services, usually in a redundant transmission (RT) manner. In the past few years, several device-redundancy-based, layer 2 solutions have been proposed. However, with the evolution of industrial networks to the Industrial Internet, these methods can no longer work properly in the non-redundancy, layer 3 environments. In this paper, an SDN-based reliable communication framework is proposed for the Industrial Internet. It can provide reliable communication guarantees for mission-critical applications while servicing non-critical applications in a best-effort transmission manner. Specifically, it first implements an RT-based reliable communication method using the Industrial Internet's link-redundancy feature. Next, it presents a redundant synchronization mechanism to prevent end systems from receiving duplicate data. Finally, to maximize the number of critical flows in it (an NP-hard problem), two ILP-based routing & scheduling algorithms are also put forward. These two algorithms are optimal (Scheduling with Unconstrained Routing, SUR) and suboptimal (Scheduling with Minimum length Routing, SMR). Numerous simulations are conducted to evaluate its effectiveness. The results show that it can provide reliable, duplicate-free services to end systems. Its reliable communication method performs better than the conventional best-effort transmission method in terms of packet delivery success ratio in layer 3 networks. In addition, its scheduling algorithm, SMR, performs well on the experimental topologies (with average quality of 93% when compared to SUR), and the time overhead is acceptable.

In order to obtain a feasible schedule of a hard real-time system, heuristic based techniques are the solution of choice. In the last few years, optimization solvers have gained attention from research communities due to their capability of handling large number of constraints. Recently, some works have used integer linear programming (ILP) for solving mono processor scheduling of real-time systems. In fact, ILP is commonly used for static scheduling of multiprocessor systems. However, two main solvers are used to solve the problem indistinctly. But, which one is the best for obtaining a schedulable system for hard real-time systems? This paper makes a comparison of two well-known optimization software packages (CPLEX and GUROBI) for the problem of finding a feasible schedule on monoprocessor hard real-time systems.

This paper presents a novel method for optimal control of timed Petri nets, introducing a novel temporal logic based constraint called a generalized mutual exclusion temporal constraint (GMETC). The GMETC is described by a metric temporal logic (MTL) formula where each atomic proposition represents a generalized mutual exclusion constraint (GMEC). We formulate an optimal control problem of the timed Petri nets under a given GMETC and solve the problem by transforming it into an integer linear programming problem where the MTL formula is encoded by linear inequalities. We show the effectiveness of the proposed approach by a numerical simulation.

One of the features of a software-defined network (SDN) is a logically centralized control plane hosting one or more SDN controllers. As SDN controller placement can impact network performance, it is widely studied as the controller placement problem (CPP). For a cost-effective network design, network providers need to minimize the number of SDN controllers used in the network since each SDN controller incurs installation and maintenance costs. Moreover, the network providers need to deal with the failure of SDN controllers. Existing studies that consider SDN controller failures use the scheme of connecting each SDN switch to one Master controller and one or more Slave controllers. The problem with this scheme is that the computing capacity of each SDN controller cannot be used efficiently since one SDN controller handles the load of all SDN switches connected to it. The number of SDN controllers required can be reduced by distributing the load of each SDN switch among multiple SDN controllers. This paper proposes a controller placement model that allows the distribution against SDN controller failures. The proposed model determines the ratios of computing capacity demanded by each SDN switch on the SDN controllers connected to it. The proposed model also determines the number and placement of SDN controllers and the assignment of each SDN switch to SDN controllers. Controller placement is determined so that a network provider can continue to manage all SDN switches if no more than a certain number of SDN controller failures occur. We develop two load distribution methods: split and even-split. We formulate the proposed model with each method as integer linear programming problems. Numerical results show that the proposed model reduces the number of SDN controllers compared to a benchmark model; the maximum reduction ratio is 38.8% when the system latency requirement between an SDN switch and an SDN controller is 100[ms], the computing capacity of each SDN controller is 6 × 106[packets/s], and the maximum number of SDN controllers that can fail at the same time is one.

With the demand for energy-efficient and high- performance computing, multicore architecture has become more appealing than ever. Multicore task scheduling is one of domains in parallel computing which exploits the parallelism of multicore. Unlike traditional scheduling, multicore task scheduling has recently been studied on the assumption that tasks have inherent parallelism and can be split into multiple sub-tasks in data parallel fashion. However, it is still challenging to properly determine the degree of parallelism of tasks and mapping on multicores. Our proposed scheduling techniques determine the degree of parallelism of tasks, and sub-tasks are decided which type of cores to be assigned to heterogeneous multicores. In addition, two approaches to hardware/software codesign for heterogeneous multicore systems are proposed. The works optimize the types of cores organized in the architecture simultaneously with scheduling of the tasks such that the overall energy consumption is minimized under a deadline constraint, a warm start approach is also presented to effectively solve the problem. The experimental results show the simultaneous scheduling and core-type optimization technique remarkably reduces the energy consumption.

Recent trends in designing filters involve development of sparse filters with coefficients that not only have real but also zero values. These sparse filters can achieve a high performance through optimizing the selection of the zero coefficients and computing the real (non-zero) coefficients. Designing an infinite impulse response (IIR) sparse filter is more challenging than designing a finite impulse response (FIR) sparse filter. Therefore, studies on the design of IIR sparse filters have been rare. In this study, we consider IIR filters whose coefficients involve zero value, called sparse IIR filter. First, we formulate the design problem as a linear programing problem without imposing any stability condition. Subsequently, we reformulate the design problem by altering the error function and prepare several possible denominator polynomials with stable poles. Finally, by incorporating these methods into successive thinning algorithms, we develop a new design algorithm for the filters. To demonstrate the effectiveness of the proposed method, its performance is compared with that of other existing methods.

The Software-defined network (SDN) uses a centralized SDN controller to store flow entries in the flow table of each SDN switch; the entries in the switch control packet flows. When a multicast service is provided in an SDN, the SDN controller stores a multicast entry dedicated for a multicast group in each SDN switch. Due to the limited capacity of each flow table, the number of flow entries required to set up a multicast tree must be suppressed. A conventional multicast routing scheme suppresses the number of multicast entries in one multicast tree by replacing some of them with unicast entries. However, since the conventional scheme individually determines a multicast tree for each request, unicast entries dedicated to the same receiver are distributed to various SDN switches if there are multiple multicast service requests. Therefore, further reduction in the number of flow entries is still possible. In this paper, we propose a multicast routing model for multiple multicast requests that minimizes the number of flow entries. This model determines multiple multicast trees simultaneously so that a unicast entry dedicated to the same receiver and stored in the same SDN switch is shared by multicast trees. We formulate the proposed model as an integer linear programming (ILP) problem. In addition, we develop a heuristic algorithm which can be used when the ILP problem cannot be solved in practical time. Numerical results show that the proposed model reduces the required number of flow entries compared to two benchmark models; the maximum reduction ratio is 49.3% when the number of multicast requests is 40.

Metabolic networks represent the relationship between chemical reactions and compounds in cells. In useful metabolite production using microorganisms, it is often required to calculate reaction deletion strategies from the original network to result in growth coupling, which means the target metabolite production and cell growth are simultaneously achieved. Although simple elementary flux mode (EFM)-based methods are useful for listing such reaction deletions strategies, the number of cases to be considered is often proportional to the exponential function of the size of the network. Therefore, it is desirable to develop methods of narrowing down the number of reaction deletion strategy candidates. In this study, the author introduces the idea of L1 norm minimal modes to consider metabolic flows whose L1 norms are minimal to satisfy certain criteria on growth and production, and developed a fast metabolic design listing algorithm based on it (minL1-FMDL), which works in polynomial time. Computational experiments were conducted for (1) a relatively small network to compare the performance of minL1-FMDL with that of the simple EFM-based method and (2) a genome-scale network to verify the scalability of minL1-FMDL. In the computational experiments, it was seen that the average value of the target metabolite production rates of minL1-FMDL was higher than that of the simple EFM-based method, and the computation time of minL1-FMDL was fast enough even for genome-scale networks. The developed software, minL1-FMDL, implemented in MATLAB, is available on https://sunflower.kuicr.kyoto-u.ac.jp/~tamura/software, and can be used for genome-scale metabolic network design for metabolite production.

For low-density parity-check (LDPC) codes, the penalized decoding method based on the alternating direction method of multipliers (ADMM) can improve the decoding performance at low signal-to-noise ratios and also has low decoding complexity. There are three effective methods that could increase the ADMM penalized decoding speed, which are reducing the number of Euclidean projections in ADMM penalized decoding, designing an effective penalty function and selecting an appropriate layered scheduling strategy for message transmission. In order to further increase the ADMM penalized decoding speed, through reducing the number of Euclidean projections and using the vertical layered scheduling strategy, this paper designs a fast converging ADMM penalized decoding method based on the improved penalty function. Simulation results show that the proposed method not only improves the decoding performance but also reduces the average number of iterations and the average decoding time.

The machine-to-machine (M2M) service network platform that accommodates and controls various types of Internet of Things devices has been presented. This paper investigates program file placement strategies for the M2M service network platform that achieve low blocking ratios of new task requests and accommodate as many tasks as possible in the dynamic scenario. We present four strategies for determining program file placement, which differ in the computation method and whether the relocation of program files being used by existing tasks is allowed or not. Simulation results show that a strategy based on solving a mixed-integer linear programming model achieves the lowest blocking ratio, but a heuristic algorithm-based strategy can be an attractive option by allowing recomputation of the placement when the placement cannot be obtained at the timing of new task request arrival.

This paper proposes a Petri net based mathematical programming approach to combinatorial optimization, in which we generate integer linear programming problems from Petri net models instead of the direct mathematical formulation. We treat two types of combinatorial optimization problems, ordinary problems and time-dependent problems. Firstly, we present autonomous Petri net modeling for ordinary optimization problems, where we obtain fundamental constraints derived from Petri net properties and additional problem-specific ones. Secondly, we propose a colored timed Petri net modeling approach to time-dependent problems, where we generate variables and constraints for time management and for resolving conflicts. Our Petri net approach can drastically reduce the difficulty of the mathematical formulation in a sense that (1) the Petri net modeling does not require deep knowledge of mathematical programming and technique of integer linear model formulations, (2) our automatic formulation allows us to generate large size of integer linear programming problems, and (3) the Petri net modeling approach is flexible for input parameter changes of the original problem.

The separating redundancy is an important property in the analysis of the error-and-erasure decoding of a linear block code. In this work, we investigate the separating redundancy of the duals of first-order generalized Reed-Muller (GRM) codes, a class of nonbinary linear block codes that have nice algebraic properties. The dual of a first-order GRM code can be specified by two positive integers m and q and denoted by R(m,q), where q is the power of a prime number and q≠2. We determine the first separating redundancy value of R(m,q) for any m and q. We also determine the second separating redundancy values of R(m,q) for any q and m=1 and 2. For m≥3, we set up a binary integer linear programming problem, the optimum of which gives a lower bound on the second separating redundancy of R(m,q).

This paper shows an optimal spreading sequence in the Weyl sequence class, which is similar to the set of the Oppermann sequences for asynchronous CDMA systems. Sequences in Weyl sequence class have the desired property that the order of cross-correlation is low. Therefore, sequences in the Weyl sequence class are expected to minimize the inter-symbol interference. We evaluate the upper bound of cross-correlation and odd cross-correlation of spreading sequences in the Weyl sequence class and construct the optimization problem: minimize the upper bound of the absolute values of cross-correlation and odd cross-correlation. Since our optimization problem is convex, we can derive the optimal spreading sequences as the global solution of the problem. We show their signal to interference plus noise ratio (SINR) in a special case. From this result, we propose how the initial elements are assigned, that is, how spreading sequences are assigned to each users. In an asynchronous CDMA system, we also numerically compare our spreading sequences with other ones, the Gold codes, the Oppermann sequences, the optimal Chebyshev spreading sequences and the SP sequences in Bit Error Rate. Our spreading sequence, which yields the global solution, has the highest performance among the other spreading sequences tested.

Cost-effective cloud storage services are attracting users with their convenience, but there is a trade-off between service availability and usage cost. We develop two cloud provider selection models for cloud storage services to minimize the total cost of usage. The models select multiple cloud providers to meet the user requirements while considering unavailability. The first model, called a user-copy (UC) model, allows the selection of multiple cloud providers, where the user copies its data to multiple providers. In addition to the user copy function of the UC model, the second model, which is called a user and cloud-provider copy (UCC) model, allows cloud providers to make copies of the data to deliver them to other cloud providers. The cloud service is available if at least one cloud provider is available. We formulate both models as integer linear programming (ILP) problems. Our performance evaluation observes that both models reduce the total cost of usage, compared to the single cloud provider selection approach. As the cost of bandwidth usage between a user and a cloud provider increases, the UCC model becomes more beneficial than the UC model. We implement the prototype for cloud storage services, and demonstrate our models via Science Information Network 5.

Task mapping is one of the most important design processes in embedded manycore systems. This paper proposes a static task mapping technique for manycore real-time systems. The technique minimizes the number of cores while satisfying deadline constraints of individual tasks.

Task scheduling is one of the most important processes in the design of multicore computing systems. This paper presents a technique for scheduling of malleable tasks. Our scheduling technique decides not only the execution order of the tasks but also the number of cores assigned to the individual tasks, simultaneously. We formulate the scheduling problem as an integer linear programming (ILP) problem, and the optimal schedule can be obtained by solving the ILP problem. Experiments using a standard task-set suite clarify the strength of this work.

In this paper, the authors propose an integer linear programming (ILP) model for static multi-car elevator operation problems. Here, “static” means that all information which make the behavior of the elevator system indeterministic is known before scheduling. The proposed model is based on the trip-based ILP model for static single-car elevator operation problems. A trip of an elevator is a one-directional movement of that elevator, which is labaled upward or downward. In the trip-based ILP model, an elevator trajectory is scheduled according to decision variables which determine allocations of trips to users of an elevator system. That model has such an advantage that the difficulty in solving ILP formulations resulted by that model does not depend on the length of the planning horizon nor the height of the considered building, thus is effective when elevator trajectories are simple. Moreover, that model has many variables relevant to elevators' positions. The proposed model is resulted by adding 3 constraints which are basically based on those variables and make it possible to prevent elevators in a same shaft from interfering. The first constraint simply imposes the first and last floors of an upper trip to be above those of its lower trip. The second constraint imagines the crossing point between upper and lower trips and imposes it ahead of or behind the lower trip according to their directions. The last constraint estimates future positions of elevators and imposes the upper trip to be above floors of passengers on the lower trip. The basic validity of the proposed model is displayed by solving 90 problem instances and examining elevator trajectories generated from them, then comparing objective function values of elevator trajectories on a multi-car elevator system with those on single-car elevator systems.

In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linear programming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance dfp of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to ⌈dfp/2⌉-1 errors.