Complexity of some parametric integer and network programming problems

Two examples of parametric cost programming problems—one in network programming and one in NP-hard 0-1 programming—are given; in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables in the problem. This research is partially supported by the Air Force Office of Scientic Research. Air Force Number AFOSR-78-3646     

A note on bicriterion programming

This note examines the complexity of solving the bicriterion vector maximum problem and the associated linear-weighted criterion problem over a finite set of alternatives. It presents an algorithm for linear-weighted problems with separable objectives that is considerably more efficient than complete enumeration of all alternatives and shows that the algorithm is essentially optimal for this problem.     

Cross decomposition for mixed integer programming

Many methods for solving mixed integer programming problems are based either on primal or on dual decomposition, which yield, respectively, a Benders decomposition algorithm and an implicit enumeration algorithm with bounds computed via Lagrangean relaxation. These methods exploit either the primal or the dual structure of the problem. We propose a new approach, cross decomposition, which allows exploiting simultaneously both structures. The development of the cross decomposition method captures profound relationships between primal and dual decomposition. It is shown that the more constraints can be included in the Langrangean relaxation (provided the duality gap remains zero), the fewer the Benders cuts one may expect to need. If the linear programming relaxation has no duality gap, only one Benders cut is needed to verify optimality.     

Comparative computer results of a new complementary pivot algorithm for solving equality and inequality constrained optimization problems

This paper reports the development of a new algorithm for solving the general constrained optimization problem (that of optimizing an objective function subject to both equality and inequality constraints). The approach is based on the complementary pivoting algorithms which have been developed to solve certain classes of fixed point problems. The specific approach is to use the equality constraints to solve for some variables in terms of the remaining ones thus enabling one to eliminate the equality constraints altogether. The result, under certain circumstances, is an optimization problem which may be transformed into a fixed point problem in such a way that a complementary pivoting code may be used to search for a solution.Seventeen test problems have been solved by this method and the results are compared against those obtained from GRG (Generalized Reduced Gradient method). The results of the tests indicate that the fixed point approach is robust (all 17 problems were solved by this method where as GRG solved 16). As to the computer times, the fixed point code proved to be as fast or faster than GRG on the lower dimensional problems; however, as the dimension increased, the trend reversed and on a 40 dimensional problem GRG was approximately 11 times faster. The conclusion from these tests is that when the dimension of the original problem can be reduced sufficiently by the equality constraints, the fixed point approach appears to be more effective than GRG.     

On the computational utility of posynomial geometric programming solution methods

Ten codes or code variants were used to solve the five equivalent posynomial GP problem formulations. Four of these codes were general NLP codes; six were specialized GP codes. A total of forty-two test problems was solved with up to twenty randomly generated starting points per problem. The convex primal formulation is shown to be intrinsically easiest to solve. The general purpose GRG code called OPT appears to be the most efficient code for GP problem solution. The reputed superiority of the specialized GP codes GGP and GPKTC appears to be largely due to the fact that these codes solve the convex primal formulation. The dual approaches are only likely to be competitive for small degree of difficulty, tightly constrained problems.     

Second order sensitivity analysis and asymptotic theory of parametrized nonlinear programs

In this paper we study second-order differential properties of an optimal-value function(x). It is shown that under certain conditions(x) possesses second-order directional derivatives, which can be calculated by solving corresponding quadratic programs. Also upper and lower bounds on these derivatives are introduced under weaker assumptions. In particular we show that the second-order directional derivative is infinite if the corresponding quadratic program is unbounded. Finally sensitivity results are applied to investigate asymptotics of estimators in parametrized nonlinear programs.     

Ein neues programmierbares Schema zur Bestimmung der Molekülsymmetrie

The symmetry of molecules can be determined, when their structure is known, using schemes of questions (algorithms), by means of which the existence of certain elements of symmetry is checked. In this paper, a new algorithm is presented, which renders feasible the prompt determination of symmetry point groups and visualizes relations between different types of symmetry. The application of the algorithm is demonstrated by means of a graphic scheme and a Pascal computer version.

     

Goal programming sensitivity analysis using interval penalty weights

This paper presents an application of the vector-maximum research [4–8] to the sensitivity analysis of goal programming problems as several of the criterion function penalty weights are simultaneously and independently varied. A generalized goal programming capability is presented and a six-stage analytic procedure is described. The problem is generalized in the sense that the regular goal programming penalty weights can be expanded to intervals if desired. The solution procedure is new in that it depends upon an algorithm for the vector-maximum problem, criterion cone contraction procedures, and filtering techniques. Together they are able to generate and process all extreme points on the portion of the surface of the goal programming augmented feasible region corresponding to the interval penalty weights specified. In effect, the procedure and adapted algorithm of this paper delivers to goal programming an operational power of sensitivity analysis not previously available to users. A numerical example is provided in order to illustrate the computerized application of the total goal programming procedure outlined.     

A polynomial algorithm for integer programming covering problems satisfying the integer round-up property

LetA be a non-negative matrix with integer entries and no zero column. The integer round-up property holds forA if for every integral vectorw the optimum objective value of the generalized covering problem min{1y: yA w, y 0 integer} is obtained by rounding up to the nearest integer the optimum objective value of the corresponding linear program. A polynomial time algorithm is presented that does the following: given any generalized covering problem with constraint matrixA and right hand side vectorw, the algorithm either finds an optimum solution vector for the covering problem or else it reveals that matrixA does not have the integer round-up property.     

The application of non-linear bi-level programming to the aluminium industry

In this paper, a solution algorithm is presented for the bi-level non-linear programming model developed to represent the complete operations of an aluminium smelter. The model is based on the Portland Aluminium Smelter, in Victoria, Australia and aims at maximising the aluminium production while minimising the main costs and activity associated with the production of this output. The model has two variables, the power input measured in kilo-Amperes (kA) and the setting cycle (of the anode replacement [SC]). The solution algorithm is based on the vertex enumeration approach and uses a specially developed grid search algorithm. An examination of the special nature of the model and how this assists the algorithm to arrive at an optimal unique solution (where there exists one) is undertaken. Additionally, future research into expansion of the model into a multi-period one (i.e., in effect a staircase model) allowing the optimisation of the smelter operations over a year (rather than as is currently the case, one month) and the broadening of the solution algorithm to deal with a more general problem, are introduced.