Uplink scheduling for joint wireless orthogonal frequency and time division multiple access networks

In this paper, we present a deterministic resource allocation model for a hybrid uplink wireless orthogonal frequency and time division multiple access network. Since the input data of the model may be affected by uncertainty, we further consider a stochastic formulation of the problem which we transform into an equivalent deterministic binary second-order conic program (SOCP). Subsequently, we use this binary SOCP to derive an equivalent integer linear programming formulation. The proposed models are aimed at maximizing the total bandwidth channel capacity subject to user power and sub-carrier assignment constraints while simultaneously scheduling users in time. As such, the models are best suited for non-real-time applications where sub-channel multiuser diversity can be further exploited simultaneously in frequency and time domains. Finally, in view of the large execution times required by CPLEX to solve the proposed models, we propose a variable neighborhood search metaheuristic procedure. Our numerical results show tight bounds and near optimal solutions for most of the instances when compared to the optimal solution of the problem. Moreover, we obtain better feasible solutions than CPLEX in the stochastic case. Finally, these bounds are obtained at a very low computational cost.     

Semidefinite relaxation for linear programs with equilibrium constraints

In this paper, we present a semidefinite programming (SDP) relaxation for linear programs with equilibrium constraints (LPECs) to be used in a branch‐and‐bound (B&B) algorithm. The procedure utilizes the global optimal solution of LPECs and was motivated by the B&B algorithm proposed by Bard and Moore for linear/quadratic bilevel programs, where complementarities are recursively enforced. We propose the use of the SDP relaxation to generate bounds at the nodes of the B&B tree. Computational results compare the quality of the bounds given by the SDP relaxation with the ones given by conventional linear programming relaxations.     

A note on “event-based MILP models for resource-constrained project scheduling problems”

Recently, new mixed integer linear programming formulations for the resource-constrained project scheduling problem were proposed by Koné et al. [3]. Unfortunately, the presentation of the first new model (called start/end-based formulation SEE) was not correct. More precisely, a set of necessary constraints representing the relative positioning of start and end events of activities was unintentionally omitted in the paper although it was present in the integer program used for the computational experiments. After presenting a counterexample showing the incorrectness, we provide a disaggregated and an aggregated variant of the set of necessary constraints, the disaggregated formulation yielding in theory a better linear programming relaxation. We present computational results showing that although the linear programming relaxations of both formulations yield equivalently poor lower bounds, the disaggregated formulation shows in average a better performance for integer solving of a well-known set of 30-activity instances.     

Bi-objective optimisation model for installation scheduling in offshore wind farms

A bi-objective optimisation using a compromise programming approach is proposed for installation scheduling of an offshore wind farm. As the installation cost and the completion period of the installation are important aspects in the construction of an offshore wind farm, the proposed method is used to deal with those conflicting objectives. We develop a mathematical model using integer linear programming (ILP) to determine the optimal installation schedule considering several constraints such as weather condition and the availability of vessels. We suggest two approaches to deal with the multi-objective installation scheduling problem, namely compromise programming with exact method and with metaheuristic techniques. In the exact method the problem is solved by CPLEX whereas in the metaheuristic approach we propose Variable Neighbourhood Search (VNS) and Simulated Annealing (SA). Moreover, greedy algorithms and a local search for solving the scheduling problem are introduced. Two generated datasets are used for testing our approaches. The computational experiments show that the proposed metaheuristic approaches produce interesting results as the optimal solution for some cases is obtained.     

On semidefinite programming bounds for graph bandwidth

In this paper, we propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds reported in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoret. Comput. Sci. 235(1) (2000), pp. 25–42; J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM J. Optim. 18(1) (2007), pp. 223–241].     

Binary partitioning, perceptual grouping, and restoration with semidefinite programming

