Fourier-Motzkin elimination and its dual

In this paper we investigate block designs with repeated blocks and parameters υ, k; b, r, λ satisfying (b, r, λ) = 1. These designs cannot be constructed by taking a number of identical copies of a smaller design. Several construction methods of such designs are given and we discuss those constructions of Hanani which yield such designs. Tables for υ ? 22 are included.     

Ranking in quadratic integer programming problems

The present paper develops an algorithm for ranking the integer feasible solutions of a quadratic integer programming (QIP) problem. A linear integer programming (LIP) problem is constructed which provides bounds on the values of the objective function of the quadratic problem. The integer feasible solutions of this related integer linear programming problem are systematically scanned to rank the integer feasible solutions of the quadratic problem in non-decreasing order of the objective function values. The ranking in the QIP problem is useful in solving a nonlinear integer programming problem in which some other complicated nonlinear restrictions are imposed which cannot be included in the simple linear constraints of QIP, the objective function being still quadratic.     

Mean value cross decomposition applied to integer programming problems

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition, that eliminates the need for using the Benders or Dantzig-Wolfe master problems. As input to the dual subproblem the average of a part of all known dual solutions of the primal subproblem is used, and as input to the primal subproblem the average of a part of all known primal solutions of the dual subproblem. In this paper we study the lower bounds on the optimal objective function value of (linear) pure integer programming problems obtainable by the application of mean value cross decomposition, and find that this approach can be used to get lower bounds ranging from the bound obtained by the LP-relaxation to the bound obtained by the Lagrangean dual. We examplify by applying the technique to the clustering problem and give some preliminary computational results.     

Ranking in integer linear fractional programming problems

An algorithm is developed which ranks the feasible solutions of an integer fractional programming problem in decreasing order of the objective function values.

---

Zusammenfassung Es wird ein Algorithmus angegeben, der die zulässigen Lösungen eines ganzzahligen Quotientenprogrammes nach fallenden Zielfunktionswerten liefert.

     

Alternative group relaxation of integer programming problems

The classical group approach to integer linear programming problems (IP) can be generalized in order to obtain group minimization problems with different computational load and different relaxation.The aim of this work is to analyze some group problems, associated to the same (IP), both from the point of view of the relaxation of the (IP) and of the complexity of the group solution algorithm; evaluation criteria for these group problems are pointed out.     

On the mixed integer signomial programming problems

This paper proposes an approximate method to solve the mixed integer signomial programming problem, for which the objective function and the constraints may contain product terms with exponents and decision variables, which could be continuous or integral. A linear programming relaxation is derived for the problem based on piecewise linearization techniques, which first convert a signomial term into the sum of absolute terms; these absolute terms are then linearized by linearization strategies. In addition, a novel approach is included for solving integer and undefined problems in the logarithmic piecewise technique, which leads to more usefulness of the proposed method. The proposed method could reach a solution as close as possible to the global optimum.     

An integral transformation for integer programming problems

It is shown that every integer programming problem can be transformed into an equivalent integer program with free variables in polynomial time. The transformation is advantageous because the equivalent problem it generates can be solved very easily in some restricted cases.     

An integer programming approach to a class of combinatorial problems

In this paper, we discuss the solution of a class of modified quadratic assignment problems, with particular reference to an application involving decentralization of a large organization. The main emphasis is on the use of a standard branch and bound mathematical programming system (UMPIRE) and the problem manipulations required to carry this out efficiently.     

Enhanced mixed integer programming techniques and routing problems

This is a summary of the author’s PhD thesis supervised by Andrea Lodi and Paolo Toth and defended on 16 April 2009 at the Università di Bologna. The thesis is written in English and is available from the author upon request. This work is focused on Mixed Integer Programming (MIP). In particular, the first part of the thesis deals with general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. The second part is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications.     

Solving school bus routing problems through integer programming

In this paper, an exact solution approach is described for solving a real-life school bus routing problem (SBRP) for transporting the students of an elementary school throughout central Ankara, Turkey. The problem is modelled as a capacitated and distance constrained open vehicle routing problem and an associated integer linear program is presented. The integer program borrows some well-known inequalities from the vehicle routing problem, which are also shown to be valid for the SBRP under consideration. The optimal solution of the problem is computed using the proposed formulation, resulting in a saving of up to 28.6% in total travelling cost as compared to the current implementation.     

On nadir points of multiobjective integer programming problems

In this study, we consider the nadir points of multiobjective integer programming problems. We introduce new properties that restrict the possible locations of the nondominated points necessary for computing the nadir points. Based on these properties, we reduce the search space and propose an exact algorithm for finding the nadir point of multiobjective integer programming problems. We present an illustrative example on a three objective knapsack problem. We conduct computational experiments and compare the performances of two recent algorithms and the proposed algorithm.     

The reformulation of two mixed integer programming problems

Two practical problems are described, each of which can be formulated in more than one way as a mixed integer programming problem. The computational experience with two formulations of each problem is given. It is pointed out how in each case a reformulation results in the associated linear programming problem being more constrained. As a result the reformulated mixed integer problem is easier to solve. The problems are a multi-period blending problem and a mining investment problem.     

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.     

A trajectory-based method for mixed integer nonlinear programming problems

A local trajectory-based method for solving mixed integer nonlinear programming problems is proposed. The method is based on the trajectory-based method for continuous optimization problems. The method has three phases, each of which performs continuous minimizations via the solution of systems of differential equations. A number of novel contributions, such as an adaptive step size strategy for numerical integration and a strategy for updating the penalty parameter, are introduced. We have shown that the optimal value obtained by the proposed method is at least as good as the minimizer predicted by a recent definition of a mixed integer local minimizer. Computational results are presented, showing the effectiveness of the method.     

On the existence of optimal solutions to integer and mixed-integer programming problems

The purpose of this paper is to present sufficient conditions for the existence of optimal solutions to integer and mixed-integer programming problems in the absence of upper bounds on the integer variables. It is shown that (in addition to feasibility and boundedness of the objective function) (1) in the pure integer case a sufficient condition is that all of the constraints (other than non-negativity and integrality of the variables) beequalities, and (2) that in the mixed-integer caserationality of the constraint coefficients is sufficient. Some computational implications of these results are also given.     

A meta-control algorithm for generating approximate solutions to binary integer programming problems

Binary integer program problems, which are known to be difficult to solve, have long been an important research area. We use a new approach with continualization techniques to find approximate solutions to binary integer programming problems. The algorithm constructs a sequence of approximations to a solution using a meta-control approach that has low polynomial time complexity. The algorithm is illustrated with a BIP example.     

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