A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization

We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization (MISOCO) problem. We extend our prior work on disjunctive conic cuts (DCCs), which has thus far been restricted to the case in which the intersection of the hyperplanes and the feasible set is bounded. Using a similar technique, we show that one can extend our previous results to the case in which that intersection is unbounded. We provide a complete characterization in closed form of the conic inequalities required to describe the convex hull when the hyperplanes defining the disjunction are parallel.     

Dual Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints

A central problem of branch-and-bound methods for global optimization is that often a lower bound do not match with the optimal value of the corresponding subproblem even if the diameter of the partition set shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present optimality cuts which cut off a given local minimizer from the feasible set. We propose a branch-and-bound algorithm using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints are added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic programming problem dual bounds which have under certain conditions a zero duality gap.     

Inventory placement in acyclic supply chain networks

By adding a set of redundant constraints, and by iteratively refining the approximation, we show that a commercial solver is able to routinely solve moderate-size strategic safety stock placement problems to optimality. The speed-up arises because the solver automatically generates strong flow cover cuts using the redundant constraints.     

Disjunctive cuts for continuous linear bilevel programming

This work shows how disjunctive cuts can be generated for a bilevel linear programming problem (BLP) with continuous variables. First, a brief summary on disjunctive programming and bilevel programming is presented. Then duality theory is used to reformulate BLP as a disjunctive program and, from there, disjunctive programming results are applied to derive valid cuts. These cuts tighten the domain of the linear relaxation of BLP. An example is given to illustrate this idea, and a discussion follows on how these cuts may be incorporated in an algorithm for solving BLP.     

On the separation of disjunctive cuts

Disjunctive cuts for Mixed-Integer Linear Programs (MIPs) were introduced by Egon Balas in the late 1970s and have been successfully exploited in practice since the late 1990s. In this paper we investigate the main ingredients of a disjunctive cut separation procedure, and analyze their impact on the quality of the root-node bound for a set of instances taken from MIPLIB library. We compare alternative normalization conditions, and try to better understand their role. In particular, we point out that constraints that become redundant (because of the disjunction used) can produce over-weak cuts, and analyze this property with respect to the normalization used. Finally, we introduce a new normalization condition and analyze its theoretical properties and computational behavior. Along the way, we make use of a number of small numerical examples to illustrate some basic (and often misinterpreted) disjunctive programming features.     

Complexity of some cutting plane methods that use analytic centers

We consider cutting plane methods for minimizing a convex (possibly nondifferentiable) function subject to box constraints. At each iteration, accumulated subgradient cuts define a polytope that localizes the minimum. The objective and its subgradient are evaluated at the analytic center of this polytope to produce one or two cuts that improve the localizing set. We give complexity estimates for several variants of such methods. Our analysis is based on the works of Goffin, Luo and Ye. Research supported by the State Committee for Scientific Research under Grant 8S50502206.     

On active redundancy allocation for coherent systems—from the viewpoint of minimal cut decomposition

This paper deals with coherent systems with one active redundancy. For systems with the subclass of minimal cuts associated with one component covering that of another, assigning the redundancy to the former component is proved to bring forth a more reliable redundant system. As for symmetric systems with lower tail permutation decreasing component lifetimes, allocating the redundancy to the less reliable component results in a longer system lifetime. Several numerical examples are also presented to illustrate the new findings.     

Stability analysis of the Pareto optimal solutions for some vector boolean optimization problem

In this article we consider the boolean optimization problem of finding the set of Pareto optimal solutions. The vector objectives are the positive cuts of linear functions to the non-negative semi-axis. Initial data are subject to perturbations, measured by the l ₁-norm in the parameter space of the problem. We present the formula expressing the extreme level (stability radius) of such perturbations, for which a particular solution remains Pareto optimal.     

Concavity cuts for disjoint bilinear programming