We introduce a novel optimization method based on semidefinite programming relaxations to the field of computer vision and apply it to the combinatorial problem of minimizing quadratic functionals in binary decision variables subject to linear constraints. The approach is (tuning) parameter-free and computes high-quality combinatorial solutions using interior-point methods (convex programming) and a randomized hyperplane technique. Apart from a symmetry condition, no assumptions (such as metric pairwise interactions) are made with respect to the objective criterion. As a consequence, the approach can be applied to a wide range of problems. Applications to unsupervised partitioning, figure-ground discrimination, and binary restoration are presented along with extensive ground-truth experiments. From the viewpoint of relaxation of the underlying combinatorial problem, we show the superiority of our approach to relaxations based on spectral graph theory and prove performance bounds.     

A branch-and-cluster coordination scheme for selecting prison facility sites under uncertainty

A multi-period stochastic model and an algorithmic approach to location of prison facilities under uncertainty are presented and applied to the Chilean prison system. The problem consists of finding locations and sizes of a preset number of new jails and determining where and when to increase the capacity of both new and existing facilities over a time horizon, while minimizing the expected costs of the prison system. Constraints include maximum inmate transfer distances, upper and lower bounds for facility capacities, and scheduling of facility openings and expansion, among others. The uncertainty lies in the future demand for capacity, because of the long time horizon under study and because of the changes in criminal laws, which could strongly modify the historical tendencies of penal population growth. Uncertainty comes from the effects of penal reform in the capacity demand. It is represented in the model through probabilistic scenarios, and the large-scale model is solved via a heuristic mixture of branch-and-fix coordination and branch-and-bound schemes to satisfy the constraints in all scenarios, the so-called branch-and-cluster coordination scheme. We discuss computational experience and compare the results obtained for the minimum expected cost and average scenario strategies. Our results demonstrate that the minimum expected cost solution leads to better solutions than does the average scenario approach. Additionally, the results show that the stochastic algorithmic approach that we propose outperforms the plain use of a state-of-the-art optimization engine, at least for the three versions of the real-life case that have been tested by us.     

Verification and control of partially observable probabilistic systems

We present automated techniques for the verification and control of partially observable, probabilistic systems for both discrete and dense models of time. For the discrete-time case, we formally model these systems using partially observable Markov decision processes; for dense time, we propose an extension of probabilistic timed automata in which local states are partially visible to an observer or controller. We give probabilistic temporal logics that can express a range of quantitative properties of these models, relating to the probability of an event’s occurrence or the expected value of a reward measure. We then propose techniques to either verify that such a property holds or synthesise a controller for the model which makes it true. Our approach is based on a grid-based abstraction of the uncountable belief space induced by partial observability and, for dense-time models, an integer discretisation of real-time behaviour. The former is necessarily approximate since the underlying problem is undecidable, however we show how both lower and upper bounds on numerical results can be generated. We illustrate the effectiveness of the approach by implementing it in the PRISM model checker and applying it to several case studies from the domains of task and network scheduling, computer security and planning.     

Rematch: a highly reliable scheduling algorithm on heterogeneous wireless mesh network

In highly dynamic and heterogeneous wireless mesh networks (WMN), link quality will seriously affect network performance. Two challenges hinder us from achieving a highly efficient WMN. One is the channel dynamics. As in real network deployment, channel qualities are changing over time, which would seriously affect network bandwidth and reliability. Existing works are limited to the assumption that link quality values are fixed, and optimal scheduling algorithms are working on the fixed values, which would inevitably suffer from the link quality dynamics. Another challenge is the channel diversity. In single channel wireless networks, channel assignment and scheduling are NP\mathcal{NP} -hard. And in multichannel wireless networks, it could be even harder for higher throughput and efficient scheduling. In this study, we firstly characterize the stochastic behavior on wireless communications in a Markov process, which is based on statistical methodology. Secondly, on exploiting the stochastic behavior on wireless channels, we propose a stochastic programming model in achieving maximized network utilization. Considering the NP\mathcal{NP} -hardness, we propose a heuristic solution for it. The key idea in the proposed algorithm is a two-stage matching process named “Rematch.” Indeed, our solution to the stochastic network scheduling is a cross-layer approach. Also, we have proved that it is 2-approximate to the optimal result. Moreover, extensive simulations have been done, showing the efficiency of “Rematch” in highly dynamic and distributed wireless mesh networks.     

