An Application Of CB Cutting Plane In Integer Programming And A Class Of Continuous Algorithm

In this thesis，we mainly study two kinds of the integer programming problems：Algorithms for solving all solutions of small-scale integer programming problems andthe continuous transformation of0-1Integer Programming Model，The detail contentsare as follows：For relatively small-scale integer programming problems，we consider how to findall solutions of this problem。 It is of great application value in reality，For the sameoptimization problem，if we can find all optimal solutions，there are a number of optionsfor policymakers to minimum the cost under the same profit。In literature[1]The authorpresents a method of looking for all solutions of problem：using a norm，combined withinteger constraints，then to obtain the nonlinear constrains of∑n（？） x （？）z x0≥1z=1，Finally theauthor uses the equivalent constraints of nonlinear constraints to transferred it into alinear programming。By the inspiration of this ideas，this paper also presents amethod to find all solutions of problem，For the general integer programming problemwe first consider to transform it into a0-1linear programming problem by usinglinearization method[2,3]。Then, we introduce CB tangent plane[4-6]into the optimizationproblem in order to establish a model，which can exclude the obtained optimal solution，such that for each obtained optimal solution there is a corresponding CB tangent planeto successive remove the solution。So we can find out all optimal solutions of theproblem。For a general0-1linear programming problem，we can get its explicit expressionof Lagrange dual problem for it’s particularity。But there is a project functionmax(f,0)in the model，as a result of this function is a piecewise function withdiscontinuity，A general analytical mathematical algorithm cannot work effectively。Here we consider some special functions：logarithmic barrier function (aggregatefunction)[7,8]，the NCP function，then presents the smooth logarithmic barrier functionmethod and the NCP function method。At the same time，we presents a new methodcombining on the equivalent constraint conditions of one norm[1]，then we obtains acontinuous and smooth optimization model，we can solve the model using analyticoptimization algorithm through the continuous transformation，the solution obtained isthat of original problem。...