From Linear to Semidefinite Programming: An Algorithm to Obtain Semidefinite Relaxations for Bivalent Quadratic Problems

In this paper, we present a simple algorithm to obtain mechanically SDP relaxations for any quadratic or linear program with bivalent variables, starting from an existing linear relaxation of the considered combinatorial problem. A significant advantage of our approach is that we obtain an improvement on the linear relaxation we start from. Moreover, we can take into account all the existing theoretical and practical experience accumulated in the linear approach. After presenting the rules to treat each type of constraint, we describe our algorithm, and then apply it to obtain semidefinite relaxations for three classical combinatorial problems: the K-CLUSTER problem, the Quadratic Assignment Problem, and the Constrained-Memory Allocation Problem. We show that we obtain better SDP relaxations than the previous ones, and we report computational experiments for the three problems.     

Multi-way clustering and biclustering by the Ratio cut and Normalized cut in graphs

In this paper, we consider the multi-way clustering problem based on graph partitioning models by the Ratio cut and Normalized cut. We formulate the problem using new quadratic models. Spectral relaxations, new semidefinite programming relaxations and linearization techniques are used to solve these problems. It has been shown that our proposed methods can obtain improved solutions. We also adapt our proposed techniques to the bipartite graph partitioning problem for biclustering.     

Restarting after Branching in the SDP Approach to MAX-CUT and Similar Combinatorial Optimization Problems

Many combinatorial optimization problems have relaxations that are semidefinite programming problems. In principle, the combinatorial optimization problem can then be solved by using a branch-and-cut procedure, where the problems to be solved at the nodes of the tree are semidefinite programs. It is desirable that the solution to one node of the tree should be exploited at the child node in order to speed up the solution of the child. We show how the solution to the parent relaxation can be used as a warm start to construct an appropriate initial dual solution to the child problem. This restart method for SDP branch-and-cut can be regarded as analogous to the use of the dual simplex method in the branch-and-cut method for mixed integer linear programming problems.     

Implicit cover inequalities

In this paper we consider combinatorial optimization problems whose feasible sets are simultaneously restricted by a binary knapsack constraint and a cardinality constraint imposing the exact number of selected variables. In particular, such sets arise when the feasible set corresponds to the bases of a matroid with a side knapsack constraint, for instance the weighted spanning tree problem and the multiple choice knapsack problem. We introduce the family of implicit cover inequalities which generalize the well-known cover inequalities for such feasible sets and discuss the lifting of the implicit cover inequalities. A computational study for the weighted spanning tree problem is reported.     

On Disjunctive Cuts for Combinatorial Optimization

In the successful branch-and-cut approach to combinatorial optimization, linear inequalities are used as cutting planes within a branch-and-bound framework. Although researchers often prefer to use facet-inducing inequalities as cutting planes, good computational results have recently been obtained using disjunctive cuts, which are not guaranteed to be facet-inducing in general.A partial explanation for the success of the disjunctive cuts is given in this paper. It is shown that, for six important combinatorial optimization problems (the clique partitioning, max-cut, acyclic subdigraph, linear ordering, asymmetric travelling salesman and set covering problems), certain facet-inducing inequalities can be obtained by simple disjunctive techniques. New polynomial-time separation algorithms are obtained for these inequalities as a by-product.The disjunctive approach is then compared and contrasted with some other general-purpose frameworks for generating cutting planes and some conclusions are made with respect to the potential and limitations of the disjunctive approach.     

An exact semidefinite programming approach for the max-mean dispersion problem

This paper proposes an exact algorithm for the Max-Mean dispersion problem (\(Max-Mean DP\)), an NP-Hard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural non-convex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. This relaxation can be tightened by means of a cutting plane algorithm which iteratively adds the most violated triangular inequalities. The proposed approach embeds the SDP relaxation and the cutting plane algorithm into a branch and bound framework to solve \(Max-Mean DP\) instances to optimality. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up to 100 elements, outperforming other alternative approaches.     

A Note on the Max-Min 0-1 Knapsack Problem

In this paper we propose new lower and upper bounds for the max-min 0-1 knapsack problem, employing a mixture of two relaxations. In addition, in order to expose whether the bounds are practical or not, we implement a method incorporating the bounds to achieve an optimal solution of the problem.     

Dynamic Programming and Hill-Climbing Techniques for Constrained Two-Dimensional Cutting Stock Problems

In this paper we propose an algorithm for the constrained two-dimensional cutting stock problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. The TDC problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. The proposed algorithm is a hybrid approach in which a depth-first search using hill-climbing strategies and dynamic programming techniques are combined. The algorithm starts with an initial (feasible) lower bound computed by solving a series of single bounded knapsack problems. In order to enhance the first-level lower bound, we introduce an incremental procedure which is used within a top-down branch-and-bound procedure. We also propose some hill-climbing strategies in order to produce a good trade-off between the computational time and the solution quality. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approach. The obtained results are compared to the results published by Alvarez-Valdés et al. (2002).     

Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering

