An algorithm for nonlinear optimization problems with binary variables

One of the challenging optimization problems is determining the minimizer of a nonlinear programming problem that has binary variables. A vexing difficulty is the rate the work to solve such problems increases as the number of discrete variables increases. Any such problem with bounded discrete variables, especially binary variables, may be transformed to that of finding a global optimum of a problem in continuous variables. However, the transformed problems usually have astronomically large numbers of local minimizers, making them harder to solve than typical global optimization problems. Despite this apparent disadvantage, we show that the approach is not futile if we use smoothing techniques. The method we advocate first convexifies the problem and then solves a sequence of subproblems, whose solutions form a trajectory that leads to the solution. To illustrate how well the algorithm performs we show the computational results of applying it to problems taken from the literature and new test problems with known optimal solutions.     

A decomposition approach for global optimum search in QP,NLP and MINLP problems

Nonconvex programming problems are frequently encountered in engineering and operations research. A large variety of global optimization algorithms have been proposed for the various classes of programming problems. A new approach for global optimum search is presented in this paper which involves a decomposition of the variable set into two sets —complicating and noncomplicating variables. This results in a decomposition of the constraint set leading to two subproblems. The decomposition of the original problem induces special structure in the resulting subproblems and a series of these subproblems are then solved, using the Generalized Benders' Decomposition technique, to determine the optimal solution. The key idea is to combine a judicious selection of the complicating variables with suitable transformations leading to subproblems which can attain their respective global solutions at each iteration. Mathematical properties of the proposed approach are presented. Even though the proposed approach cannot guarantee the determination of the global optimum, computational experience on a number of nonconvex QP, NLP and MINLP example problems indicates that a global optimum solution can be obtained from various starting points.     

Polynomial dual network simplex algorithms

We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m ² logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

A primal simplex algorithm that solves the maximum flow problem in at mostnm pivots and O(n 2 m) time

We propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that isclosest to the source node from amongst all possible candidates. We prove that this algorithm requires at mostnm pivots to solve a problem withn nodes andm arcs, and give implementations of it which run in O(n ² m) time. Our algorithm is, as far as we know, the first strongly polynomial primal simplex algorithm for solving the maximum flow problem.This research was supported in part by NSF Grants DMS 85-12277 and CDR 84-21402 and ONR Contract N00014-87-K0214.     

A Decomposition Method for Global and Local Quadratic Minimization

We present a decomposition method for indefinite quadratic programming problems having n variables and m linear constraints. The given problem is decomposed into at most m QP subproblems each having m linear constraints and n-1 variables. All global minima, all isolated local minima and some of the non-isolated local minima for the given problem are obtained from those of the lower dimensional subproblems. One way to continue solving the given problem is to apply the decomposition method again to the subproblems and repeatedly doing so until subproblems of dimension 1 are produced and these can be solved directly. A technique to reduce the potentially large number of subproblems is formulated.     

The Exterior Dirichlet Problem for the Biharmonic Equation: Solutions with Bounded Dirichlet Integral

We study the unique solvability of the Dirichlet problem for the biharmonic equation in the exterior of a compact set under the assumption that a generalized solution of this problem has a bounded Dirichlet integral with weight |x|^a. Depending on the value of the parameter ^a,a we prove uniqueness theorems or present exact formulas for the dimension of the solution space of the Dirichlet problem.     

Neighborhood search approaches to beam orientation optimization in intensity modulated radiation therapy treatment planning

The intensity modulated radiation therapy (IMRT) treatment planning problem consists of several subproblems which are typically solved sequentially. We seek to combine two of the subproblems: the beam orientation optimization (BOO) problem and the fluence map optimization (FMO) problem. The BOO problem is the problem of selecting the beam orientations to deliver radiation to the patient. The FMO problem is the problem of determining the amount of radiation intensity, or fluence, of each beamlet in each beam. The solution to the FMO problem measures the quality of a beam set, but the majority of previous BOO studies rely on heuristics and approximations to gauge the quality of the beam set. In contrast with these studies, we use an exact measure of the treatment plan quality attainable using a given beam set, which ensures convergence to a global optimum in the case of our simulated annealing algorithm and a local optimum in the case of our local search algorithm. We have also developed a new neighborhood structure that allows for faster convergence using our simulated annealing and local search algorithms, thus reducing the amount of time required to obtain a good solution. Finally, we show empirically that we can generate clinically acceptable treatment plans that require fewer beams than in current practice. This may reduce the length of treatment time, which is an important clinical consideration in IMRT.     

A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming

The constraint selection approach to linear programming begins by solving a relaxed version of the problem using only a few of the original constraints. If the solution obtained to this relaxation satisfies the remaining constraints it is optimal for the original LP. Otherwise, additional constraints must be incorporated in a larger relaxation. The procedure successively generates larger subproblems until an optimal solution is obtained which satisfies all of the original constraints. Computational results for a dual simplex implementation of this technique indicate that solving several small subproblems in this manner is more computationally efficient than solving the original LP using the revised simplex method.     

