The University of Iowa

Abstracts of Refereed Publications

1. Bricker, D.L., "Reformulation of Special Ordered Sets for Implicit Enumeration Algorithms with Applications in Nonconvex Separable Programming", AIIE Transactions, Vol. 9 (1977), pp. 195-203.
   Abstract: Special Ordered Sets (SOSs) of variables of types 1 and 2 are used in mathematical programming for formulating both multiple choice problems and nonconvex separable problems, respectively. This paper suggests problem formulations which may be more efficiently solved by mixed-integer programming codes when special codes for handling SOSs are unavailable. A shipment planning problem is used to illustrate some of these formulation.
   
2. Bricker, D.L., and Chang, T.S., "A Surrogate Dual for the Simple Plant Location Problem", SCIMA, Vol. 7 (1978), pp. 13-36. Click here to download this working paper in .pdf format.
   Abstract: While Lagrangian duality is quite well-known, surrogate duality remains relatively obscure, because computation of its solution is generally quite difficult. In this paper, we derive a surrogate dual for the simple (uncapacitated) plant location problem. Use of the lower bound provided by the surrogate dual value to fathom a branch and bound algorithm does not, however, require an explicit solution of the surrogate dual. Rather, it is shown that its effectiveness in fathoming a subproblem may be determined by a test of a rather simple inequality. Computational experience is reported, showing that, for a majority of the subproblems tested, the surrogate dual is stronger than the simple (weak) linear programming bound which has often been used in branch and bound algorithms for this problem, although not competitive with the stronger linear programming bound now being used very effectively in "state-of-the-art" algorithms.
   
3. Bricker, D.L., "Bounding Linearly-Constrained Concave Minimization Problems via the Surrogate Dual", Mathematical Programming,, Vol. 18 (1980), pp. 68-83.
   Abstract: We consider a class of problems of resource allocation under economies of scale, namely that of minimizing a lower semicontinuous, isotone, and explicitly quasiconcave cost function subject to linear constraints. An important class of algorithms for the linearly constrained minimization of nonconvex cost functions utilize the branch and bound approach, using convex underestimating cost functions to compute the lower bounds. We suggest instead the use of the surrogate dual problem to bound subproblems. We show that the success of the surrogate dual in fathoming subproblems in a branch and bound algorithm may be determined without directly solving the surrogate dual itself, but that a simple test of the feasibility of a certain linear system of inequalities will suffice. This test is interpreted geometrically and used to characterize the extreme points and extreme rays of the optimal value function's level sets.
   
4. Bricker, D.L., and Rajgopal, J., "Yet Another Geometric Programming Dual Algorithm", Operations Research Letters, Vol. 2 (1983), pp. 177-180.
   Abstract: We describe an algorithm for the geometric programming dual problem which uses an adaptation of the generalized LP algorithm, proposed by Dantzig et al. twenty-five years ago for the chemical equilibrium problem, and show that slack primal constraints pose no numerical difficulties for this algorithm as they do for previous dual-based algorithms.
   
5. Raz, T. and D.L. Bricker, "Sequencing of Imperfect Inspection Operations Subject to Constraints on the Quality of Accepted and Rejected Units", International Journal of Production Research, Vol. 25 (1987), pp. 809-821.
   Abstract: Several imperfect inspection operations are available in a discrete production environment. A decision regarding acceptance or rejection of the produced items needs to be made without exceeding specified limits for the probabilities of accepted units being non-conforming and rejected units conforming to quality specifications. A branch and bound approach is used to find the inspection sequence resulting in least expected total inspection cost. Following the heuristic construction of a trial solution, a dominance relationship is applied to search the tree of possible sequences for the optimal sequence. A numerical example is included.
   
6. Nyman, J. and D. L. Bricker, "Profit Incentives and Technical Efficiency in the Production of Nursing Home Care", Review of Economics and Statistics, Vol. (1989), pp. 586-594.
   Abstract: In recent years, nursing home care expenditures have approached 1% of GNP. Their growth is a major contributor to the escalating costs of health care. In this article, we analyze a sample of nursing homes from Wisconsin to determine the characteristics of the efficiently operated nursing homes. Data environment analysis is used to calculate efficiency scores for the various nursing homes in the sample. We then use regression analysis to investigate the determinants of efficiency, holding constant the characteristics of the output. We find that for-profit firms have significantly higher efficiency scores.
   
7. Nyman, J., D. L. Bricker and D. Link, "Technical Efficiency in Nursing Homes", Medical Care, Vol. 28 (1990), pp. 541-551.
   Abstract:
   
8. Rajgopal, J. and D. L. Bricker, "Posynomial Geometric Programming as a Special Case of Semi-Infinite Linear Programming", Journal of Optimization Theory and Applications,, Vol. 66 (1990), pp. 455-475.
   Abstract: This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algortihms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.
   
