A penalty for concave minimization derived from the tuy cutting plane

A wide variety of optimization problems have been approached with branch-and-bound methodology, most notably integer programming and continuous nonconvex programming. Penalty calculations provide a means to reduce the number of subproblems solved during the branch-and-bound search. We develop a new penalty based on the Tuy cutting plane for the nonconvex problem of globally minimizing a concave function over linear constraints and continuous variables. Computational testing with a branch-and-bound algorithm for concave minimization indicates that, for the problems solved, the penalty reduces solution time by a factor ranging from 1.2 to 7.2. © 1994 John Wiley & Sons, Inc.     

Nonpreemptive scheduling of independent tasks with prespecified processor allocations

In this article we study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of prespecified processors, with the objective of minimizing the maximum completion time. We propose a graph-theoretical approach and identify a class of polynomial instances, corresponding to comparability graphs. We show that the scheduling problem is polynomially equivalent to the problem of extending a graph to a comparability graph whose maximum weighted clique has minimum weight. Using this formulation we show that in some cases it is possible to decompose the problem according to the canonical decomposition of the graph. Finally, a general solution procedure is given that includes a branch-and-bound algorithm for the solution of subproblems which can be neither decomposed nor solved in polynomial time. Some examples and computational results are presented. © 1994 John Wiley & Sons, Inc.     

A node covering algorithm

This paper describes a node covering algorithm, i.e., a procedure for finding a smallest set of nodes covering all edges of an arbitrary graph. The algorithm is based on the concept of a dual node-clique set, which allows us to identify partial covers associated with integer dual feasible solutions to the linear programming equivalent of the node covering problem. An initial partial cover with the above property is first found by a labeling procedure. Another labeling procedure then successively modifies the dual node-clique set, so that more and more edges are covered, i.e., the (primal) infeasibility of the solution is gradually reduced, while integrality and dual feasibility are preserved. When this cannot be continued, the problem is partitioned and the procedure applied to the resulting subproblems. While the steps of the algorithm correspond to sequences of dual simplex pivots, these are carried out implicitly, by labeling. The procedure is illustrated by examples, and some early computational experience is reported. We conclude with a discussion of potential improvements and extensions.     

Optimizing the allocation of components to kits in small-lot,multiechelon assembly systems

The kitting problem in multiechelon assembly systems is to allocate on-hand stock and anticipated future deliveries to kits so that cost is minimized. This article structures the kitting problem and describes several preprocessing methods that are effective in refining the formulation. The model is resolved using an optimizing approach based on Lagrangian relaxation, which yields a separable problem that decomposes into a subproblem for each job. The resulting subproblems are resolved using a specialized dynamic programming algorithm, and computational efficiency is enhanced by dominance properties devised for that purpose. The Lagrangian problem is resolved effectively using subgradient optimization and a specialized branching method incorporated in the branch-and-bound procedure. Computational experience demonstrates that the specialized approach outperforms the general-purpose optimizer OSL. The new solution approach facilitates time-managed flow control, prescribing kitting decisions that promote cost-effective performance to schedule. © 1994 John Wiley & Sons. Inc.     

A finite algorithm for concave minimization over a polyhedron

We present a new algorithm for solving the problem of minimizing a nonseparable concave function over a polyhedron. The algorithm is of the branch-and-bound type. It finds a globally optimal extreme point solution for this problem in a finite number of steps. One of the major advantages of the algorithm is that the linear programming subproblems solved during the branch-and-bound search each have the same feasible region. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some preliminary computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several bilinear programming problems with the code.     

An algorithm and new penalties for concave integer minimization over a polyhedron

We present a branch-and-bound algorithm for globally minimizing a concave function over linear constraints and integer variables. Concave cost functions and integer variables arise in many applications, such as production planning, engineering design, and capacity expansion. To reduce the number of subproblems solved during the branch-and-bound search, we also develop a framework for computing new and existing penalties. Computational testing indicates that penalties based on the Tuy cutting plane provide large decreases in solution time for some problems. A combination of Driebeek-Tomlin and Tuy penalties can provide further decreases in solution time. © 1994 John Wiley & Sons, Inc.     

Geometric programming with multiplicative slack variables

