A chance constrained problem involves a set of scenario constraints from which a small subset can be violated. Existing works typically consider a mixed integerprogramming (MIP) formulation of this problem by introdu...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
A chance constrained problem involves a set of scenario constraints from which a small subset can be violated. Existing works typically consider a mixed integerprogramming (MIP) formulation of this problem by introducing binary variables to indicate which constraint systems are to be satisfied or violated. A variety of cutting plane approaches for this MIP formulation have been developed. In this paper we consider a family of cuts for chance constrained problems in the original space rather than those in the extended space of the MIP reformulation. these cuts, known as quantile cuts, can be viewed as a projection of the well known family of mixing inequalities for the MIP reformulation, onto the original problem space. We show the following results regarding quantile cuts: (i) the closure of all quantile cuts is a polyhedral set;(ii) separation of quantile cuts is in general NP-hard;(iii) successive application of quantile cut closures achieves the convex hull of the chance constrained problem in the limit;and (iv) in the pure integer setting this convergence is finite.
Wireless Sensor Network is huge number of sensor nodes disposed randomly in severe field to gather data. It monitors physical phenominan changes such as temperature, pressure, humidity, solar radition, ambident light ...
详细信息
ISBN:
(纸本)9781467389754
Wireless Sensor Network is huge number of sensor nodes disposed randomly in severe field to gather data. It monitors physical phenominan changes such as temperature, pressure, humidity, solar radition, ambident light extra. Sensor nodes are small in size, having less energy, less communication power, less cost and multi functional nodes. this paper we firstly discuss about different types types of network, protocols extra i. e Network such as Direct network, hierarchical network etc and protocols like LEACH, PEGASIS. Next in this paper we deployed sensor nodes randomly in the grid network, We focus on data aggregation in different type of sitution known as critical zone, in critical zone(critical grid) senor nodes are heavly loaded with information. Our objective is to maximize the data generation rate of sensor nodes. To got this objective we form different integer linear programming formulation. A optimization tool such as CPLEX IBM ILOG used for optimization and to show critical grids aggregation used MATLAB.
We propose two simple polynomial-time algorithms to find a positive solution to Ax = 0. Both algorithms iterate between coordinate descent steps similar to von Neumann's algorithm, and rescaling steps. In both cas...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We propose two simple polynomial-time algorithms to find a positive solution to Ax = 0. Both algorithms iterate between coordinate descent steps similar to von Neumann's algorithm, and rescaling steps. In both cases, either the updating step leads to a substantial decrease in the norm, or we can infer that the condition measure is small and rescale in order to improve the geometry. We also show how the algorithms can be extended to find a solution of maximum support for the system Ax = 0, x >= 0. this is an extended abstract. the missing proofs will be provided in the full version.
the exact solution of bilevel optimization problems is a very challenging task that received more and more attention in recent years, as witnessed by the flourishing recent literature on this topic. In this paper we p...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
the exact solution of bilevel optimization problems is a very challenging task that received more and more attention in recent years, as witnessed by the flourishing recent literature on this topic. In this paper we present ideas and algorithms to solve to proven optimality generic Mixed-integer Bilevel Linear Programs (MIBLP's) where all constraints are linear, and some/all variables are required to take integer values. In doing so, we look for a general-purpose approach applicable to any MIBLP (under mild conditions), rather than ad-hoc methods for specific cases. Our approach concentrates on minimal additions required to convert an effective branch-and-cut MILP exact code into a valid MIBLP solver, thus inheriting the wide arsenal of MILP tools (cuts, branching rules, heuristics) available in modern solvers.
this paper proposes a force-directed scheduling algorithm for peak power optimization based on multi-cycle operations. Utilizing the basic idea of traditional force-directed scheduling algorithm and resetting the para...
详细信息
ISBN:
(纸本)9781467397209
this paper proposes a force-directed scheduling algorithm for peak power optimization based on multi-cycle operations. Utilizing the basic idea of traditional force-directed scheduling algorithm and resetting the parameters related to force, this new algorithm has realized the balanced distribution of cycle power in scheduling process, thus minimizing peak power. Experimental results show that withthe same control step constraint and resource consumption, the algorithm proposed in this paper has been improved in the aspect of peak power optimization compared with traditional force-directed scheduling algorithms, and bears comparison withthe integer linear programming method.
Sherali-Adams [25] and Lovasz-Schrijver [21] developed systematic procedures to strengthen a relaxation known as lift-and-project methods. they have been proven to be a strong tool for developing approximation algorit...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
Sherali-Adams [25] and Lovasz-Schrijver [21] developed systematic procedures to strengthen a relaxation known as lift-and-project methods. they have been proven to be a strong tool for developing approximation algorithms, matching the best relaxations known for problems like Max-Cut and Sparsest-Cut. In this work we provide lower bounds for these hierarchies when applied over the configuration LP for the problem of scheduling identical machines to minimize the makespan. First we show that the configuration LP has an integrality gap of at least 1024/1023 by providing a family of instances with 15 different job sizes. then we show that for any integer n there is an instance with n jobs in this family such that after Omega(n) rounds of the Sherali-Adams (SA) or the Lovasz-Schrijver (LS+) hierarchy the integrality gap remains at least 1024/1023.
In recent years, decision diagrams (DDs) have proven useful for solving a variety of optimization problems, often closing long-standing instances from classical benchmarks. this success is primarily driven by a DDs ab...
详细信息
ISBN:
(数字)9783319339542
ISBN:
(纸本)9783319339542;9783319339535
In recent years, decision diagrams (DDs) have proven useful for solving a variety of optimization problems, often closing long-standing instances from classical benchmarks. this success is primarily driven by a DDs ability to capture structure. this paper exploits this characteristic and proposes a novel solution method which decomposes a problem into highly-structured portions, where the solution set of each portion can be compactly represented using a DD. this technique is applied to a special case of the independent set problem and to unconstrained binary quadratic programming. Preliminary computational results suggest that the proposed decomposition approach can improve upon both standard integerprogramming models and a single DD approach.
Nowadays, we're all familiar withthe speed of e-commerce development, but we have to admit that logistics industry in rural areas is still in its infancy. As deficient rural logistics network has restricted the r...
详细信息
ISBN:
(纸本)9781509061198
Nowadays, we're all familiar withthe speed of e-commerce development, but we have to admit that logistics industry in rural areas is still in its infancy. As deficient rural logistics network has restricted the rural development to a certain extent, this research field becomes a hot topic. However, most existing papers on forward and reverse logistics network design were primarily concerned with minimizing the total cost, neglecting the time sensitivity. In this paper, we propose a rural forward and reverse logistics network mode of e-commerce platform and a multiobjective mixed-integer linear programming model for logistics network design. To solve the NP-hard problem of the model, the nondominated sorting genetic algorithm II (NSGA-II) has been used. At last, the model has been used to design forward and reverse rural logistics network in Pinggu district of Beijing as an example, and the result show that the model is efficient for establishing virtuous rural logistics network.
Nursing workload in hospitals has an impact on the quality of care and on job satisfaction. Understandably there has been much recent research on improving the staffing and nurse-patient assignment decisions in increa...
详细信息
ISBN:
(纸本)9783319339542;9783319339535
Nursing workload in hospitals has an impact on the quality of care and on job satisfaction. Understandably there has been much recent research on improving the staffing and nurse-patient assignment decisions in increasingly realistic settings. On a version of the nurse-patient assignment problem given a fixed staffing of neonatal intensive care units, constraint programming (CP) was shown to perform better than competing optimization methods. In this paper we take advantage of recent improvements to the CP approach to solve the integrated problem of staffing and nurse-patient assignment. We then consider a more difficult but also more realistic version of the problem in which patients are categorized into a small number of types and the workload associated with each type is nurse-dependent.
暂无评论