9. Lin, E. Y. H. and D. L. Bricker, "Implementing the Recursive APL Code for Dynamic Programming", APL90 Conference Proceedings, Copenhagen, 1990, pp. 239-250.
   Abstract: Despite the importance and wide applicability of dynamic programming technique in optimization, the complexity and uniqueness of various dynamic programming models often make the comprehension of their solution procedures difficult, particularly for a novice. Although it can be aruged that, unlike the Simplex method in linear programming, no general dynamic programming algortihm exists, with the recursive capability of APL, it is feasible to develop a "systematic" solution approach for deterministic dynamic programming. In this paper, we introduce a set of such APL code developed to solve various types of dynamic programming problems with minor modificaitons on some of its key functions to accommodate the nature of each type of dynamic programming problems.
   
10. Lin, E. Y. H. and D. L. Bricker, "On the Calculation of True and Pseudo Penalties in Multiple Choice Integer Programming". European Journal of Operational Research, Vol. 55 (1991) pp. 228-236.
    Abstract: The general solution approach leading to the global optimum for multiple choice integer programming uses the branch-and-bound procedure designed for special ordered sets. Incorporated in such a solution procedure, the partitioning strategy based on a weighted mean method is most often adopted to calculate the pseudo penalties on the partitioned subconstraints for branching and backtracking. Based on a reformulation and transformation technique, we show that the calculation of true penalties on these partitioned subconstraints can be performed efficiently.
    
11. Raz, T. and D. L. Bricker, "Optimal and Heuristic Solutions to the Variable Inspection Policy Problem", Computers and Operations Research, Vol. 18 (1990), pp. 115-123
    Abstract: This paper presents optimal and heuristic methods for finding the variable inspection policy that minimizes expected total cost per unit. These methods utilize a recursive function to compute the minimum remaining cost over all policies that begin with the given inspection sequence. The results of an exploratory experiment suggest that the best performance, in terms of reduction in computational effort relative to deviation from the optimum, is obtained with adaptive heuristics, where the number of inspection operations considered for addition to a given sequence varies with the position in the sequence. A sensitivity analysis indicates that the optimal and heeuristic procedures are not sensitive to variations in the incoming fraction nonconforming.
    
12. Yu, K.-Y. and D. L. Bricker, "Analysis of a Markov Chain Model of a Multistage Manufacturing System with Inspection, Rejection, and Rework", Industrial Engineering Transactions, Vol. 25, 109-112.
    Abstract: Absorption analysis is applied to a Markov chain model of a multistage manufacturing process with inspection and reworking.
    
13. Bricker, D.L., J.C. Choi, and J. Rajgopal, "On Geometric Programming Problems Having Negative Degrees of Difficulty", European Journal of Operational Research, Vol. 68 (1993), pp. 427-430.
    Abstract: The dual of a geometric programming problem with negative degree of difficulty is often infeasible. It has been suggested that such problems be solved by finding a dual "approximate" solution which minimizes a measure of the infeasibility, e.g., the summed squares of the infeasibilities in the dual constraints. We point out the shortcomings in that approach, and suggest a simple technique to ensure dual feasibility, namely the addition of a constant term to the primal objective.
    
14. Rajgopal, J., and D.L. Bricker, "On Subsidiary Problems in Geometric Programming", European Journal of Operational Research, 63 (1992), pp. 102-113.
    Abstract: When a dual-based procedure is used to solve a geometric programming problem, the presence of inactive constraints at the primal optimum reduces the amount of information available about the relationship between the optimal primal and dual vectors. In certain situations one must resort to solving one or more subsidiary problems to recover solution from the dual optimum. This paper reviews such situations and presents an alternative formulation of the dual as a generalized linear program, along with a column generation algorithm based on the same. The algorithm avoids subsidiary problems, and the formulation provides more information than the traditional dual when recovering the primal optimum.
    
15. Raz, T. and D.L. Bricker, "Sequencing of Inspection Operations Subject to Errors", European Journal of Operational Research, Vol. 68 (1993), pp. 251-264.
    Abstract: The problem of sequencing inspection operations subject to errors in order to minimize the expected sum of inspection and penalty costs is formulated. Three basically different types of sequences (complete, fixed and variable) are defined. The paper presents methods for computing the optimal solution for each type, and a family of heuristics for the variable sequence problem. These methods are based on a branch and bound approach and involve recursive calls to a sequence evaluation function.
    
16. Bricker, D. L., and Lin, E. Y.-H. , "Teaching Dynamic Programming Using APL", International Journal of Mathematical Education in Science and Technology, Vol. 23 (1993), pp. 433-444.
    Abstract: Unlike most other algorithms in optimization, such as the Simplex method in linear programming, dynamic programming is generally considered to be an approach to viewing an optimization problem rather than an algorithm which provides a step-by-step solution procedure converging to the optimum. This specificity of the dynamic programming technique often confuses its users both in classroom and in practice. In this paper we illustrate how this difficulty can be overcome with the aid of APL (A Programming Language).
    
