We extend recent work on nonlinear optimal control problems with integer restrictions on some of the control functions (mixed-integer optimal control problems, MIOCP). We improve a theorem (Sager et al. in Math Progra...
详细信息
We extend recent work on nonlinear optimal control problems with integer restrictions on some of the control functions (mixed-integer optimal control problems, MIOCP). We improve a theorem (Sager et al. in Math Program 118(1): 109-149, 2009) that states that the solution of a relaxed and convexified problem can be approximated with arbitrary precision by a solution fulfilling the integer requirements. Unlike in previous publications the new proof avoids the usage of the Krein-Milman theorem, which is undesirable as it only states the existence of a solution that may switch infinitely often. We present a constructive way to obtain an integer solution with a guaranteed bound on the performance loss in polynomial time. We prove that this bound depends linearly on the control discretization grid. A numerical benchmark example illustrates the procedure. As a byproduct, we obtain an estimate of the Hausdorff distance between reachable sets. We improve the approximation order to linear grid size instead of the previously known result with order (Hackl in Reachable sets, control sets and their computation, augsburger mathematisch-naturwissenschaftliche schriften. Dr. Bernd Winer, Augsburg, 1996). We are able to include a Special Ordered Set condition which will allow for a transfer of the results to a more general, multi-dimensional and nonlinear case compared to the Theorems in Pietrus and Veliov in (Syst Control Lett 58:395-399, 2009).
We present a wide-area, multiflow ad-hoc network model leveraging information-theoretic rate control, emphasizing interfering rather than colliding transmissions. We seek to allocate resources in this network by optim...
详细信息
We present a wide-area, multiflow ad-hoc network model leveraging information-theoretic rate control, emphasizing interfering rather than colliding transmissions. We seek to allocate resources in this network by optimizing scheduling, routing and power control to solve the max-min throughput problem for all flows involved. In general, our time-slotted, fully-interfering model leads to an NP-hard problem. Further, the rate-control element of the mixed-integer program results in a non-convex problem in the continuous domain. The complexity of the joint problem makes an optimal solution prohibitively difficult to find, leading us to propose a two-pronged approach to determine a near-optimal resource allocation. First, we propose a novel decomposition technique, breaking the joint problem into a sequence of more tractable subproblems. Second, we present a data structure serving multiple purposes: it compactly represents network conditions as they evolve with time, and also serves as the basis for our cubic-time dynamic programming algorithms used to solve and catalog the subproblems. The result is a schedule, route, and power allocation for all data frames involved. We demonstrate the performance of our techniques on the max-min throughput problem, while also showing that they are sufficiently general to apply to a wide variety of optimality criteria in which decisions over transmission schedules and packet routing must be made.
The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristi...
详细信息
The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast. (C) 2011 Elsevier Ltd. All rights reserved.
The NP-hard problem of scheduling jobs on unrelated parallel machines, in the presence of machine-dependent and sequence-dependent setup times, with the objective of minimizing the makespan, is considered. A variable ...
详细信息
The NP-hard problem of scheduling jobs on unrelated parallel machines, in the presence of machine-dependent and sequence-dependent setup times, with the objective of minimizing the makespan, is considered. A variable neighborhood descent search algorithm, hybridized with mathematical programming elements, is presented and its performance is evaluated on a large set of benchmark problem instances. The extensive computational experiments show that the proposed algorithm outperforms previously proposed methods in terms of solution quality as well as computation time.
In this paper, the problem of maximizing the median of a convex combination of vectors having important applications in finance is considered. The objective function is a highly nonlinear, nondifferentiable function w...
详细信息
In this paper, the problem of maximizing the median of a convex combination of vectors having important applications in finance is considered. The objective function is a highly nonlinear, nondifferentiable function with many local minima and the problem was shown to be APX hard. We present two hybrid Large Neighborhood Search algorithms that are based on mixed-integer programs and include a time limit for their running times. We have tested the algorithms on three testbeds and showed their superiority compared to other state-of-the-art heuristics for the considered problem. Furthermore, we achieved a significant reduction in running time for large instances compared to solving it exactly while retaining high quality of the solutions returned. (C) 2012 Elsevier Ltd. All rights reserved.
Resources in cognitive radio networks (CRNs) should dynamically be allocated according to the sensed radio environment. Although some work has been done for dynamic resource allocation in CRNs, many works assume that ...
详细信息
Resources in cognitive radio networks (CRNs) should dynamically be allocated according to the sensed radio environment. Although some work has been done for dynamic resource allocation in CRNs, many works assume that the radio environment can perfectly be sensed. However, in practice, it is difficult for the secondary network to have the perfect knowledge of a dynamic radio environment in CRNs. In this paper, we study the dynamic resource allocation problem for heterogeneous services in CRNs with imperfect channel sensing. We formulate the power and channel allocation problem as a mixed-integer programming problem under constraints. The computational complexity is enormous to solve the problem. To reduce the computational complexity, we tackle this problem in two steps. First, we solve the optimal power allocation problem using the Lagrangian dual method under the assumption of known channel allocation. Next, we solve the joint power and channel allocation problem using the discrete stochastic optimization method, which has low computational complexity and fast convergence to approximate to the optimal solution. Another advantage of this method is that it can track the changing radio environment to dynamically allocate the resources. Simulation results are presented to demonstrate the effectiveness of the proposed scheme.
This paper analyzes the problem of maximizing the disconnectivity of undirected graphs by deleting a subset of their nodes. We consider three metrics that measure the connectivity of a graph: the number of connected c...
详细信息
This paper analyzes the problem of maximizing the disconnectivity of undirected graphs by deleting a subset of their nodes. We consider three metrics that measure the connectivity of a graph: the number of connected components (which we attempt to maximize), the largest component size (which we attempt to minimize), and the minimum cost required to reconnect the graph after the nodes are deleted (which we attempt to maximize). We formulate each problem as a mixed-integer program, and then study valid inequalities for the first two connectivity objectives by examining intermediate dynamic programming solutions to k-hole subgraphs. We randomly generate a set of test instances, on which we demonstrate the computational efficacy of our approaches. Published by Elsevier B.V.
This paper is concerned with the problem of relay assignment in cooperative wireless networks having multiple sources, multiple relays, and a single destination. With the objective of maximizing the minimum capacity a...
详细信息
This paper is concerned with the problem of relay assignment in cooperative wireless networks having multiple sources, multiple relays, and a single destination. With the objective of maximizing the minimum capacity among all sources in the network, a mixed-integer linear programming (MILP) problem is formulated, which can be solved by standard branch-and-bound algorithms. To reduce computational complexity, a greedy solution in the form of a lexicographic bottleneck assignment algorithm is proposed. Simulation results obtained for the IEEE 802.16j uplink scenarios show that the greedy algorithm performs very close to the optimal solution but at a much lower computational cost. The proposed greedy solution can also be tailored to provide further improvements on other network performance criteria.
We express a general mixed-integer programming (MIP) scheduling model in state-space form, and show how common scheduling disruptions, which lead to rescheduling, can be modeled as disturbances in the state-space mode...
详细信息
We express a general mixed-integer programming (MIP) scheduling model in state-space form, and show how common scheduling disruptions, which lead to rescheduling, can be modeled as disturbances in the state-space model. We also discuss how a wide range of scheduling models, with different types of decisions and processing constraints, can be expressed in state-space form. The proposed framework offers a natural representation of dynamic systems, thereby enabling researchers in the chemical process control area to study scheduling problems. It also facilitates the application of known results for hybrid systems, as well as the development of new tools necessary to address scheduling applications. We hope that it will lead to the development of scheduling solution methods with desired closed-loop properties, a topic that has received no attention in the process operations literature. (C) 2012 Elsevier Ltd. All rights reserved.
This paper presents a simple branch-and-bound method based on Lagrangean relaxation and subgradient optimization for solving large instances of the capacitated facility location problem (CFLP) to optimality. To guess ...
详细信息
This paper presents a simple branch-and-bound method based on Lagrangean relaxation and subgradient optimization for solving large instances of the capacitated facility location problem (CFLP) to optimality. To guess a primal solution to the Lagrangean dual, we average solutions to the Lagrangean subproblem. Branching decisions are then based on this estimated (fractional) primal solution. Extensive numerical results reveal that the method is much faster and more robust than other state-of-the-art methods for solving the CFLP exactly.
暂无评论