A posynomial geometric programming problem formulated so that the number of objective function terms is equal to the number of primal variables will have a zero degree of difficulty when augmented by multiplying each constraint term by a slack variable and including a surrogate constraint composed of the product of the slack variables, each raised to an undetermined negative exponent or surrogate multiplier. It is assumed that the original problem is canonical. The exponents in the constraint on the product of the slack variables must be estimated so that the associated solution to the augmented problem, obtained immediately, also solves the original problem. An iterative search procedure for finding the required exponents, thus solving the original problem, is described. The search procedure has proven quite efficient, often requiring only two or three iterations per degree of difficulty of the original problem. At each iteration the well-known procedure for solving a geometric programming problem with a zero degree of difficulty is used and so computations are simple. The solution generated at each iteration is optimal for a problem which differs from the original problem only in the values of some of the constraint coefficients, so intermediate solutions provide useful information.     

Coordinated replenishments from multiple suppliers with price discounts

In this study we present an integer programming model for determining an optimal inbound consolidation strategy for a purchasing manager who receives items from several suppliers. The model considers multiple suppliers with limited capacity, transportation economies, and quantity discounts. We propose an integrated branch and bound procedure for solving the model. This procedure, applied to a Lagrangean dual at every node of the search tree, combines the subgradient method with a primal heuristic that interact to change the Lagrangean multipliers and tighten the upper and lower bounds. An enhancement to the branch and bound procedure is developed using surrogate constraints, which is found to be beneficial for solving large problems. We report computational results for a variety of problems, with as many as 70,200 variables and 3665 constraints. Computational testing indicates that our procedure is significantly faster than the general purpose integer programming code OSL. A regression analysis is performed to determine the most significant parameters of our model. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 579–598, 1998     

Computational results with a branch-and-bound algorithm for the general knapsack problem

In this paper, a branch-and-bound procedure is presented for treating the general knapsack problem. The fundamental notion of the procedure involves a variation of traditional branching strategies as well as the incorporation of penalties in order to improve bounds. Substantial computational experience has been obtained, the results of which would indicate the feasibility of the procedure for problems of large size.     

An exact branch-and-bound procedure for the quadratic-assignment problem

The quadratic-assignment problem is a difficult combinatorial problem which still remains unsolved. In this study, an exact branch-and-bound procedure, which is able to produce optimal solutions for problems with twelve facilities or less, is developed. The method incorporates the concept of stepped fathoming to reduce the effort expended in searching the decision trees. Computational experience with the procedure is presented.     

Balancing a one‐way corridor capacity and safety‐oriented reliability: A stochastic optimization approach for metro train timetabling

In urban rail transit systems of large cities, the headway and following distance of successive trains have been compressed as much as possible to enhance the corridor capacity to satisfy extremely high passenger demand during peak hours. To prevent train collisions and ensure the safety of trains, a safe following distance of trains must be maintained. However, this requirement is subject to a series of complex factors, such as the uncertain train braking performance, train communication delay, and driver reaction time. In this paper, we propose a unified mathematical framework to analyze the safety‐oriented reliability of metro train timetables with different corridor capacities, that is, the train traffic density, and determine the most reliable train timetable for metro lines in an uncertain environment. By employing a space‐time network representation in the formulations, the reliability‐based train timetabling problem is formulated as a nonlinear stochastic programming model, in which we use 0‐1 variables to denote the time‐dependent velocity and position of all involved trains. Several reformulation techniques are developed to obtain an equivalent mixed integer programming model with quadratic constraints (MIQCP) that can be solved to optimality by some commercial solvers. To improve the computational efficiency of the MIQCP model, we develop a dual decomposition solution framework that decomposes the primal problem into several sets of subproblems by dualizing the coupling constraints across different samples. An exact dynamic programming combined with search space reduction strategies is also developed to solve the exact optimal solutions of these subproblems. Two sets of numerical experiments, which involve a relatively small‐scale case and a real‐world instance based on the operation data of the Beijing subway Changping Line are implemented to verify the effectiveness of the proposed approaches.     

A branch-and-bound algorithm for solving fixed charge problems

Numerous procedures have been suggested for solving fixed charge problems. Among these are branch-and-bound methods, cutting plane methods, and vertex ranking methods. In all of these previous approaches, the procedure depends heavily on the continuous costs to terminate the search for the optimal solution. In this paper, we present a new branch-and-bound algorithm that calculates bounds separately on the sum of fixed costs and on the continuous objective value. Computational experience is shown for various standard test problems as well as for randomly generated problems. These test results are compared to previous procedures as well as to a mixed integer code. These comparisons appear promising.     

An algorithm for 0-1 multiple-knapsack problems

The 0-1 multiple-knapsack problem is an extension of the well-known 0-1 knapsack problem. It is a problem of assigning m objects, each having a value and a weight, to n knapsacks in such a way that the total weight in each knapsack is less than its capacity limit and the total value in the knapsacks is maximized. A branch-and-bound algorithm for solving the problem is developed and tested. Branching rules that avoid the search of redundant partial solutions are used in the algorithm. Various bounding techniques, including Lagrangean and surrogate relaxations, are investigated and compared.     