17. Bricker, Dennis L. and JaeChul Choi, "Obtaining a Feasible Geometric Programming Primal Solution, Given a Near-Optimal Dual Solution", Engineering Optimization, Vol.23 (1995), pp. 323-331.
    Abstract: A dual algorithm applied to a posynomial geometric programming probelm generally terminates with a dual feasible solution which is only approximately optimal. The usual methods for recovering the primal solution then yields solutions with corresponding slight infeasibilities in the primal constraints. This paper demonstrates a linear programming problem for computation fo a primal solution which is strictly feasible.
    
18. Choi, Jae-Chul and Dennis L. Bricker, "Geometric Programming with Several Discrete Variables: Algorithms Employing Generalized Benders' Decomposition", Engineering Optimization, Vol. 25 (1995), pp. 201-212.
    Abstract: Geometric programming problems in which several of the variables are restricted to assume either integer values or one of a set of standard sizes are known as Semi-Discrete Geometric Programming problems. In this paper several variations of Generalized Benders' Decomposition are described for these problems and some computational experience is presented.
    
19. Hsieh, Yi-Chih, and Dennis L. Bricker, "New Infeasible Interior Point Algorithm Based on Monomial Method", Computers & Operations Research, Vol. 23 (1996), pp. 653-666.
    Abstract: We propose a new infeasible path-following algorithm for convex linearly-constrained quadratic programming problem. This algorithm utilizes the monomial method rather than Newton's method for solving the KKT equations at each iteraiton. As a result, the sequence of iterates generated by this new algorithm is infeasible in the primal and dual linear constraints, but, unlike the sequence of iterates generated by other path-following algorithms, does satisfy the complementarity equations. Performance of this new algortihm is demonstrated by the results of solving QP problems (both separable and nonseparable) which are constructed so as to have known optimal solutions. Additionally, results of solving continuous quadratic knapsack problems indicate that for problems of a given size, the computational time of this new algorithm is less variable than other algorithms.
    
20. Lin, E. Y.-H. and Bricker, D.L., "Computational Comparison on the Partitioning Strategies in Multiple Choice Integer Programming", European Journal of Operational Research, Vol. 88 (1996), pp. 182-292.
    Abstract: In this paper we review the theoretical background of two partitioning strategies, the Weighted-Mean-Method (WMM) and the Reformulation-and-Transformation-Technique (RTT), incorporated in the special ordered set branch-and-bound procedures leading to the global optimum in Multiple Choice Integer Programming (MCIP). Prodedure flow is developed with a numerical example presented to illustrate the effect of these two partitioning strategies in the algorithm. This procedure flow is then coded using IBM APL2. A total of 24 test problems are solved by this APL2 code for MCIP to analyze the performance of WMM and RTT in MCIP. The preliminary computational results indicate that, on the average, RTT produces smaller branching trees than does WMM. Its performance tends to be better for those MCIP problems having more multiple choice sets and a fewer average number of variables in each set. However, the average CPU time consumed by using RTT does not differ much from that consumed by using WMM.
    
21. Choi, J. C. and D. L. Bricker , "Effectiveness of Geometric Programming Algorithms for Optimization of Machining Economics Models", Computers & Operations Research, Vol. 23 (1996), No. 10, pp. 957-961.
    Abstract: Machining economics problems usually contain highly non-linear equations which may present difficulties for some non-linear programming algorithms. An earlier article by Duffuaa et al. [1] compared the performance of several non-linear programming algorithms, including a geometric programming algorithm, applied to five machining economics problems. Those authors concluded that the Generalized Reduced Gradient (GRG) algorithm is the most suitable mthod for solving such problems. In this paper, we point out shortcomings in that conclusion and demonstrate the effectiveness of the Geometric Programming technique in such problems compared with the results of GRG which were presented.
    
22. Choi, JaeChul, and Dennis L. Bricker, "A Heuristic Procedure for Rounding Posynomial Geometric Programming Solutions to Discrete Values", Computers & Industrial Engineering Vol. 30 (1996), No. 4, pp. 623-629.
    Abstract: While geometric programming is a useful computational approach for engineering design problems, it is often the case that some design variables specifying sizes must be rounded to readily available standard sizes, or variables specifying the number of component parts must be rounded to integers. To assist in deciding whether to round these variables up or down to the discrete admissible values, we present a technique to estimate the respective penalties which would be incurred.
    
