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).     

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.     

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.     

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.     

Linearizable special cases of the QAP

We consider special cases of the quadratic assignment problem (QAP) that are linearizable in the sense of Bookhold. We provide combinatorial characterizations of the linearizable instances of the weighted feedback arc set QAP, and of the linearizable instances of the traveling salesman QAP. As a by-product, this yields a new well-solvable special case of the weighted feedback arc set problem.     

下料问题与运输问题联合优化建模

本文研究了考虑子材运输的标准一维下料问题。建立了由生产商负责运输时,标准一维下料与运输协调优化整数规划模型,最小化母材使用成本,子材库存成本及子材运输成本。采用拉格朗日松弛技术对有关约束进行松弛和模型分解,设计基于序列规则和FFD规则的混合启发式算法求解模型。该算法由两部分组成,分别用于求解标准一维下料子问题和卖方运输子问题。通过随机产生的1800个算例,验证模型合理性与算法的有效性。与基于列生成法的两阶段算法解进行比较,平均总成本降低了17.57%,表明集成算法优于两阶段算法。     

Decomposition algorithms for the integrated process planning and scheduling problem

There are several algorithms to solve the integrated process planning and scheduling (IPPS) problem (i.e., flexible job shop scheduling with process plan flexibility) in the literature. All the existing algorithms for IPPS are heuristic-based search methods and no research has investigated the use of exact solution methods for this problem. We develop several decomposition approaches based on the logic-based Benders decomposition (LBBD) algorithm. Our LBBD algorithm allows us to partition the decision variables in the IPPS problem into two models, master-problem and sub-problem. The master-problem determines process plan and operation-machine assignment, while the sub-problem optimizes sequencing and scheduling decisions. To achieve faster convergence, we develop two relaxations for the optimal makespan objective function and incorporate them into the master-problem. We analyze the performance and further enhance the algorithm with two ideas, a Benders optimality cut based on the critical path and a faster heuristic way to solve the sub-problem. 16 standard benchmark instances available in the literature are solved to evaluate and compare the performances of our algorithms with those of the state-of-the-art methods in the literature. The proposed algorithm either results in the optimal solution or improves the best-known solutions in all the existing instances, demonstrating its superiority to the existing state-of-the-art methods in literature.     

The QAP-polytope and the graph isomorphism problem

In this paper we propose a geometric approach to solve the Graph Isomorphism (GI in short) problem. Given two graphs \(G_1, G_2\), the GI problem is to decide if the given graphs are isomorphic i.e., there exists an edge preserving bijection between the vertices of the two graphs. We propose an Integer Linear Program (ILP) that has a non-empty solution if and only if the given graphs are isomorphic. The convex hull of all possible solutions of the ILP has been studied in literature as the Quadratic Assignment Problem (QAP) polytope. We study the feasible region of the linear programming relaxation of the ILP and show that the given graphs are isomorphic if and only if this region intersects with the QAP-polytope. As a consequence, if the graphs are not isomorphic, the feasible region must lie entirely outside the QAP-polytope. We study the facial structure of the QAP-polytope with the intention of using the facet defining inequalities to eliminate the feasible region outside the polytope. We determine two new families of facet defining inequalities of the QAP-polytope and show that all the known facet defining inequalities are special instances of a general inequality. Further we define a partial ordering on each exponential sized family of facet defining inequalities and show that if there exists a common minimal violated inequality for all points in the feasible region outside the QAP-polytope, then we can solve the GI problem in polynomial time. We also study the general case when there are k such inequalities and give an algorithm for the GI problem that runs in time exponential in k.     

Geometry of Semidefinite Max-Cut Relaxations via Matrix Ranks

Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and has been shown to be excellent both in theory and in practice.Recently the present authors have derived a new relaxation using a second lifting. This new relaxation, denoted SDP2, is strictly tighter than the relaxation obtained by adding all the triangle inequalities to the well-known relaxation. In this paper we present new results that further describe the remarkable tightness of this new relaxation. Let denote the feasible set of SDP2 for the complete graph with n nodes, let F _n denote the appropriately defined projection of into , the space of real symmetric n × n matrices, and let C _n denote the cut polytope in . Further let be the matrix variable of the SDP2 relaxation and X F _n be its projection. Then for the complete graph on 3 nodes, F ₃ = C ₃ holds. We prove that the rank of the matrix variable of SDP2 completely characterizes the dimension of the face of the cut polytope in which the corresponding matrix X lies. This shows explicitly the connection between the rank of the variable Y of the second lifting and the possible locations of the projected matrix X within C ₃. The results we prove for n = 3 cast further light on how SDP2 captures all the structure of C ₃, and furthermore they are stepping stones for studying the general case n 4. For this case, we show that the characterization of the vertices of the cut polytope via rank Y = 1 extends to all n 4. More interestingly, we show that the characterization of the one-dimensional faces via rank Y = 2 also holds for n 4. Furthermore, we prove that if rank Y = 2 for n 3, then a simple algorithm exhibits the two rank-one matrices (corresponding to cuts) which are the vertices of the one-dimensional face of the cut polytope where X lies.     

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.     

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.     