间歇生产调度优化模型的分周期逼近算法

间歇生产调度过程中存在许多不确定因素,其中最重要的是需求不确定.考虑需求不确定的多周期间歇生产调度优化模型采用离散或连续时间表达方式,将调度时间域分割成大量与调度决策相关的时间段,导致模型中存在大量整数变量,给模型求解造成很大困难.本研究对已有求解方法进行了分析,提出分周期逼近算法.将多周期间歇生产调度决策问题分解为第一周期调度决策问题和其余周期调度决策问题,简化结构,加快求解速度.通过方案树聚集将表达需求不确定信息的方案树转化成若干方案文件,针对每个方案文件应用确定性方法获得调度决策,但只保留第一周期调度决策,可以减小最小利益方案对期望利益的影响,提高第一周期调度决策水平;获得若干第一周期候选调度决策后,以时间收缩三阶段方法确定其余周期较优调度决策,同时应用时间收缩策略和补偿策略,提高其余周期调度决策水平;最后用期望利益评估第一周期候选调度决策并确定全部周期调度决策.实例研究证明了本文提出的算法能够提高间歇生产调度决策水平,同时加快求解速度,能够有效求解多周期间歇生产调度优化模型.     

Models and Algorithms for Integration of Vehicle and Crew Scheduling

This paper deals with models, relaxations, and algorithms for an integrated approach to vehicle and crew scheduling for an urban mass transit system with a single depot. We discuss potential benefits of integration and provide an overview of the literature which considers mainly partial integration. Our approach is new in the sense that we can tackle integrated vehicle and crew scheduling problems of practical size.We propose new mathematical formulations for integrated vehicle and crew scheduling problems and we discuss corresponding Lagrangian relaxations and Lagrangian heuristics. To solve the Lagrangian relaxations, we use column generation applied to set partitioning type of models. The paper is concluded with a computational study using real life data, which shows the applicability of the proposed techniques to practical problems. Furthermore, we also address the effectiveness of integration in different situations.     

Optimization-based scheduling for the single-satellite,multi-ground station communication problem

In this paper, we develop models and algorithms for solving the single-satellite, multi-ground station communication scheduling problem, with the objective of maximizing the total amount of data downloaded from space. With the growing number of small satellites gathering large quantities of data in space and seeking to download this data to a capacity-constrained ground station network, effective scheduling is critical to mission success. Our goal in this research is to develop tools that yield high-quality schedules in a timely fashion while accurately modeling on-board satellite energy and data dynamics as well as realistic constraints of the space environment and ground network. We formulate an under-constrained mixed integer program (MIP) to model the problem. We then introduce an iterative algorithm that progressively tightens the constraints of this model to obtain a feasible and thus optimal solution. Computational experiments are conducted on diverse real-world data sets to demonstrate tractability and solution quality. Additional experiments on a broad test bed of contrived problem instances are used to test the boundaries of tractability for applying this approach to other problem domains. Our computational results suggest that our approach is viable for real-world instances, as well as providing a strong foundation for more complex problems with multiple satellites and stochastic conditions.     

Robust semidefinite relaxations for a quadratic OFDMA resource allocation scheme

This paper proposes two robust binary quadratically constrained quadratic programs (BQCQP) for wireless Orthogonal Frequency Division Multiple Access (OFDMA) networks. The first one is based on a scenario uncertainty approach from Kouvelis and Yu [1] and the second is based on an interval uncertainty approach from Bertsimas and Sim [2]. Both robust models allow to decide what modulations and what sub-carriers are going to be used by a particular user in the system depending on its bit rate requirements. Thus, we derive two robust semidefinite relaxations to compute lower bounds. Our numerical results show, in average near optimal integrality gaps of 4.12% and 1.15% under the scenario and interval approach when compared to the optimal solution of the problem derived by linearizing the two quadratic models with Fortet linearization method. Some comparison between the two robust approaches is also provided.     

基于二阶段随机规划的回收物流网络优化设计研究