23. Sohn, Han-Suk, Dennis Bricker, J. Richard Simon, and Yi-Chih Hsieh, "Optimum Sequences of Trials for Balancing Practice and Repetition Effects". (to appear in Behavior Research Methods, Instruments, and Computers) Click here for additional information and listings of such sequences.
    Abstract: This paper describes procedures for generating trial sequences to balance out practice effects and intertrial repetition effects in experiments consisting of repeated trials. In the sequences presented, each stimulus appears an equal number of times, is preceded equally often by itself and by each other stimulus and is distributed in a "balanced" manner throughout the block of trials. Two criteria for balance are employed. One criterion aims to equalize the average position of each stimulus in the sequence. The second criterion maintains, as much as possible, a uniform interval between appearances of each stimulus in the sequence. For each criterion, optimal or near-optimal sequences are presented for experiments involving from three to nine different stimulus conditions. Suggestions are included for extending (e.g., doubling or tripling) the length of the sequences.
    
24. Hsieh, Yi-Chih, and Dennis L. Bricker, "Scheduling Linearly Deteriorating Jobs on Multiple Machines", to appear in Computers & Industrial Engineering
    Abstract: This paper investigates the scheduling problems in which the job processing times do not remain constant but are increasing linear functions of their starting times. Two deteriorating scheduling models, Model 1 and Model 2, for multiple machines are considered. In this paper, we propose an efficient heuristic for Model 1 and prove that the ratio of the makespan obtained by the heuristic to the optimal makespan is bounded. For model 2, two heuristics are proposed to obtain the feasible solution; in addition, a probabilisitic search approach is used to improbe the feasible solution. Numerical results are provided to show the efficiency of the approaches in this paper.
    
25. Bricker, Dennis, K.O. Kortanek, and Lina Xu, "Maximum Likelihood Estimates with Order Restrictions on Probabilities and Odds Ratios", Journal of Applied Mathematics and Decision Sciences, volume 1, no. 1 (July 1997), pp. 53-65.
    Abstract: The problem of assigning cell probabilities to maximize a multinomial likelihood with order restrictions on the probabilies and/or restrictions on the local odds ratios is modeled as a posynomial geometric program (GP), a class of nonlinear optimization problems with a well-developed duality theory and collection of algorithms. (Local odds ratios provide a measure of association between categorical random variables.) A constrained multinomial MLE example from the literature is solved, and the quality of the solution is compared with that obtained by the iterative method of El Barmi and Dykstra, which is based upon Fenchel duality. Exploiting the proximity of the GP model of MLE problems to linear programming (LP) problems, we also describe as an alternative, in the absence of special-purpose GP software, an easily implemented successive LP approximation method for solving this class of MLE problems using one of the readily available LP solvers.
    
26. Yang, H.-H. and D. L. Bricker, “Investigation of path-following algorithms for signomial geometric programming problems.” European Journal of Operational Research Vol. 103(1997): 230-241.
    Abstract: This paper considers signomial geometric programming (GP) dual problems, a class of nonconvex nonlinear programming problems possessing multiple locally optimal solutions. The primary purpose of this paper is to investigate the quality of solutions found by use of a path-following algorithm. The path-following method may be applied to either the original nonconvex problem, or to each of a sequence of convex posynomial GP problems approximating the original problem. For each test problem, the algorithms were initiated with thousands of different starting points. It was determined that, when the stopping criterion was relaxed for early posynomial GP problems in the sequence, the ultimate solution tended to be of better quality, and more frequently globally optimal.
    
27. Hsieh, Yi-Chih, Ta-Cheng Chen, and Dennis L. Bricker, "Genetic Algorithms for Determining Redundancy in Reliability Problems", Microelectronics and Reliability, Vol. 38 (1998), pp. 1599-1605.
    Abstract: This paper presents genetic algorithms for solving various redundancy reliability problems, which include series systems, series-parallel systems and complex (bridge) systems. The objective is to maximize the system reliability by means of redundancy in the elements of the system, while maintaining feasibility with respect to three nonlinear constraints, namely, cost and weight constraints, and constraints on the products of volume and weight. Numerical examples show that the genetic algorithms perform well for all the redundancy reliability problems considered in this paper. In particular, as reported, some solutions obtained by genetic algorithms are better than previously best-known solutions.
    
28. Xu, Lina, Dennis Bricker, and K.O. Kortanek, "Bounds for Stop-Loss Premium Under Restrictions on I-Divergence" , Vol. 23 (1998), pp. 119-139.
    Abstract: Stop--Loss reinsurance contracts have attracted much attention recently. In its simplest form, the reinsurer agrees to pay all losses of the insurer in excess of an agreed --upon limit. This paper concerns the calculation of upper and lower bounds on the stop--loss premium i.e. the expected payment by the reinsurer, when the claim distribution is unknown but assumed to be in the proximity (as measured by I--divergence) of the empirical distribution of past claims. The problems of computing the upper and lower bounds on the premium are modeled as nonlinear constrained optimization problems, namely, generalized geometric programs. Simple solution procedures, based upon generalized geometric programming duality, are described and demonstrated for an example.
    