An easy solution for a special class of fixed charge problems

The fixed charge problem is a mixed integer mathematical programming problem which has proved difficult to solve in the past. In this paper we look at a special case of that problem and show that this case can be solved by formulating it as a set-covering problem. We then use a branch-and-bound integer programming code to solve test fixed charge problems using the setcovering formulation. Even without a special purpose set-covering algorithm, the results from this solution procedure are dramatically better than those obtained using other solution procedures.     

A streamlined simplex approach to the singly constrained transportation problem

A primal simplex procedure is developed to solve transportation problems with an arbitrary additional linear constraint. The approach is a specialization of the Double Reverse Method of Charnes and Cooper. Efficient procedures for pricing-out the basis, determining representations, and implementing the change of basis are presented. These procedures exploit the pure transportation substructure in such a manner that full advantage may be taken of the computational schemes and list structures used to store and update the basis in codifying the MODI method. Furthermore, the pricing-out and change-of-basis procedures are organized in a manner that permits the calculations for one to be utilized in the other. Computational results are presented which indicate that this method is at least 50 times faster than the state-of-the-art LP code, APEX-III. Methods for obtaining basic primal “feasible” starts and “good” feasible integer solutions are also presented.     

Capacity improvement,penalties, and the fixed charge transportation problem

Capacity improvement and conditional penalties are two computational aides for fathoming subproblems in a branch‐and‐bound procedure. In this paper, we apply these techniques to the fixed charge transportation problem (FCTP) and show how relaxations of the FCTP subproblems can be posed as concave minimization problems (rather than LP relaxations). Using the concave relaxations, we propose a new conditional penalty and three new types of capacity improvement techniques for the FCTP. Based on computational experiments using a standard set of FCTP test problems, the new capacity improvement and penalty techniques are responsible for a three‐fold reduction in the CPU time for the branch‐and‐bound algorithm and nearly a tenfold reduction in the number of subproblems that need to be evaluated in the branch‐and‐bound enumeration tree. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 341–355, 1999     

Cyclic scheduling in flow lines: Modeling observations,effective heuristics and a cycle time minimization procedure

In this paper we address the cyclic scheduling problem in flow lines. We develop a modeling framework and an integer programming formulation of the problem. We subsequently present exact and approximate solution procedures. The exact solution procedure is a branch-and-bound algorithm which uses Lagrangian and station-based relaxations of the integer programming formulation of the problem as the lower bounding method. Our heuristic procedures show a performance superior to the available ones in the literature. Finally, we address the stability issue in cyclic scheduling, demonstrate its relationship to the work-in-progress inventory control of a flow line, and present a very simple procedure to generate stable schedules in flow lines. © 1996 John Wiley & Sons, Inc.     

An efficient primal approach to bottleneck transportation problems

This article addresses bottleneck linear programming problems and in particular capacitated and constrained bottleneck transportation problems. A pseudopricing procedure based on the poly-ω procedure is used to facilitate the primal simplex procedure. This process allows the recent computational developments such as the Extended Threaded Index Method to be applied to bottleneck transportation problems. The impact on problem solution times is illustrated by computational testing and comparison with other current methods.     

Solving the generalized knapsack problem with variable coefficients

In this article we present methods based on Lagrangian duality and decomposition techniques for the generalized knapsack problem with variable coefficients. The Lagrangian dual is solved with subgradient optimization or interval bisection. We also describe a heuristic that yields primal feasible solutions. Combining the Lagrangian relaxation with a primal (Benders) subproblem yields the subproblem phase in cross decomposition. By using averages in this procedure, we get the new mean-value cross-decomposition method. Finally, we describe how to insert this into a globally convergent generalized Benders decomposition framework, in the case that there is a duality gap. Encouraging computational results for the optimal generating unit commitment problem are presented. © 1996 John Wiley & Sons, Inc.     

Dual‐ascent and primal heuristics for production‐assembly‐distribution system design

This article proposes two dual‐ascent algorithms and uses each in combination with a primal drop heuristic embedded within a branch and bound framework to solve the uncapacitated production assembly distribution system (i.e., supply chain) design problem, which is formulated as a mixed integer program. Computational results indicate that one approach, which combines primal drop and dual‐ascent heuristics, can solve instances within reasonable time and prescribes solutions with gaps between the primal and dual solution values that are less than 0.15%, an efficacy suiting it for actual large‐scale applications. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2013