Maximum cut in fuzzy nature: Models and algorithms

The maximum cut (Max-Cut) problem has extensive applications in various real-world fields, such as network design and statistical physics. In this paper, a more practical version, the Max-Cut problem with fuzzy coefficients, is discussed. Specifically, based on credibility theory, the Max-Cut problem with fuzzy coefficients is formulated as an expected value model, a chance-constrained programming model and a dependent-chance programming model respectively according to different decision criteria. When these fuzzy coefficients are represented by special fuzzy variables like triangular fuzzy numbers and trapezoidal fuzzy numbers, the crisp equivalents of the fuzzy Max-Cut problem can be obtained. Finally, a genetic algorithm combined with fuzzy simulation techniques is designed for the general fuzzy Max-Cut problem under these models and numerical experiment confirms the effectiveness of the designed genetic algorithm.     

An efficient Lagrangian smoothing heuristic for Max-Cut

Max-Cut is a famous NP-hard problem in combinatorial optimization. In this article, we propose a Lagrangian smoothing algorithm for Max-Cut, where the continuation subproblems are solved by the truncated Frank-Wolfe algorithm. We establish practical stopping criteria and prove that our algorithm finitely terminates at a KKT point, the distance between which and the neighbour optimal solution is also estimated. Additionally, we obtain a new sufficient optimality condition for Max-Cut. Numerical results indicate that our approach outperforms the existing smoothing algorithm in less time.     

Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations

We present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a “nearly optimal” solution of the basic semidefinite Max-Cut relaxation, strengthened by triangle inequalities. The expensive part of our bounding procedure is solving the basic semidefinite relaxation of the Max-Cut problem, which has to be done several times during the bounding process. We review other solution approaches and compare the numerical results with our method. We also extend our experiments to instances of unconstrained quadratic 0–1 optimization and to instances of the graph equipartition problem. The experiments show that our method nearly always outperforms all other approaches. In particular, for dense graphs, where linear programming-based methods fail, our method performs very well. Exact solutions are obtained in a reasonable time for any instance of size up to n = 100, independent of the density. For some problems of special structure we can solve even larger problem classes. We could prove optimality for several problems of the literature where, to the best of our knowledge, no other method is able to do so. Supported in part by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438.     

Greedy Differencing Edge-Contraction heuristic for the Max-Cut problem

The Max-Cut problem is a classical NP-hard problem where the objective is to partition the nodes of an edge-weighted graph in a way that maximizes the sum of edges between the parts. We present a greedy heuristic for solving Max-Cut that combines an Edge-Contraction heuristic with the Differencing Method. We compare the heuristic’s performance to other greedy heuristics using a large and diverse set of problem instances.     

Convergence rate of block-coordinate maximization Burer–Monteiro method for solving large SDPs

Mathematical Programming - Semidefinite programming (SDP) with diagonal constraints arise in many optimization problems, such as Max-Cut, community detection and group synchronization. Although...     

Rank of Handelman hierarchy for Max-Cut

We consider a hierarchical relaxation, called Handelman hierarchy, for a class of polynomial optimization problems. We prove that the rank of Handelman hierarchy, if applied to a standard quadratic formulation of Max-Cut, is exactly the same as the number of nodes of the underlying graph. Also we give an error bound for Handelman hierarchy, in terms of its level, applied to the Max-Cut formulation.     

SpeeDP: an algorithm to compute SDP bounds for very large Max-Cut instances

We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained $\{-1,1\}$ quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the non-convex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an efficient and globally convergent algorithm, called SpeeDP, for finding critical points of the LRSDP problem. We provide evidence of the effectiveness of SpeeDP by comparing it with other existing codes on an extended set of instances of the Max-Cut problem. We further include SpeeDP within a simply modified version of the Goemans?CWilliamson algorithm and we show that the corresponding heuristic SpeeDP-MC can generate high-quality cuts for very large, sparse graphs of size up to a million nodes in a few hours.     

MADAM: a parallel exact solver for max-cut based on semidefinite programming and ADMM

Computational Optimization and Applications - We present MADAM, a parallel semidefinite-based exact solver for Max-Cut, a problem of finding the cut with the maximum weight in a given graph. The...     

Improved approximation of Max-Cut on graphs of bounded degree

Let α0.87856 denote the best approximation ratio currently known for the Max-Cut problem on general graphs. We consider a semidefinite relaxation of the Max-Cut problem, round it using the random hyperplane rounding technique of Goemans and Williamson [J. ACM 42 (1995) 1115–1145], and then add a local improvement step. We show that for graphs of degree at most Δ, our algorithm achieves an approximation ratio of at least α+ε, where ε>0 is a constant that depends only on Δ. Using computer assisted analysis, we show that for graphs of maximal degree 3 our algorithm obtains an approximation ratio of at least 0.921, and for 3-regular graphs the approximation ratio is at least 0.924. We note that for the semidefinite relaxation of Max-Cut used by Goemans and Williamson the integrality gap is at least 1/0.885, even for 2-regular graphs.     

Improved semidefinite bounding procedure for solving Max-Cut problems to optimality