29. Sankaran, Jayaram, Dennis Bricker, and Shuw-Hwey Juang, "A Strong Fractional Cutting-Plane Algorithm for Resource-Constrained Project Scheduling", International Journal of Industrial Engineering, Vol. 6 (1999), pp. 99-111.
    Abstract: We develop and test a strong fractional cutting-plane algorithm for the classical non-preemptive precedence- and resource-constrained project scheduling problem. While our basic approach is to formulate the problem as a 0-1 IP and solve it by LP-based braqnch-and-bound, we enhance the algorithm considerably through (a) an improved IP reformulation, (b) problem preprocessing techniques, and (c) on-the-fly tightening of the LP relaxation by generating strong and valid inequalities that are violated by the current (fractional) LP optimum. Preliminary computational results on a collection of test problems are encouraging.
    
30. Kawatra, R., A. Dutta, and D. L. Bricker. “A Lagrangian based heuristic for the design of multipoint linkages in a communication network with unreliable links and node outage costs.” OPSEARCH Vol. 36(1999), pp. 218-230.
    Abstract: This paper studies the capacitated minimal spanning tree with unreliable links and node outage costs problem. Tree topologies appear in the design of centralized communication networks. In these topologies the number of nodes in a subtree rooted at the central node is limited to a predefined number due to polling, loading, and response time restrictions. The links in a communication network are prone to failure. Whenever a link in these networks fails, all the terminal nodes connected to the central node through that link are unable to communicate until the faulty link is repaired. In some networks such failures can have adverse economic effect on the network user. The economic effect on the network user due to inability of a terminal to communicate with the central node due to link failure is called node outage cost. The sum of expected yearly node outage costs for a network depends on the topology of the network. In this paper we suggest a Lagrangean based heuristic to solve the integer programming formulation of the network topology problem. The objective of the problem is to minimize the sum of link costs and node outage costs. Our computational results on a set of test data with up to 80 nodes show that compared to the previously developed greedy heuristic, our method gives solutions that are better by up to 6 percent. The gaps between our heuristic solutions and the lower bounds found as a byproduct of the solution procedure are in the 2-17 percent range.
    
31. Hsieh, Y.-C. and D. L. Bricker, "Solving obstacle problems by a new pathfollowing algorithm", Journal of Chinese Institute of Industrial Engineering Vol. 16(1999), pp. 771-780.
    Abstract: Obstacle problems are typical problems in engineering and physics. After finite approximation, the obstacle problem can be reduced to a QP problem with box constraints. In this paper, a new infeasible path-following algorithm, which follows a path on the complementarity surface, is proposed for solving obstacle problems. The sequence of iterates generated by the algorithm does not satisfy the primal-dual feasibilities as do the other path-following algorithms which follow the central path, but satisfies the complementarity equations at each iteration. In our test obstacle problems, the total number of variables for the Karush-Kuhn-Tucker equations is up to 2,5000. Limited numerical results show that this new path-following algorithm can efficiently solve such quadratic problems requiring only a few iterations.
    
32. Kawatra, R. and D. L. Bricker, "A Multiperiod Planning Model for the Capacitated Minimal Spanning Tree Problem", European Journal of Operational Research Vol. 121(2000): pp. 412-419.
    Abstract: The Multiperiod Capacitated Minimal Spanning Tree Problem (MCMSTP) consists of scheduling the installation of links in a network so as to connect a set of terminal nodes S = [2,3...N] to a central node (node 1) with minimal present value of expenditures, where link capacities limit the number of terminal nodes. Some of the terminal nodes are active at the beginning of the planning horizon while others are activated over time. We formulate this problem as an integer programming problem. A branch exchange heuristic procedure for solving the problem is presented. We also present a Lagrangian relaxation method to find a lower bound for the optimal objective function value. This lower bound may be used to estimate the quality of the solution given by the branch exchange heuristic. Experimental results over a wide range of problem structures show that the branch exchange heuristic method yields verifiably good solutions to this problem.
    
33. Jayant Rajgopal and Dennis Bricker, "An Algorithm for Posynomial Geometric Programming, Based upon Generalized Linear Programming", Computational Optimization and Applications, Vol. 21 (2002), pp. 95-109.
    Abstract: This paper revisits an efficient procedure for solving posynomial geometric programming (GP) problems, which was initially developed by Avriel et al. The procedure, which used the concept of condensation, was embedded within an algorithm for the more general (signomial) GP problem. It is shown here that a computationally equivalent dual-based algorithm may be independently derived based on some more recent work where the GP primal-dual pair was reformulated as a set of inexact linear programs. The constraint structure of the reformulation provides insight into why the algorithm is successful in avoiding all of the computational problems traditionally associated with dual-based algorithms. Test results indicate that the algorithm can be used to successfully solve large-scale geometric programming problems on a desktop computer.
    
