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.
Given a factorable function f, we propose a procedure that constructs a concave underestimator of f that is tight at a given point. these underestimators can be used to generate intersection cuts. A peculiarity of the...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
Given a factorable function f, we propose a procedure that constructs a concave underestimator of f that is tight at a given point. these underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.
Numerous real-world problems relating to flow-shop scheduling are characterized by combinatorially explosive alternatives as well as multiple conflicting objectives and are denoted as multiobjective combinatorial opti...
详细信息
ISBN:
(纸本)9787560322780
Numerous real-world problems relating to flow-shop scheduling are characterized by combinatorially explosive alternatives as well as multiple conflicting objectives and are denoted as multiobjective combinatorialoptimization problems. the problem of multiobjective optimization with setup times in flow shop is considered in this study. the objective function of the problem is minimization of the weighted sum of total completion time, makespan, maximum tardiness and maximum earliness. An integerprogramming model is developed for the problem which belongs to NP-hard class by using the hybrid genetic algorithm (HGA) to move from. local optimal solution to near optimal solution for flow-shop scheduling problems. Small size problems and large size problems can be solved by the proposed integerprogramming model. Computational experiments are performed to illustrate the effectiveness and efficiency of the proposed HGA algorithm.
this book constitutes the refereed proceedings of the 17thinternationalconference on integerprogramming and combinatorialoptimization, IPCO 2014, held in Bonn, Germany, in June 2014. the 34 full papers presented w...
详细信息
ISBN:
(数字)9783319075570
ISBN:
(纸本)9783319075563
this book constitutes the refereed proceedings of the 17thinternationalconference on integerprogramming and combinatorialoptimization, IPCO 2014, held in Bonn, Germany, in June 2014. the 34 full papers presented were carefully reviewed and selected from 143 submissions. the conference is a forum for researchers and practitioners working on various aspects of integerprogramming and combinatorialoptimization. the aim is to present recent developments in theory, computation, and applications in these areas. the scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integerprogramming and combinatorialoptimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.
this paper addresses the resolution of combinatorialoptimization problems presenting some kind of recurrent structure, coupled with machine learning techniques. Stemming from the assumption that such recurrent proble...
详细信息
ISBN:
(纸本)9789897583520
this paper addresses the resolution of combinatorialoptimization problems presenting some kind of recurrent structure, coupled with machine learning techniques. Stemming from the assumption that such recurrent problems are the realization of an unknown generative probabilistic model, data is collected from previous resolutions of such problems and used to train a supervised learning model for multi-label classification. this model is exploited to predict a subset of decision variables to be set heuristically to a certain reference value, thus becoming fixed parameters in the original problem. the remaining variables then form a smaller subproblem whose solution, while not guaranteed to be optimal for the original problem, can be obtained faster, offering an advantageous tool for tackling time-sensitive tasks.
In this paper, we show how to generate strong cuts for unstructured mixed integer programs through the study of high-dimensional group problems. We present a new operation that generates facet-defining inequalities fo...
详细信息
ISBN:
(纸本)9783540727910
In this paper, we show how to generate strong cuts for unstructured mixed integer programs through the study of high-dimensional group problems. We present a new operation that generates facet-defining inequalities for two-dimensional group problems by combining two facet-defining inequalities of one-dimensional group problems. Because the procedure allows the use of a large variety of one-dimensional constituent inequalities, it yields large families of new cutting planes for MIPs that we call sequential-merge inequalities. We show that sequential-merge inequalities can be used to generate inequalities whose continuous variable coefficients are stronger than those of one-dimensional cuts and can be used to derive the three-gradient facet-defining inequality introduced by Dey and Richard [4].
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.
We propose a Branch-and-Cut algorithm for the robust influence maximization problem. the influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
We propose a Branch-and-Cut algorithm for the robust influence maximization problem. the influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum number of other actors. We assume that the social network is given in the form of a graph with node thresholds to indicate the resistance of an actor to influence, and arc weights to represent the strength of the influence between two actors. In the robust version of the problem that we study, the node thresholds are affected by uncertainty and we optimize over a worst-case scenario within a given robustness budget. Numerical experiments show that we are able to solve to optimality instances of size comparable to other exact approaches in the literature for the non-robust problem, but in addition to this we can also tackle the robust version with similar performance.
A clutter is identically self-blocking if it is equal to its blocker. We prove that every identically self-blocking clutter different from {{a}} is nonideal. Our proofs borrow tools from Gauge Duality and Quadratic Pr...
详细信息
ISBN:
(数字)9783030179533
ISBN:
(纸本)9783030179533;9783030179526
A clutter is identically self-blocking if it is equal to its blocker. We prove that every identically self-blocking clutter different from {{a}} is nonideal. Our proofs borrow tools from Gauge Duality and Quadratic programming. Along the way we provide a new lower bound for the packing number of an arbitrary clutter.
暂无评论