We pursue the study of concavity cuts for the disjoint bilinear programming problem. This optimization problem has two equivalent symmetric linear maxmin reformulations, leading to two sets of concavity cuts. We first examine the depth of these cuts by considering the assumptions on the boundedness of the feasible regions of both maxmin and bilinear formulations. We next propose a branch and bound algorithm which make use of concavity cuts. We also present a procedure that eliminates degenerate solutions. Extensive computational experiences are reported. Sparse problems with up to 500 variables in each disjoint sets and 100 constraints, and dense problems with up to 60 variables again in each sets and 60 constraints are solved in reasonable computing times. Received: October 1999 / Accepted: January 2001?Published online March 22, 2001     

Core-generating approximate minimum entropy discretization for rough set feature selection in pattern classification

Rough set feature selection (RSFS) can be used to improve classifier performance. RSFS removes redundant attributes whilst retaining important ones that preserve the classification power of the original dataset. Reducts are feature subsets selected by RSFS. Core is the intersection of all the reducts of a dataset. RSFS can only handle discrete attributes, hence, continuous attributes need to be discretized before being input to RSFS. Discretization determines the core size of a discrete dataset. However, current discretization methods do not consider the core size during discretization. Earlier work has proposed core-generating approximate minimum entropy discretization (C-GAME) algorithm which selects the maximum number of minimum entropy cuts capable of generating a non-empty core within a discrete dataset. The contributions of this paper are as follows: (1) the C-GAME algorithm is improved by adding a new type of constraint to eliminate the possibility that only a single reduct is present in a C-GAME-discrete dataset; (2) performance evaluation of C-GAME in comparison to C4.5, multi-layer perceptrons, RBF networks and k-nearest neighbours classifiers on ten datasets chosen from the UCI Machine Learning Repository; (3) performance evaluation of C-GAME in comparison to Recursive Minimum Entropy Partition (RMEP), Chimerge, Boolean Reasoning and Equal Frequency discretization algorithms on the ten datasets; (4) evaluation of the effects of C-GAME and the other four discretization methods on the sizes of reducts; (5) an upper bound is defined on the total number of reducts within a dataset; (6) the effects of different discretization algorithms on the total number of reducts are analysed; (7) performance analysis of two RSFS algorithms (a genetic algorithm and Johnson’s algorithm).     

Lexicographic balanced optimization problems

We introduce the lexicographic balanced optimization problem (LBaOP) and show that it can be solved efficiently if an associated lexicographic bottleneck problem can be solved efficiently. For special cases of cuts in a graph and base system of a matroid, improved algorithms are proposed. A generalization of LBaOP is also discussed.     

A heuristic to generate rank-1 GMI cuts

Gomory mixed-integer (GMI) cuts are among the most effective cutting planes for general mixed-integer programs (MIP). They are traditionally generated from an optimal basis of a linear programming (LP) relaxation of a MIP. In this paper we propose a heuristic to generate useful GMI cuts from additional bases of the initial LP relaxation. The cuts we generate have rank one, i.e., they do not use previously generated GMI cuts. We demonstrate that for problems in MIPLIB 3.0 and MIPLIB 2003, the cuts we generate form an important subclass of all rank-1 mixed-integer rounding cuts. Further, we use our heuristic to generate globally valid rank-1 GMI cuts at nodes of a branch-and-cut tree and use these cuts to solve a difficult problem from MIPLIB 2003, namely timtab2, without using problem-specific cuts.     

A branch-and-cut algorithm for vehicle routing problems

We present a branch-and-cut algorithm for the identical customer Vehicle Routing Problem. Transforming the problem into an equivalent Path-Partitioning Problem allows us to exploit its polyhedral structure and to generate strong cuts corresponding to facet-inducing inequalities. By using cuts defined by multistars, partial multistars and generalized subtour elimination constraints, we are able to consistently solve 60-city problems to proven optimality and are currently attempting to solve problems involving a hundred cities. We also present details of the computer implementation and our computational results.     

Cutting Sphere Algorithm