34. Lin, E. Y.-H. and D. L. Bricker, “Connecting special ordered inequalities and transformation and reformulation technique in multiple choice programming”, Computers & Operations Research Vol. 29(2002), pp.1441-1446.
    Abstract: An article entitled: "A Note on Modeling Multiple Choice Requirements for Simple Mixed Integer Programming Solvers" was published by Ogryczak (Comput. Oper. Res. 23 (1996) 199). In this article, Ogryczak proposed a reformulation technique called special ordered inequalities (SOI) to model the non-convex programming problems with special ordered sets (SOS) of variables. The SOI technique appears to be analogous to the reformulation technique introduced by Bricker (AIIE Trans. 9 (1977) 105) and is related to the reformulation and transformation technique (RTT) developed by Lin and Bricker (Eur. J. Oper. Res. 55(2) (1991) 228); Lin and Bricker (Eur. J. Oper. Res. 88 (1996) 182). Since none of this literature was cited in the references of Ogryczak (Comput. Oper. Res. 23 (1996) 199), we would like to use this note to differentiate SOI and RTT and to elaborate their connection.
    
    In the context of non-convex programming, two major types of special ordered sets (SOS) of variables have been identified and studied by researchers. SOS1 are sets of non-negative variables where, for each set, at most one of the variables can be non-zero in the final solution. The most common application of SOS1 is multiple choice programming (MCP) which can be found in the modeling of many integer programming problems in location, distribution, scheduling, etc. SOS2 requires that, for each set, at most two of the variables can be non-zero in the final solution and, if they are, they must be adjacent. SOS2 has been widely used in separable programming to model non-linear functions using sets of piece-wise linear functions. Bricker introduced an explicit reformulation technique for SOS in 1977. Lin and Bricker developed a reformulation and transformation technique (RTT) to implicitly compose the optimal Simplex tableau for MCP in 1991. They also elaborated upon it with a computational report in 1996. Without citing the work by Bricker, or that by Lin and Bricker, Ogryczak proposed an analogous reformulation technique called special ordered inequalities (SOI) for SOS in 1996. This note aims to elaborate upon the connection between SOI and RTT as the supplementary information for the future research in SOS.
    
35. Hsieh, Yi-Chih, Sohn, Han-Suk, and Dennis Bricker, "Generating (n,2) De Bruijn Sequences with Some Balance and Uniformity Properties", Ars Combinatoria (to appear).
    Abstract: This paper presents two new algorithms for generating (n,2) de Bruijn sequences which possess certain properties. The sequences generated by the proposed algorithms may be useful for experimenters to systematically investigate intertrial repetition effects. Characteristics are compared with those of randomly sampled (n,2) de Bruijn sequences.
36. Kawatra, R. and D. L. Bricker,"Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs",European Journal of Operational Research, Vol. 156, No. 1, pp. 73-82
    Abstract: The degree-constrained minimal spanning tree (DCMST) problem with unreliable links and node outage costs consists of finding links in a network to connect a set of terminal nodes to a central node while minimizing the expected annual expenditure. The number of ports available on each terminal node limits the number of incident links (the degree constraint). Each terminal node in the network has an associated node outage cost, which is the economic cost incurred by the network user whenever that node is disabled due to failure of a link. We formulate this problem as an integer-programming problem and present a Lagrangian relaxation method which, for each choice of Lagrangian multipliers, provides a lower bound for the optimal objective function value. A subgradient optimization method is used to search for multipliers which yield good lower bounds. A branch exchange heuristic procedure makes modifications to each infeasible solution of the Lagrangian relaxation in order to find good feasible solutions. The quality of these heuristic solutions is estimated using the best obtained lower bounds. Experimental results over a wide range of problem structures show that the branch exchange heuristic method yields verifiably good solutions to this problem.
37. Sohn, Han-Suk, and Dennis Bricker, "Cross-Decomposition of the Degree-Constrained Minimum Spanning Tree Problem", Journal of Systemics, Cybernetics and Informatics, Vol. 5 (2007), No. 1, 4 pp.
    Abstract: As computer communication networks become a prevalent part in our daily life, the importance of efficient design of those networks becomes more evident. One of the critical issues in the network design process is the topological design problem involved in establishing a centralized data communication network with best performance and low costs. It can be recognized as a degree-constrained minimum spanning tree and it has been shown to be NP-hard. The degree-constrained minimum spanning tree problem commonly appears as a subproblem in the design of centralized data communication networks, and so the development of effective algorithms has received much attention in the research literature. To achieve effectiveness in solving degree-constrained minimum spanning tree, a solution algorithm based on cross-decomposition is proposed in this paper. The computational results are analyzed to demonstrate the effectiveness of the proposed algorithm. It shows a great promise in the design of centralized data communication networks.

Working Papers