针对含有连续分布随机参数的回收物流网络优化设计问题,结合抽样理论,建立了由样本数量决定求解效率的二阶段随机规划模型.指出适量小样本对应的模型最优值必然是实际最优值的下界,提出了基于大样本分析的物流网络稳健性评价方法以及实际最优值上界的确定方法.给出模型求解的混合遗传算法,并总结了物流网络的优化设计步骤.通过具体算例说明了模型及其算法在设计决策中的应用.     

Probabilistic tubes in linear stochastic model predictive control

This paper considers constrained control of linear systems with additive and multiplicative stochastic uncertainty and linear input/state constraints. Both hard and soft constraints are considered, and bounds are imposed on the probability of soft constraint violation. Assuming the plant parameters to be finitely supported, a method of constraint handling is proposed in which a sequence of tubes, corresponding to a sequence of confidence levels on the predicted future plant state, is constructed online around nominal state trajectories. A set of linear constraints is derived by imposing bounds on the probability of constraint violation at each point on an infinite prediction horizon through constraints on one-step-ahead predictions. A guarantee of the recursive feasibility of the online optimization ensures that the closed loop system trajectories satisfy both the hard and probabilistic soft constraints. The approach is illustrated by a numerical example.     

Parametrized model reduction based on semidefinite programming

A parametrized model in addition to the control and state-space variables depends on time-independent design parameters, which essentially define a family of models. The goal of parametrized model reduction is to approximate this family of models. In this paper, a reduction method for linear time-invariant (LTI) parametrized models is presented, which constitutes the development of a recently proposed reduction approach. Reduced order models are computed based on the finite number of frequency response samples of the full order model. This method uses a semidefinite relaxation, while enforcing stability on the reduced order model for all values of parameters of interest. As a main theoretical statement, the relaxation gap (the ratio between upper and lower bounds) is derived, which validates the relaxation. The proposed method is flexible in adding extra constraints (e.g., passivity can be enforced on reduced order models) and modifying the objective function (e.g., frequency weights can be added to the minimization criterion). The performance of the method is validated on a numerical example.     

A modified ant colony system for finding the expected shortest path in networks with variable arc lengths and probabilistic nodes

The problem of finding the expected shortest path in stochastic networks, where the presence of each node is probabilistic and the arc lengths are random variables, have numerous applications, especially in communication networks. The problem being NP-hard we use an ant colony system (ACS) to propose a metaheuristic algorithm for finding the expected shortest path. A new local heuristic is formulated for the proposed algorithm to consider the probabilistic nodes. The arc lengths are randomly generated based on the arc length distribution functions. Examples are worked out to illustrate the applicability of the proposed approach.     

A convex relaxation approach to set-membership identification of LPV systems

Identification of linear parameter varying models is considered in this paper, under the assumption that both the output and the scheduling parameter measurements are affected by bounded noise. First, the problem of computing parameter uncertainty intervals is formulated in terms of nonconvex optimization. Then, on the basis of the analysis of the regressor structure, we present an ad hoc convex relaxation scheme for computing parameter bounds by means of semidefinite optimization.     

A probabilistic model for bounded elasticity tensor random fields with application to polycrystalline microstructures

In this paper, we address the construction of a prior stochastic model for non-Gaussian deterministically-bounded positive-definite matrix-valued random fields in the context of mesoscale modeling of heterogeneous elastic microstructures. We first introduce the micromechanical framework and recall, in particular, Huet’s Partition Theorem. Based on the latter, we discuss the nature of hierarchical bounds and define, under some given assumptions, deterministic bounds for the apparent elasticity tensor. Having recourse to the Maximum Entropy Principle under the constraints defined by the available information, we then introduce two random matrix models. It is shown that an alternative formulation of the boundedness constraints further allows constructing a probabilistic model for deterministically-bounded positive-definite matrix-valued random fields. Such a construction is presented and relies on a class of random fields previously defined. We finally exemplify the overall methodology considering an experimental database obtained from EBSD measurements and provide a simple numerical application.