An Arborescent Network Formulation and Dual Ascent Based Procedure for the Two-Stage Multi-Item Dynamic Demand Lotsize Problem

Traditional approaches for modeling and solving dynamic demand lotsize problems are based on Zangwill's single-source network and dynamic programming algorithms. In this paper, we propose an arborescent fixed-charge network (ARBNET) programming model and dual ascent based branch-and-bound procedure for the two-stage multi-item dynamic demand lotsize problem. Computational results show that the new approach is significantly more efficient than earlier solution strategies. The largest set of problems that could be solved using dynamic programming contained 4 end items and 12 time periods, and required 475.38 CPU seconds per problem. The dual ascent algorithms averaged .06 CPU seconds for this problem set, and problems with 30 end items and 24 time periods were solved in 85.65 CPU seconds. Similar results verify the superiority of the new approach for handling backlogged demand. An additional advantage of the algorithm is the availability of a feasible solution, with a known worst-case optimality gap, throughout the problem-solving process.     

An improved MIP heuristic for the intermodal hub location problem

Optimization methods have been commonly developed for the intermodal hub location problem because it has a broad range of practical applications. These methods include exact methods (limited on solving large-size problems) and heuristics (no guarantee on solution quality). In order to avoid their weakness but to leverage their strength, we develop an improved MIP heuristic combining branch-and-bound, Lagrangian relaxation, and linear programming relaxation. In the heuristic, we generate a population of initial feasible solutions using the branch-and-bound and Lagrangian relaxation methods and create a linear-relaxed solution using the linear programming relaxation method. We combine these feasible and linear-relaxed solutions to fix a portion of hub location variables so as to create a number of restricted hub location subproblems. We then combine the branch-and-bound method to solve these restricted subproblems for iteratively improving solution quality. We discuss in detail the application of the method to the intermodal hub location problem. The discussion is followed by extensive statistical analysis and computational tests, where the analysis shows statistical significance of solutions for guiding the heuristic search and comparisons with other methods indicate that the proposed approach is computationally tractable and is able to obtain competitive results.     

Cardinality constraints and systems of restricted representatives

Cardinality constraints have received considerable attention from the Constraint Programming community as (so-called) global constraints that appear in the formulation of several real-life problems, while also having an interesting combinatorial structure. After discussing the relation of cardinality constraints with well-known combinatorial problems (e.g., systems of restricted representatives), we study the polytope defined by the convex hull of vectors satisfying two such constraints, in the case where all variables share a common domain. We provide families of facet-defining inequalities that are polytime separable, together with a condition for when these families of inequalities define a convex hull relaxation. Our results also hold for the case of a single such constraint.     

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.     

Corporate structure optimisation for multinational companies

In this paper we consider a multinational corporate structuring problem. This problem involves designing a corporate/organisational structure (across different countries) so as to remit profits from a number of subsidiaries to a single parent company, whilst minimising the tax paid (maximise the amount received at the parent company). This corporate structure is constrained to be a (directed) tree structure.We present a mixed-integer zero-one formulation of the problem that (for the test problems examined) provides very good linear programming relaxation bounds. We also present a tabu search heuristic for the problem which, when combined with the bounds provided by the linear programming relaxation, is able to find provably optimal solutions. Extensions to the basic corporate structuring problem and how they can be dealt with using our heuristic are also discussed.Computational results for the solution (to proven optimality) of publicly available test problems involving up to 150 countries are reported. The largest problem solved previously in the literature to proven optimality involved only 22 countries.     

Linear solution schemes for Mean-SemiVariance Project portfolio selection problems: An application in the oil and gas industry