1. Hsieh, Yi-Chih, and D.L. Bricker "Solving obstacle problems using a new interior point algorithm". Click here to download this working paper in .pdf format.
   Abstract: A new infeasible path-following algorithm, which follows a path on the complementarity surface, is proposed for solving obstacle problems. The sequence of iterates generated by the algorithm does not satisfy primal-dual feasibility as do the other path-following algorithms which follow the central path, but satisfy the complementarity equations at each iteration. Numerical results show that only a few iterations are required for solving this class of problems.
   
2. Jayant Rajgopal and Dennis Bricker, "An Algorithm for Posynomial Geometric Programming, Based upon Generalized Linear Programming", to appear in Mathematical Methods of Operations Research. Click here to download this working paper in .pdf format.
   Abstract: This paper describes a column generation algorithm for posynomial geometric programming which is based on Dantzig's generalized linear programming principle. The algorithm works on the dual problem and successfully avoids all the traditional computational problems associated with dual-based algorithms. Test results indicate that the algorithm is extremely robust and can be used to successfully solve large-scale geometric programming problems on a microcomputer.
   
3. Hsieh, Y.-C. and D. L. Bricker, "Solving obstacle problems by a new pathfollowing algorithm", Journal of Chinese Institute of Industrial Engineering Vol. 16(1999), pp. 771-780
   
   

   ---

4. Hsieh, Yi-Chih and Dennis L. Bricker, "Infeasible Interior Point Algorithm Following a Path on the Complementarity Surface". Click here to download this working paper in .pdf format.
   Abstract: We investigate an infeasible path-following algorithm, which follows a path on the complementarity surface, for convex linearly-constrained QP problems. That is, the sequence of iterates generated by the algorithm satisfies the complementarity equations at each iteration. An auxiliary sequence which always satisfies both primal and dual feasibility is used to prove the convergence of this algorithm.
   
5. Hsieh, Yi-Chih, and D.L. Bricker "Solving obstacle problems using a new interior point algorithm" Click here to download this working paper in .pdf format.
   Abstract: A new infeasible path-following algorithm, which follows a path on the complementarity surface, is proposed for solving obstacle problems. The sequence of iterates generated by the algorithm does not satisfy primal-dual feasibility as do the other path-following algorithms which follow the central path, but satisfy the complementarity equations at each iteration. Numerical results show that only a few iterations are required for solving this class of problems.
   
6. Xu, Lina and Dennis Bricker, "Bounds for Stop-Loss Premium Under Restrictions on the Chi-Square Statistic" Click here to download this working paper in .pdf format.
   Abstract: One type of reinsurance contract which has attracted recent attention is stop-loss reinsurance. In its simplest form, the reinsurer agrees to pay all losses of the insurer in excess of an agree-upon limit. This paper concerns the computation of bounds, both lower and upper, on the stop-loss premium when the loss distribution in unknown, but information about past claim experience is available in the form of frequencies of claims in each of a set of intervals. Placing limits on the chi-square statistic or modified chi-square statistic as measures of the proximity of the loss distribution to the empirical distribution, we use a dual approach to calculate the bounds on the premium. If the chi-square statistic is restricted, this approach requires optimizing with respect to a single dual variable. If, on the other hand, the modified chi-square statistic is restricted, the bounds are given in closed form.
   
7. Chen, Ta-Cheng, Dennis Bricker, and Soo Y. Chang, "An Application of Lagrangian Decomposition to the Scheduling of Hot Charged Rolling in Steel Production"
   Abstract: A scheduling problem for Hot Charged Rolling (HCR) in the continuous casting process, requiring both grouping and sequencing within each group, is modeled as a degree-constrained minimum spanning tree problem. This paper compares several algorithms employing Lagrangean decomposition and several heuristic methods.
   
8. Yi-Chih Hsieh and Dennis Bricker, "New Paths for Path-Following Algorithms"
   Abstract: The central path is typically followed with the use of Newton's method in solving the Karush-Kuhn-Tucker (KKT) equations for convex quadratic programming problems. Based upon a logarithmic transformation to linearize the KKT equations before applying Newton's method, a class of alternative paths are derived. As shown, these paths are similar to that obtained by using the monomial method.
   
9. Vargas, SClaudina and Dennis Bricker, "Combining DEA and factor analysis to improve evaluation of academic departments given uncertainty about the output constructs" Click here to download this working paper in .pdf format.
   Abstract: This paper combines the CCR output-oriented model of data envelopment analysis (DEA) and Factor Analysis (FA) to evaluate the performance of academic units of a university's graduate programs relative to their counterparts nationally. We propose DEA/FA as a means of increasing the utility of DEA for policy decisions when there is uncertainty about the output constructs relevant to the programs. We discuss the concept that an academic program often maximizes the levels of some constructed outputs (CO), which may not themselves be directly observable. By means of FA, these COs can be deduced from the observable outputs, and can be expressed as a linear combination of observed and random components. Using the COs lessen the caveat of extreme specialization without the requirement for value judgements.
   
