Recently, Andersen et al. [1] and Borozan and Cornuejols [3] characterized the minimal inequalities of a system of two rows with two free integer variables and nonnegative continuous variables. these inequalities are ...
详细信息
ISBN:
(纸本)9783540688860
Recently, Andersen et al. [1] and Borozan and Cornuejols [3] characterized the minimal inequalities of a system of two rows with two free integer variables and nonnegative continuous variables. these inequalities are either split cuts or intersection cuts derived using maximal lattice-free convex sets. In order to use these minimal inequalities to obtain cuts from two rows of a general simplex tableau, it is necessary to extend the system to include integer variables (giving the two-dimensional mixed integer infinite group problem), and to develop lifting functions giving the coefficients of the integer variables in the corresponding inequalities. In this paper, we analyze the lifting of minimal inequalities derived from lattice-free triangles. Maximal lattice-free triangles in R-2 can be classified into three categories: those with multiple integral points in the relative interior of one of its sides, those with integral vertices and one integral point in the relative interior of each side, and those with non integral vertices and one integral point in the relative interior of each side. We prove that the lifting functions are unique for each of the first two categories such that the resultant inequality is minimal for the mixed integer infinite group problem, and characterize them. We show that the lifting function is not necessarily unique in the third category. For this category we show that a fill-in inequality (Johnson [11]) yields minimal inequalities for mixed integer infinite group problem under certain sufficiency conditions. Finally, we present conditions for the fill-in inequality to be extreme.
We study mixed integer nonlinear programs (MINLP) that are driven by a collection of indicator variables where each indicator variable controls a subset of the decision variables. An indicator variable, when it is &qu...
详细信息
ISBN:
(纸本)9783540688860
We study mixed integer nonlinear programs (MINLP) that are driven by a collection of indicator variables where each indicator variable controls a subset of the decision variables. An indicator variable, when it is "turned off", forces some of the decision variables to assume a fixed value, and, when it is "turned on", forces them to belong to a convex set. Most of the integer variables in known MINLP problems are of this type. We first study a mixed integer set defined by a single separable quadratic constraint and a collection of variable upper and lower bound constraints. this is an interesting set that appears as a substructure in many applications. We present the convex hull description of this set. We then extend this to produce an explicit characterization of the convex hull of the union of a point and a bounded convex set defined by analytic functions. Further, we show that for many classes of problems, the convex hull can be expressed via conic quadratic constraints, and thus relaxations can be solved via second-order cone programming. Our work is closely related withthe earlier work of Ceria and Soares (1996) as well as recent work by Frangioni and Gentile (2006) and, Akturk, Atamturk and Gurel (2007). Finally, we apply our results to develop tight formulations of mixed integer nonlinear programs in which the nonlinear functions are separable and convex and in which indicator variables play an important role. In particular, we present strong computational results with two applications - quadratic facility location and network design with congestion - that show the power of the reformulation technique.
We give a new, algorithmic proof for the maximum even factor formula which can be converted into a polynomial time combinatorial algorithm to solve the maximum even factor problem. In several aspects, the approach is ...
详细信息
ISBN:
(纸本)3540261990
We give a new, algorithmic proof for the maximum even factor formula which can be converted into a polynomial time combinatorial algorithm to solve the maximum even factor problem. In several aspects, the approach is similar to Edmonds' Matching Algorithm, but there is a significant difference.
the vendor selection and Order Quantity Allocation problem with fuzzy demand and price discount is formulated as a multi-objective mixed-integer fuzzy programming model. the proposed model has the following characteri...
详细信息
ISBN:
(纸本)7560323553
the vendor selection and Order Quantity Allocation problem with fuzzy demand and price discount is formulated as a multi-objective mixed-integer fuzzy programming model. the proposed model has the following characteristics: deterministic and fuzz constraints, and the assumption of fuzzy demand and price discount are expressed by using constraint equations. According to the special features of the model, appropriate solution strategy is proposed. It involves three steps: (1) membership function for every fuzzy objective and constraint is set up;(9) by means of max-min operator, the multi-objective mixed-integer fuzzy programming model is converted into several equivalent single-objective linear programming model;() the optimal solution for order quantity allocation problem is derived based on two-phase approach. An application example was also given for testing the feasibility and effectiveness of the proposed method.
We report on GADGET, a new software test generation system that uses combinatorialoptimization to obtain condition/decision coverage of C/C++ programs. the GADGET system is fully automatic and supports all C/C++ lang...
详细信息
ISBN:
(纸本)0818687509
We report on GADGET, a new software test generation system that uses combinatorialoptimization to obtain condition/decision coverage of C/C++ programs. the GADGET system is fully automatic and supports all C/C++ language constructs. this allows us to generate tests for programs more complex than those previously reported in the literature. We address a number of issues that are encountered when automatically generating tests for complex software systems. these issues have not been discussed in earlier work on test-data generation, which concentrates on small programs (most often single functions) written in restricted programming languages.
We study the stochastic machine replenishment problem, which is a canonical special case of closed multiclass queuing systems in Markov decision theory. the problem models the scheduling of processor repairs in a mult...
详细信息
ISBN:
(纸本)9783540688860
We study the stochastic machine replenishment problem, which is a canonical special case of closed multiclass queuing systems in Markov decision theory. the problem models the scheduling of processor repairs in a multiprocessor system in which one repair can be made at a time and the goal is to maximize system utilization. We analyze the performance of a natural greedy index policy for this problem. We first show that this policy is a 2 approximation by exploring linear queuing structure in the index policy. We then try to exploit more complex queuing structures, but this necessitates solving an infinite-size, non-linear, non-convex, and non-separable function-maximization program. We develop a general technique to solve such programs to arbitrary degree of accuracy, which involves solving a discretized program on the computer and rigorously bounding the error. this proves that the index policy is in fact a 1.51 approximation. the main non-trivial ingredients of the proof are two folds: finding a way to analyze the complex queuing structure of the index policy, and bounding the error in discretization when numerically solving the non-linear function-maximization. We believe that this framework is general enough to be useful in the analysis of index policies in related problems. As far as we are aware, this is one of the first non-trivial approximation analysis of an index policy a multi-class queuing problem, as well as one of the first non-trivial example of an approximation ratio that is rigorously proven by numerical optimization via a computer.
Robust combinatorialoptimization with budget uncertainty is one of the most popular approaches for integrating uncertainty in optimization problems. the existence of a compact reformulation for (mixed-integer) linear...
详细信息
ISBN:
(数字)9783031327261
ISBN:
(纸本)9783031327254;9783031327261
Robust combinatorialoptimization with budget uncertainty is one of the most popular approaches for integrating uncertainty in optimization problems. the existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is actually quite poor when solving robust integer problems due to its weak linear relaxation. To overcome the problems arising from the weak formulation, we propose a procedure to derive new classes of valid inequalities for robust binary optimization problems. For this, we recycle valid inequalities of the underlying deterministic problem such that the additional variables from the robust formulation are incorporated. the valid inequalities to be recycled may either be readily available model constraints or actual cutting planes, where we can benefit from decades of research on valid inequalities for classical optimization problems. We first demonstrate the strength of the inequalities theoretically, by proving that recycling yields a facet-defining inequality in surprisingly many cases, even if the original valid inequality was not facet-defining. Afterwards, we show in a computational study that using recycled inequalities leads to a significant improvement of the computation time when solving robust optimization problems.
this paper investigates the Kronecker canonical form of matrix pencils under the genericity assumption that the set of nonzero entries is algebraically independent. We provide a combinatorial characterization of the s...
详细信息
ISBN:
(纸本)3540261990
this paper investigates the Kronecker canonical form of matrix pencils under the genericity assumption that the set of nonzero entries is algebraically independent. We provide a combinatorial characterization of the sums of the row/colunm indices supported by efficient bipartite matching algorithms. We also give a simple alternative proof for a theorem of Poljak on the generic ranks of matrix powers.
We present two approaches to the construction of scaling functions and wavelets that generate nearly cardinal and nearly symmetric wavelets on the line. the first approach casts wavelet construction as an optimization...
详细信息
ISBN:
(纸本)9781728137414
We present two approaches to the construction of scaling functions and wavelets that generate nearly cardinal and nearly symmetric wavelets on the line. the first approach casts wavelet construction as an optimization problem by imposing constraints on the integer samples of the scaling function and its associated wavelet and with an objective function that minimizes deviation from cardinality or symmetry. the second method is an extension of the feasibility approach by Franklin, Hogan, and Tam to allow for symmetry by considering variables generated from uniform samples of the quadrature mirror filter, and is solved via the Douglas-Rachford algorithm.
In this paper we consider a variant of the betweenness problem occurring in computational biology. We present a new polyhedral approach which incorporates the solution of consecutive ones problems and show that it sup...
详细信息
ISBN:
(纸本)354064590X
In this paper we consider a variant of the betweenness problem occurring in computational biology. We present a new polyhedral approach which incorporates the solution of consecutive ones problems and show that it supersedes an earlier one. A particular feature of this new branch-and-cut algorithm is that it is not based on an explicit integerprogramming formulation of the problem and makes use of automatically generated facet-defining inequalities.
暂无评论