We present an improved algorithm for finding exact solutions to Max-Cut and the related binary quadratic programming problem, both classic problems of combinatorial optimization. The algorithm uses a branch-(and-cut-)and-bound paradigm, using standard valid inequalities and nonstandard semidefinite bounds. More specifically, we add a quadratic regularization term to the strengthened semidefinite relaxation in order to use a quasi-Newton method to compute the bounds. The ratio of the tightness of the bounds to the time required to compute them depends on two real parameters; we show how adjusting these parameters and the set of strengthening inequalities gives us a very efficient bounding procedure. Embedding our bounding procedure in a generic branch-and-bound platform, we get a competitive algorithm: extensive experiments show that our algorithm dominates the best existing method.     

An improved rounding method and semidefinite programming relaxation for graph partition

Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming (SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut, and Max-Vertex-Cover. Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and Equipartition

We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a relatively simple semidefinite program. Our approach provides accurate solutions to semidefinite relaxations of the Max-Cut and the Equipartition problem, which are not achievable by direct approaches based only on interior-point methods. Received: April, 2004 The last author gratefully acknowledges the support from the Austrian Science Foundation FWF Project P12660-MAT.     

A global optimization method for the design of space trajectories

The problem of optimally designing a trajectory for a space mission is considered in this paper. Actual mission design is a complex, multi-disciplinary and multi-objective activity with relevant economic implications. In this paper we will consider some simplified models proposed by the European Space Agency as test problems for global optimization (GTOP database). We show that many trajectory optimization problems can be quite efficiently solved by means of relatively simple global optimization techniques relying on standard methods for local optimization. We show in this paper that our approach has been able to find trajectories which in many cases outperform those already known. We also conjecture that this problem displays a “funnel structure” similar, in some sense, to that of molecular optimization problems.     

Test case generators and computational results for the maximum clique problem

In the last years many algorithms have been proposed for solving the maximum clique problem. Most of these algorithms have been tested on randomly generated graphs. In this paper we present different test problem generators that arise from a variety of practical applications, as well as graphs with known maximum cliques. In addition, we provide computational experience with two exact algorithms using the generated test problems.     

Generating quadratic assignment test problems with known optimal permutations

The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem of which the travelling-salesman problem is a special case. Although the QAP has been extensively studied during the past three decades, this problem remains very hard to solve. Problems of sizes greater than 15 are generally impractical to solve. For this reason, many heuristics have been developed. However, in the literature, there is a lack of test problems with known optimal solutions for evaluating heuristic algorithms. Only recently Paulubetskis proposed a method to generate test problems with known optimal solutions for a special type of QAP. This paper concerns the generation of test problems for the QAP with known optimal permutations. We generalize the result of Palubetskis and provide test-problem generators for more general types of QAPs. The test-problem generators proposed are easy to implement and were also tested on several well-known heuristic algorithms for the QAP. Computatinal results indicate that the test problems generated can be used to test the effectiveness of heuristic algorithms for the QAP. Comparison with Palubetskis' procedure was made, showing the superiority of the new test-problem generators. Three illustrative test problems of different types are also provided in an appendix, together with the optimal permutations and the optimal objective function values.     

Regularization tools and robust optimization for ill-conditioned least squares problem: A computational comparison

Least squares problems arise frequently in many disciplines such as image restorations. In these areas, for the given least squares problem, usually the coefficient matrix is ill-conditioned. Thus if the problem data are available with certain error, then after solving least squares problem with classical approaches we might end up with a meaningless solution. Tikhonov regularization, is one of the most widely used approaches to deal with such situations. In this paper, first we briefly describe these approaches, then the robust optimization framework which includes the errors in problem data is presented. Finally, our computational experiments on several ill-conditioned standard test problems using the regularization tools, a Matlab package for least squares problem, and the robust optimization framework, show that the latter approach may be the right choice.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.     

Test Problem Generator by Neural Network for Algorithms that Try Solving Nonlinear Programming Problems Globally

A test problem generator, by means of neural networks nonlinear function approximation capability, is given in this paper which provides test problems, with many predetermined local minima and a global minimum, to evaluate nonlinear programming algorithms that are designed to solve the problem globally.     

An Improved Algorithm for the Capacitated Facility Location Problem

In this paper we consider the classical capacitated facility location problem. A branch and bound algorithm is presented which measurably improves upon the recent results of Akinc and Khumawala. The use of a specialized Lagrangean relaxation results in significantly tighter bounds than those for the traditional continuous relaxation. These bounds, when combined with penalties derived from the Lagrangean relaxation, enable many integer variables to be fixed at specific values. This results in fewer branches, and indeed for certain test problems taken from the literature, branching is not required. Average computation time for a battery of test problems from the literature has been reduced (conservatively) by a factor of 3.     

The location and allocation of products and product families on retail shelves

In this paper, we model a shelf-management problem in which individual products are categorized as part of a product family. It is well known that a product’s shelf location has a significant impact on sales for many retail items. We develop a continuous as well as a discrete model with postprocessing to optimize product placement with consideration given to maintaining the grouping of product families. Computational results are reported on test problems as well as real-world beverage placement problems.