The 0-1 cubic knapsack problem (CKP), a generalization of the classical 0-1 quadratic knapsack problem, is an extremely challenging NP-hard combinatorial optimization problem. An effective exact solution strategy for the CKP is to reformulate the nonlinear problem into an equivalent linear form that can then be solved using a standard mixed-integer programming solver. We consider a classical linearization method and propose a variant of a more recent technique for linearizing 0-1 cubic programs applied to the CKP. Using a variable reordering strategy, we show how to improve the strength of the linear programming relaxation of our proposed reformulation, which ultimately leads to reduced overall solution times. In addition, we develop a simple heuristic method for obtaining good-quality CKP solutions that can be used to provide a warm start to the solver. Computational tests demonstrate the effectiveness of both our variable reordering strategy and heuristic method.

     

Semidefinite Programming Relaxations for the Quadratic Assignment Problem

Semidefinite programming (SDP) relaxations for the quadratic assignment problem (QAP) are derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalent representations of QAP. These relaxations result in the interesting, special, case where only the dual problem of the SDP relaxation has strict interior, i.e., the Slater constraint qualification always fails for the primal problem. Although there is no duality gap in theory, this indicates that the relaxation cannot be solved in a numerically stable way. By exploring the geometrical structure of the relaxation, we are able to find projected SDP relaxations. These new relaxations, and their duals, satisfy the Slater constraint qualification, and so can be solved numerically using primal-dual interior-point methods.For one of our models, a preconditioned conjugate gradient method is used for solving the large linear systems which arise when finding the Newton direction. The preconditioner is found by exploiting the special structure of the relaxation. See e.g., Vandenverghe and Boyd (1995) for a similar approach for solving SDP problems arising from control applications.Numerical results are presented which indicate that the described methods yield at least competitive lower bounds.     

Approximate and Exact Algorithms for Constrained (Un) Weighted Two-dimensional Two-staged Cutting Stock Problems

In this paper we propose two algorithms for solving both unweighted and weighted constrained two-dimensional two-staged cutting stock problems. The problem is called two-staged cutting problem because each produced (sub)optimal cutting pattern is realized by using two cut-phases. In the first cut-phase, the current stock rectangle is slit down its width (resp. length) into a set of vertical (resp. horizontal) strips and, in the second cut-phase, each of these strips is taken individually and chopped across its length (resp. width).First, we develop an approximate algorithm for the problem. The original problem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact algorithm tailored especially for the constrained two-staged cutting problem. The algorithm starts with an initial (feasible) lower bound computed by applying the proposed approximate algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approximate and exact approaches.     

A low complexity semidefinite relaxation for large-scale MIMO detection

Many wireless communication problems is based on a convex relaxation of the maximum likelihood problem which further can be cast as binary quadratic programs (BQPs). The two standard relaxation methods that are widely used for solving general BQPs such as spectral methods and semidefinite programming problem (SDP), each have their own advantages and disadvantages. It is widely accepted that small and medium sized SDP problems can be solved efficiently by interior point methods. Albeit, semidefinite relaxation has a tighter bound for large scale problems, but its computational complexity is high. However, Row-by-Row method (RBR) for solving SDPs could be opted for an alternative for large-scale MIMO detection because of low complexity. The present work is a spectral SDP-cut formulation to which the RBR is applied for large-scale MIMO detection. A modified RBR algorithm with tighter bound is presented to specify the efficiency in detecting massive MIMO.     

Lower bounds for positive semidefinite zero forcing and their applications

The positive semidefinite zero forcing number of a graph is a parameter that is important in the study of minimum rank problems. In this paper, we focus on the algorithmic aspects of computing this parameter. We prove that it is NP-complete to find the positive semidefinite zero forcing number of a given graph, and this problem remains NP-complete even for graphs with maximum vertex degree 7. We present a linear time algorithm for computing the positive semidefinite zero forcing number of generalized series–parallel graphs. We introduce the constrained tree cover number and apply it to improve lower bounds for positive semidefinite zero forcing. We also give formulas for the constrained tree cover number and the tree cover number on graphs with special structures.     

Algorithmic approaches to the multiple knapsack assignment problem

We consider a variant of the multiple knapsack problem in which some assignment-type side constraints have to be satisfied. The problem finds applications in logistics sectors related, e.g., to transportation and maritime shipping. We derive upper bounds from Lagrangian and surrogate relaxations of a mathematical model of the problem. We introduce a constructive heuristic and a metaheuristic refinement. We study the computational complexity of the proposed methods and evaluate their practical performance through extensive computational experiments on benchmarks from the literature and on new sets of randomly generated instances.     

Protein Threading by Linear Programming: Theoretical Analysis and Computational Results