We study the Mean-SemiVariance Project (MSVP) portfolio selection problem, where the objective is to obtain the optimal risk-reward portfolio of non-divisible projects when the risk is measured by the semivariance of the portfolio׳s Net-Present Value (NPV) and the reward is measured by the portfolio׳s expected NPV. Similar to the well-known Mean-Variance portfolio selection problem, when integer variables are present (e.g., due to transaction costs, cardinality constraints, or asset illiquidity), the MSVP problem can be solved using Mixed-Integer Quadratic Programming (MIQP) techniques. However, conventional MIQP solvers may be unable to solve large-scale MSVP problem instances in a reasonable amount of time. In this paper, we propose two linear solution schemes to solve the MSVP problem; that is, the proposed schemes avoid the use of MIQP solvers and only require the use of Mixed-Integer Linear Programming (MILP) techniques. In particular, we show that the solution of a class of real-world MSVP problems, in which project returns are positively correlated, can be accurately approximated by solving a single MILP problem. In general, we show that the MSVP problem can be effectively solved by a sequence of MILP problems, which allow us to solve large-scale MSVP problem instances faster than using MIQP solvers. We illustrate our solution schemes by solving a real MSVP problem arising in a Latin American oil and gas company. Also, we solve instances of the MSVP problem that are constructed using data from the PSPLIB library of project scheduling problems.     

On Approximate Graph Colouring and MAX-k-CUT Algorithms Based on the θ-Function

The problem of colouring a k-colourable graph is well-known to be NP-complete, for k 3. The MAX-k-CUT approach to approximate k-colouring is to assign k colours to all of the vertices in polynomial time such that the fraction of `defect edges' (with endpoints of the same colour) is provably small. The best known approximation was obtained by Frieze and Jerrum (1997), using a semidefinite programming (SDP) relaxation which is related to the Lovász -function. In a related work, Karger et al. (1998) devised approximation algorithms for colouring k-colourable graphs exactly in polynomial time with as few colours as possible. They also used an SDP relaxation related to the -function.In this paper we further explore semidefinite programming relaxations where graph colouring is viewed as a satisfiability problem, as considered in De Klerk et al. (2000). We first show that the approximation to the chromatic number suggested in De Klerk et al. (2000) is bounded from above by the Lovász -function. The underlying semidefinite programming relaxation in De Klerk et al. (2000) involves a lifting of the approximation space, which in turn suggests a provably good MAX-k-CUT algorithm. We show that of our algorithm is closely related to that of Frieze and Jerrum; thus we can sharpen their approximation guarantees for MAX-k-CUT for small fixed values of k. For example, if k = 3 we can improve their bound from 0.832718 to 0.836008, and for k = 4 from 0.850301 to 0.857487. We also give a new asymptotic analysis of the Frieze-Jerrum rounding scheme, that provides a unifying proof of the main results of both Frieze and Jerrum (1997) and Karger et al. (1998) for k 0.     

对偶性在线性规划预处理中的应用分析

在当今大数据背景下,从实际应用中抽象出来的线性规划问题的规模越来越大,复杂性越来越高,因此数据预处理技术在线性规划问题求解中的重要性日渐突显。对偶性不仅有助于原始问题的算法（如对偶单纯形法）求解,而且是进行算法求解前的预处理步的重要组成部分。针对后者,本文基于有上下界的线性规划模型,详细分析总结了将对偶性应用于预处理中的两种方法：优先列和比例列的处理,并利用无效约束的概念证明了弱优先列的性质,最后应用C语言将预处理方法进行编程实现,以国际通用题库中变量个数大于1500的标准线性规划问题为实例进行测试。实例测试结果表明：（1）对于一般线性规划问题而言,对偶性在预处理中的应用能够有效减小问题规模,一方面体现在直接减少问题的变量数和非零元数,另一方面通过影响其他预处理方法间接减少问题的约束个数;（2）从减小问题规模的角度,对大部分问题而言比例列的预处理效果优于优先列。     

QAP—not so hard in spreadsheets

Quadratic assignment problems (QAP) are rarely mentioned in introductory textbooks in management science and other relevant areas. Even in advanced textbooks, only very small examples are used, because of the complexity of the cost function. This article shows that alternative formulations of the cost function reduce the complexity. The cost function is still quadratic and the variables are still integers (binary variables), so the computational difficulties are the same as with the traditional approach. But new solvers for spreadsheets seem to be quite efficient using the matrix representation of the cost function. This approach turns out to be very simple to implement in spreadsheets. Another formulation directly representing the permutation by integers is even easier to implement, and has shown very promising results using heuristic solvers. In fact spreadsheet solvers could very well be the preferred software solving QAP, compared to other general purpose optimization software.