Remarks on a difficult test problem for quadratic boolean programming

We show that a “difficult” example is only difficult for special kinds of algorithms     

A lift-and-project cutting plane algorithm for mixed 0–1 programs

We propose a cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.The research underlying this report was supported by National Science Foundation Grant #DDM-8901495 and Office of Naval Research Contract N00014-85-K-0198.     

A Branch and Bound algorithm for the minimax regret spanning arborescence

The paper considers the problem of finding a spanning arborescence on a directed network whose arc costs are partially known. It is assumed that each arc cost can take on values from a known interval defining a possible economic scenario. In this context, the problem of finding the spanning arborescence which better approaches to that of minimum overall cost under each possible scenario is studied. The minimax regret criterion is proposed in order to obtain such a robust solution of the problem. As it is shown, the bounds on the optimal value of the minimax regret optimization problem obtained in a previous paper, can be used here in a Branch and Bound algorithm in order to give an optimal solution. The computational behavior of the algorithm is tested through numerical experiments. This research has been supported by the Spanish Ministry of Education and Science and FEDER Grant No. MTM2006-04393 and by the European Alfa Project, “Engineering System for Preparing and Making Decisions Under Multiple Criteria”, II-0321-FA.     

A Boolean Penalty Method for Zero-One Nonlinear Programming

We introduce a discrete penalty called Boolean Penalty to 0–1 constrained nonlinear programming (PNLC-01). The main importance of this Penalty function are its properties which allow us to develop algorithms for the PNLC-01 problem. Optimality conditions, and numerical results are presented.     

A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem

In this article, we present and validate a simplicial branch and bound duality-bounds algorithm for globally solving the linear sum-of-ratios fractional program. The algorithm computes the lower bounds called for during the branch and bound search by solving ordinary linear programming problems. These problems are derived by using Lagrangian duality theory. The algorithm applies to a wide class of linear sum-of-ratios fractional programs. Two sample problems are solved, and the potential practical and computational advantages of the algorithm are indicated.     

A branch and bound algorithm for the maximum diversity problem

This article begins with a review of previously proposed integer formulations for the maximum diversity problem (MDP). This problem consists of selecting a subset of elements from a larger set in such a way that the sum of the distances between the chosen elements is maximized. We propose a branch and bound algorithm and develop several upper bounds on the objective function values of partial solutions to the MDP. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the medium-sized instances (with 50 elements) as well as some large-sized instances (with 100 elements). We compare our method with the best previous linear integer formulation solved with the well-known software Cplex. The comparison favors the proposed procedure.     

An efficient envelope-based Branch and Bound algorithm for non-convex combined heat and power production planning

Combined heat and power (CHP) production is universally accepted as one of the most energy-efficient technologies to produce energy with lower fuel consumption and fewer emissions. In CHP technology, heat and power generation follow a joint characteristic. Traditional CHP production is usually applied in backpressure plants, where the joint characteristic can often be represented by a convex model. Advanced CHP production technologies such as backpressure plants with condensing and auxiliary cooling options, gas turbines, and combined gas and steam cycles may require non-convex models. Cost-efficient operation of a CHP system can be planned using an optimization model based on forecasts for heat load and power price. A long-term planning model decomposes into thousands of single-period models, which can be formulated in the convex case as linear programming (LP) problems, and in the non-convex case as mixed integer programming (MIP) problems.     

NP-Completeness of the linear complementarity problem

We consider the linear complementarity problem (q, M) for which the data are the integer column vectorq εR ⁿ and the integer square matrixM of ordern. GLCP is the decision problem: Does (q, M) have a solution? We show that GLCP is NP-complete in the strong sense.     

A Convex Envelope Formula for Multilinear Functions

Convex envelopes of multilinear functions on a unit hypercube arepolyhedral. This well-known fact makes the convex envelopeapproximation very useful in the linearization of non-linear 0–1programming problems and in global bilinear optimization. This paperpresents necessary and sufficient conditions for a convex envelope to be apolyhedral function and illustrates how these conditions may be used inconstructing of convex envelopes. The main result of the paper is a simpleanalytical formula, which defines some faces of the convex envelope of amultilinear function. This formula proves to be a generalization of the wellknown convex envelope formula for multilinear monomial functions.     

A note on the convergence of an algorithm for nonconvex programming problems

A strong convergence theorem is proven to hold for the general algorithm of the branch and bound type for solving nonconvex programming problems given in [1].     

A comparison of two dual-based procedures for solving the p-median problem

We compare two dual-based procedures for solving the p-median problem. They rely upon alternative Lagrangean relaxations of the problem. We describe the algorithms and report on our computational experiments.     

LaGO: a (heuristic) Branch and Cut algorithm for nonconvex MINLPs

We present a Branch and Cut algorithm of the software package LaGO to solve nonconvex mixed-integer nonlinear programs (MINLPs). A linear outer approximation is constructed from a convex relaxation of the problem. Since we do not require an algebraic representation of the problem, reformulation techniques for the construction of the convex relaxation cannot be applied, and we are restricted to sampling techniques in case of nonquadratic nonconvex functions. The linear relaxation is further improved by mixed-integer-rounding cuts. Also box reduction techniques are applied to improve efficiency. Numerical results on medium size test problems are presented to show the efficiency of the method.     

A generalized knapsack problem with variable coefficients