In a previous paper (Xu, Li, Kim, and Xu, Journal of Bioinformatics and Computational Biology, vol. 1, no. 1, pp. 95–117, 2003), we have used an integer programming approach to implement a protein threading program RAPTOR for protein 3D structure prediction, based on the threading model treating pairwise contacts rigorously and allowing variable gaps. We have solved the integer program by the canonical branch-and-bound method. In this paper we present a branch-and-cut method, a careful theoretical analysis of our formulation and why our approach is so effective. The result of cutting plane analysis is that two types of well-known cuts for this problem are already implied in the constraint set, which provides us some intuition that our formulation would be very effective. Experimental results show that for about 99 percent of real threading instances, the linear relaxations of their integer programs solve to integral optimal solutions directly. For the rest one percent of real instances, the integral solutions can be obtained with only several branch nodes. Experimental results also show that no special template or sequence features result in more possibilities of fractional solutions. This indicates that extra effort to seek for cutting planes to strengthen the existing formulation is unnecessary.     

The Flow Shop Scheduling Polyhedron with Setup Times

This paper addresses the problem of improving the polyhedral representation of a certain class of machine scheduling problems. Despite the poor polyhedral representation of many such problems in general, it is shown that notably tighter linear programming representations can be obtained for many important models. In particular, we study the polyhedral structure of two different mixed-integer programming formulations of the flow shop scheduling problem with sequence-dependent setup times, denoted by SDST flow shop. The first is related to the asymmetric traveling salesman problem (ATSP) polytope. The second is less common and is derived from a model proposed by Srikar and Ghosh based on the linear ordering problem (LOP) polytope. The main contribution of this work is the proof that any facet-defining inequality (facet) of either of these polytopes (ATSP and LOP) induces a facet for the corresponding SDST flow shop polyhedron. The immediate benefit of this result is that all developments to date on facets and valid inequalities for both the ATSP and the LOP can be applied directly to the machine scheduling polytope. In addition, valid mixed-integer inequalities based on variable upper-bound flow inequalities for either model are developed as well. The derived cuts are evaluated within a branch-and-cut framework.     

On threshold BDDs and the optimal variable ordering problem

Many combinatorial optimization problems can be formulated as 0/1 integer programs (0/1 IPs). The investigation of the structure of these problems raises the following tasks: count or enumerate the feasible solutions and find an optimal solution according to a given linear objective function. All these tasks can be accomplished using binary decision diagrams (BDDs), a very popular and effective datastructure in computational logics and hardware verification. We present a novel approach for these tasks which consists of an output-sensitive algorithm for building a BDD for a linear constraint (a so-called threshold BDD) and a parallel AND operation on threshold BDDs. In particular our algorithm is capable of solving knapsack problems, subset sum problems and multidimensional knapsack problems. BDDs are represented as a directed acyclic graph. The size of a BDD is the number of nodes of its graph. It heavily depends on the chosen variable ordering. Finding the optimal variable ordering is an NP-hard problem. We derive a 0/1 IP for finding an optimal variable ordering of a threshold BDD. This 0/1 IP formulation provides the basis for the computation of the variable ordering spectrum of a threshold function. We introduce our new tool azove 2.0 as an enhancement to azove 1.1 which is a tool for counting and enumerating 0/1 points. Computational results on benchmarks from the literature show the strength of our new method.     

Approximation algorithms on 0–1 linear knapsack problem with a single continuous variable

The 0–1 linear knapsack problem with a single continuous variable (KPC) is a natural generalization of the standard 0–1 linear knapsack problem (KP). In KPC, the capacity of the knapsack is not fixed, but can be adjusted by a continuous variable. This paper studies the approximation algorithm on KPC. Firstly, assuming that the weight of each item is at most the original capacity of the knapsack, we give a 2-approximation algorithm on KPC by generalizing the 2-approximation algorithm on KP. Then, without the above assumption, we give another 2-approximation algorithm on KPC for general cases by extending the first algorithm.     

Integrated Procurement Planning in Multi‐division Firms

For large multi‐division firms, coordinating procurement policies across multiple divisions to leverage volume discounts from suppliers based on firm‐wide purchasing power can yield millions of dollars of savings in procurement costs. Coordinated procurement entails deciding which suppliers to use to meet each division's purchasing needs and sourcing preferences so as to minimize overall purchasing, logistics, and operational costs. Motivated by this tactical procurement planning problem facing a large industrial products manufacturer, we propose an integrated optimization model that simultaneously considers both firm‐wide volume discounts and divisional ordering and inventory costs. To effectively solve this large‐scale integer program, we develop and apply a tailored solution approach that exploits the problem structure to generate tight bounds. We identify several classes of valid inequalities to strengthen the linear programming relaxation, establish polyhedral properties of these inequalities, and develop both a cutting‐plane method and a sequential rounding heuristic procedure. Extensive computational tests for realistic problems demonstrate that our integrated sourcing model and solution method are effective and can provide significant economic benefits. The integrated approach yields average savings of 7.5% in total procurement costs compared to autonomous divisional policies, and our algorithm generates near‐optimal solutions (within 0.75% of optimality) within reasonable computational time.     

A Tight Semidefinite Relaxation of the MAX CUT Problem

We obtain a tight semidefinite relaxation of the MAX CUT problem which improves several previous SDP relaxation in the literature. Not only is it a strict improvement over the SDP relaxation obtained by adding all the triangle inequalities to the well-known SDP relaxation, but also it satisfy Slater constraint qualification (strict feasibility).