We present a generalization of the conventional cutting plane algorithm for the solution of nonconvex optimization problems with nonsmooth inequality constraints. The cuts are effected using spheres rather than hyperplanes.     

A Complementarity-based Partitioning and Disjunctive Cut Algorithm for Mathematical Programming Problems with Equilibrium Constraints

In this paper a branch-and-bound algorithm is proposed for finding a global minimum to a Mathematical Programming Problem with Complementarity (or Equilibrium) Constraints (MPECs), which incorporates disjunctive cuts for computing lower bounds and employs a Complementarity Active-Set Algorithm for computing upper bounds. Computational results for solving MPECs associated with Bilivel Problems, NP-hard Linear Complementarity Problems, and Hinge Fitting Problems are presented to highlight the efficacy of the procedure in determining a global minimum for different classes of MPECs.     

On the complexity of cutting-plane proofs using split cuts

We prove a monotone interpolation property for split cuts which, together with results from Pudlák (1997) [20], implies that cutting-plane proofs which use split cuts (or, equivalently, mixed-integer rounding cuts or Gomory mixed-integer cuts) have exponential length in the worst case.     

Computational aspects of cutting-plane algorithms for geometric programming problems

This paper presents the results of computational studies of the properties of cutting plane algorithms as applied to posynomial geometric programs. The four cutting planes studied represent the gradient method of Kelley and an extension to develop tangential cuts; the geometric inequality of Duffin and an extension to generate several cuts at each iteration. As a result of over 200 problem solutions, we will draw conclusions regarding the effectiveness of acceleration procedures, feasible and infeasible starting point, and the effect of the initial bounds on the variables. As a result of these experiments, certain cutting plane methods are seen to be attractive means of solving large scale geometric programs.This author's research was supported in part by the Center for the Study of Environmental Policy, The Pennsylvania State University.     

Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra

In this paper, we study the relationship between 2D lattice-free cuts, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in ${\mathbb{R}^2}$ , and various types of disjunctions. Recently Li and Richard (2008), studied disjunctive cuts obtained from t-branch split disjunctions of mixed-integer sets (these cuts generalize split cuts). Balas (Presentation at the Spring Meeting of the American Mathematical Society (Western Section), San Francisco, 2009) initiated the study of cuts for the two-row continuous group relaxation obtained from 2-branch split disjunctions. We study these cuts (and call them cross cuts) for the two-row continuous group relaxation, and for general MIPs. We also consider cuts obtained from asymmetric 2-branch disjunctions which we call crooked cross cuts. For the two-row continuous group relaxation, we show that unimodular cross cuts (the coefficients of the two split inequalities form a unimodular matrix) are equivalent to the cuts obtained from maximal lattice-free sets other than type 3 triangles. We also prove that all 2D lattice-free cuts and their S-free extensions are crooked cross cuts. For general mixed integer sets, we show that crooked cross cuts can be generated from a structured three-row relaxation. Finally, we show that for the corner relaxation of an MIP, every crooked cross cut is a 2D lattice-free cut.     

Foundation-penalty cuts for mixed-integer programs

We propose a new class of foundation-penalty (FP) cuts for MIPs that are easy to generate by exploiting routine penalty calculations. Their underlying concept generalizes the lifting process and provides derivations of major classical cuts. (Gomory cuts arise from low level FP cuts by simply ‘plugging in’ standard penalties.)     

On the strength of Gomory mixed-integer cuts as group cuts

Gomory mixed-integer (GMI) cuts generated from optimal simplex tableaus are known to be useful in solving mixed-integer programs. Further, it is well-known that GMI cuts can be derived from facets of Gomory’s master cyclic group polyhedron and its mixed-integer extension studied by Gomory and Johnson. In this paper we examine why cutting planes derived from other facets of master cyclic group polyhedra (group cuts) do not seem to be as useful when used in conjunction with GMI cuts. For many practical problem instances, we numerically show that once GMI cuts from different rows of the optimal simplex tableau are added to the formulation, all other group cuts from the same tableau rows are satisfied.