The ordinary knapsack problem is to find the optimal combination of items to be packed in a knapsack under a single constraint on the total allowable resources, where all coefficients in the objective function and in the constraint are constant.In this paper, a generalized knapsack problem with coefficients depending on variable parameters is proposed and discussed. Developing an effective branch and bound algorithm for this problem, the concept of relaxation and the efficiency function introduced here will play important roles. Furthermore, a relation between the algorithm and the dynamic programming approach is discussed, and subsequently it will be shown that the ordinary 0–1 knapsack problem, the linear programming knapsack problem and the single constrained linear programming problem with upper-bounded variables are special cases of the interested problem. Finally, practical applications of the problem and its computational experiences will be shown.     

Unconstrained 0–1 nonlinear programming: A nondifferentiable approach

The purpose of this paper is to give new formulations for the unconstrained 0–1 nonlinear problem. The unconstrained 0–1 nonlinear problem is reduced to nonlinear continuous problems where the objective functions are piecewise linear. In the first formulation, the objective function is a difference of two convex functions while the other formulations lead to concave problems. It is shown that the concave problems we obtain have fewer integer local minima than has the classical concave formulation of the 0–1 unconstrained 0–1 nonlinear problem.     

A survey for the quadratic assignment problem

The quadratic assignment problem (QAP), one of the most difficult problems in the NP-hard class, models many real-life problems in several areas such as facilities location, parallel and distributed computing, and combinatorial data analysis. Combinatorial optimization problems, such as the traveling salesman problem, maximal clique and graph partitioning can be formulated as a QAP. In this paper, we present some of the most important QAP formulations and classify them according to their mathematical sources. We also present a discussion on the theoretical resources used to define lower bounds for exact and heuristic algorithms. We then give a detailed discussion of the progress made in both exact and heuristic solution methods, including those formulated according to metaheuristic strategies. Finally, we analyze the contributions brought about by the study of different approaches.     

A multi-level search strategy for the 0-1 Multidimensional Knapsack Problem

We propose an exact method based on a multi-level search strategy for solving the 0-1 Multidimensional Knapsack Problem. Our search strategy is primarily based on the reduced costs of the non-basic variables of the LP-relaxation solution. Considering that the variables are sorted in decreasing order of their absolute reduced cost value, the top level branches of the search tree are enumerated following Resolution Search strategy, the middle level branches are enumerated following Branch & Bound strategy and the lower level branches are enumerated according to a simple Depth First Search enumeration strategy. Experimentally, this cooperative scheme is able to solve optimally large-scale strongly correlated 0-1 Multidimensional Knapsack Problem instances. The optimal values of all the 10 constraint, 500 variable instances and some of the 30 constraint, 250 variable instances of the OR-Library were found. These values were previously unknown.     

A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints

This paper deals with the problem of locating at minimum total costs both plants and warehouses in a two-level distribution system where commodities are delivered from plants to customers either directly or indirectly via warehouses. Some side-constraints are imposed on the problem, which represent the adjunct relationship of some warehouses to a certain plant. Proposed is an efficient branch and bound solution procedure, employing a set of new devices for lower bounds and simplifications which are obtained by exploiting the submodularity of the objective function and the special structure of the side-constraints. Computational experiments with fifteen test problems are provided.     

A level-2 reformulation–linearization technique bound for the quadratic assignment problem

This paper studies polyhedral methods for the quadratic assignment problem. Bounds on the objective value are obtained using mixed 0–1 linear representations that result from a reformulation–linearization technique (rlt). The rlt provides different “levels” of representations that give increasing strength. Prior studies have shown that even the weakest level-1 form yields very tight bounds, which in turn lead to improved solution methodologies. This paper focuses on implementing level-2. We compare level-2 with level-1 and other bounding mechanisms, in terms of both overall strength and ease of computation. In so doing, we extend earlier work on level-1 by implementing a Lagrangian relaxation that exploits block-diagonal structure present in the constraints. The bounds are embedded within an enumerative algorithm to devise an exact solution strategy. Our computer results are notable, exhibiting a dramatic reduction in nodes examined in the enumerative phase, and allowing for the exact solution of large instances.     

PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem

This paper deals with the generalized resource-constrained project scheduling problem (GRCPSP) which extends the well-known resource-constrained project scheduling problem (RCPSP) by considering job specific release and due dates, non-negative minimum start-to-start time lags as well as time-varying resource availabilities. The structure of the project is represented by an acyclic network diagram. Though the extensions are of high practical importance, only a few exact solution procedures have been presented in the literature so far. Therefore, a new exact procedure PROGRESS is developed which includes new dominance rules as well as enhancements of existing ones. For evaluating the efficiency experimentally, new GRCPSP instances with 30 and 60 jobs are considered which extend the standard benchmark sets for the RCPSP generated by ProGen. PROGRESS shows superior performance when applied to the GRCPSP and is also very competitive in comparison to approaches proposed for the RCPSP.     

Hyperbolic 0–1 programming and query optimization in information retrieval

Unconstrained hyperbolic 0–1 programming can be solved in linear time when the numerator and the denominator are linear and the latter is always positive. It is NP-hard, and finding an approximate solution with a value equal to a positive multiple of the optimal one is also NP-hard, if this last hypothesis does not hold. Determining the optimal logical form of a query in information retrieval, given the attributes to be used, can be expressed as a parametric hyperbolic 0–1 program and solved in O(n logn) time, wheren is the number of elementary logical conjunctions of the attributes. This allows to characterize the optimal queries for the Van Rijsbergen synthetic criterion.This research was done in part during a visit of the first author to the Pontifical Catholic University of Rio de Janeiro in July and August 1987, sponsored by CNPq. It was also supported in part by grants 0271 and 0066 of the AFOSR to Rutgers University. The second author was with Centro de Análise de Sistemas Navais, Rio de Janeiro.