10. Hsieh, Yi-Chih and Dennis L. Bricker, "Computational Experience with a New Infeasible Interior Point Algorithm"
    Abstract: We propose a new infeasible path-following algorithm, which follows a path on the complementarity surface, for convex linearly-constrained QP problems. The sequence of iterates generated by the algorithm does not satisfy the primal-dual feasibility as do the other path-following algorithms which follow the central path, but satisfies the complementarity equation at each iteration. Numerical results are reported for a discretization of obstacle problems (a class of engineering problems). In addition, tests on a set of continuous quadratic knapsack problems indicate that the variability in computation time for this new algorithm is less than that for the potential reduction algorithm or the iterative algorithm.
    
11. Techapichetvanich, K. and D. L. Bricker (1993). "Investigation of Lagrangian Heuristics for Set Covering Problems" Click here to download this working paper in .pdf format.
    Abstract: This paper presents new Lagrangian Heuristics for the set covering problem (SCP). These heuristics are designed to be embedded within an algorithm (e.g., subgradient optimization) to search for optimal Lagrangian multipliers. A Lagrangian heuristic may adjust a (perhaps infeasible) solution of a Lagrangian relaxation and/or make use of information available in the form of the Lagrangian multipliers. Such an algorithm was presented by J.E. Beasley who reported that, in computational experiments, it outperformed a number of other existing heuristic algorithms. However, his heuristic algorithm which uses only the Lagrangian relaxation solution and ignores the multipliers, worked well only for random-cost problems which may bear little resemblance to typical real world applications. We present four extensions of his algorithm designed to perform well for classes of problems which appear to be much harder to solve than Beasley's random-cost problems but which more adequately model real world problems, i.e., unicost and correlated-cost problems. (The latter class displays a positive correlation between the cost of a column and its density, i.e., the number of rows covered.) Computational results, based on problems involving 200 rows and 1000 columns, indicate that our Lagrangian heuristics do produce good-quality solutions and outperform Beasley's heuristic significantly for unicost and correlated-cost problems.
    
12. Sohn, Hansuk and D. L. Bricker, "Utilizing the Surrogate Dual Bound in Capacity Planning Under Economies of Scale" Click here to download this working paper in .pdf format.
    Abstract: Minimizing a nondecreasing separable concave cost function over a polyhedral set arises in capacity planning problems where economies of scale and fixed costs are significant, as well as production planning when a learning effect results in decreasing marginal costs. This is an NP-hard combinatorial problem in which the extreme points of the polyhedral set must be enumerated, each of them a local optimum. Branch-and-bound methods have been frequently used to solve these problems. Although it has been shown that in general the bound provided by the surrogate dual is tighter than that of the Lagrangian dual, the latter has generally been preferred because of the apparent computational intractability of the surrogate dual problem. In this paper we describe a branch-and-bound algorithm that exploits the superior surrogate dual bound in a branch-and-bound algorithm without explicitly solving the dual problem. This is accomplished by determining the feasibility of a set of linear inequalities.
    
13. Sohn, Hansuk and D. L. Bricker, "A Cross-Decomposition Scheme for Two-Stage Stochastic Linear Programming" Click here to download this working paper in .pdf format.
    Abstract: We present a new algorithm for the two-stage stochastic linear programming problem with complete recourse. This cross-decomposition algorithm employs the Benders (primal) subproblems as in the so-called L-shaped method but eliminates the Benders master problem for generating the next trial first-stage solution, relying instead upon Lagrangian (dual) subproblems. (The Lagrangian multipliers used in defining the dual subproblems are in turn obtained from the primal subproblems.) The primal subproblem separates into subproblems, one for each scenario, each containing only the second-stage variables. The dual subproblem also separates into subproblems, one for each scenario which contains both first- and second-stage variables, and additionally a subproblem containing only the first-stage variables. We then show that the substantial computational savings may be obtained by solving at most iterations only the dual subproblem with the first-stage variables and bypassing the termination test.
    
14. Bricker, D. L., "Quasi-conjugacy, Quasi-subgradients, and Surrogate Duality in Nonconvex Programming" Click here
    to download this working paper in .pdf format.
    Abstract: Conjugate functions have played an important role in the theory of convex programming. An analogous role in quasi-convex programming is played by quasi-conjugate functions. Conjugates relate to epigraph supports, whereas quasi-conjugates relate to level set supports and barriers; conjugate functions provide a baisis for Lagrangian duality, whereas quasi-conjugate functions provide a basis for surrogate duality. In this paper, we shall briefly survey the existing theory of quasi-conjugacy and surrogate duality as developed by Greenberg & Pierskalla as it relates to nonconvex programming, interpreting it geometrically, and shall then add several extensions to this theory.

to Dennis Bricker's publication page.

Last modified: 18 April 2008