A polynomial-time simplex method for the maximumk-flow problem

A generalization of the maximum-flow problem is considered in which every unit of flow sent from the source to the sink yields a payoff of $k. In addition, the capacity of any arce can be increased at a per-unit cost of $c _e . The problem is to determine how much arc capacity to purchase for each arc and how much flow to send so as to maximize the net profit. This problem can be modeled as a circulation problem. The main result of this paper is that this circulation problem can be solved by the network simplex method in at mostkmn pivots. Whenc _e = 1 for each arce, this yields a strongly polynomial-time simplex method. This result uses and extends a result of Goldfarb and Hao which states that the standard maximum-flow problem can be solved by the network simplex method in at mostmn pivots.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

Convergence of an operator splitting method on a bounded domain for a convection-diffusion-reaction system

We solve a convection-diffusion-sorption (reaction) system on a bounded domain with dominant convection using an operator splitting method. The model arises in contaminant transport in groundwater induced by a dual-well, or in controlled laboratory experiments. The operator splitting transforms the original problem to three subproblems: nonlinear convection, nonlinear diffusion, and a reaction problem, each with its own boundary conditions. The transport equation is solved by a Riemann solver, the diffusion one by a finite volume method, and the reaction equation by an approximation of an integral equation. This approach has proved to be very successful in solving the problem, but the convergence properties where not fully known. We show how the boundary conditions must be taken into account, and prove convergence in L1,loc of the fully discrete splitting procedure to the very weak solution of the original system based on compactness arguments via total variation estimates. Generally, this is the best convergence obtained for this type of approximation. The derivation indicates limitations of the approach, being able to consider only some types of boundary conditions. A sample numerical experiment of a problem with an analytical solution is given, showing the stated efficiency of the method.     

Packing congruent hyperspheres into a hypersphere

The paper considers a problem of packing the maximal number of congruent nD hyperspheres of given radius into a larger nD hypersphere of given radius where n = 2, 3, . . . , 24. Solving the problem is reduced to solving a sequence of packing subproblems provided that radii of hyperspheres are variable. Mathematical models of the subproblems are constructed. Characteristics of the mathematical models are investigated. On the ground of the characteristics we offer a solution approach. For n ≤ 3 starting points are generated either in accordance with the lattice packing of circles and spheres or in a random way. For n > 3 starting points are generated in a random way. A procedure of perturbation of lattice packings is applied to improve convergence. We use the Zoutendijk feasible direction method to search for local maxima of the subproblems. To compute an approximation to a global maximum of the problem we realize a non-exhaustive search of local maxima. Our results are compared with the benchmark results for n = 2. A number of numerical results for 2 ≤ n ≤ 24 are given.     

A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs

We consider probabilistically constrained linear programs with general distributions for the uncertain parameters. These problems involve non-convex feasible sets. We develop a branch-and-bound algorithm that searches for a global optimal solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partition elements. This basic algorithm is enhanced by domain reduction and cutting plane strategies to reduce the size of the partition elements and hence tighten bounds. The proposed branch-reduce-cut algorithm exploits the monotonicity properties inherent in the problem, and requires solving linear programming subproblems. We provide convergence proofs for the algorithm. Some illustrative numerical results involving problems with discrete distributions are presented.     

On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables

In this paper, we propose a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having mixed-integer first- and second-stage variables. A modified Benders' decomposition method is developed, where the Benders' subproblems define lower bounding second-stage value functions of the first-stage variables that are derived by constructing a certain partial convex hull representation of the two-stage solution space. This partial convex hull is sequentially generated using a convexification scheme such as the Reformulation-Linearization Technique (RLT) or lift-and-project process, which yields valid inequalities that are reusable in the subsequent subproblems by updating the values of the first-stage variables. A branch-and-bound algorithm is designed based on a hyperrectangular partitioning process, using the established property that any resulting lower bounding Benders' master problem defined over a hyperrectangle yields the same objective value as the original stochastic program over that region if the first-stage variable solution is an extreme point of the defining hyperrectangle or the second-stage solution satisfies the binary restrictions. We prove that this algorithm converges to a global optimal solution. Some numerical examples and computational results are presented to demonstrate the efficacy of this approach.     

Optimal Covering of Plane Domains by Circles Via Hyperbolic Smoothing

We consider the problem of optimally covering plane domains by a given number of circles. The mathematical modeling of this problem leads to a min–max–min formulation which, in addition to its intrinsic multi-level nature, has the significant characteristic of being non-differentiable. In order to overcome these difficulties, we have developed a smoothing strategy using a special class C^∞ smoothing function. The final solution is obtained by solving a sequence of differentiable subproblems which gradually approach the original problem. The use of this technique, called Hyperbolic Smoothing, allows the main difficulties presented by the original problem to be overcome. A simplified algorithm containing only the essential of the method is presented. For the purpose of illustrating both the actual working and the potentialities of the method, a set of computational results is presented.