The heat conduction problem for orthotropic shells with a system of cuts

Using the Fourier integral method we have solved the heat conduction problem for an orthotropic shell of arbitrary Gaussian curvature with a system of thermally insulated cuts. In the process we have taken account of heat exchange on the lateral surfaces of the shells. We have studied the influence of the anistropy properties of the material on the distribution of the perturbed temperature field. Using the example of a system consisting of two cuts we have studied the dependence of jumps in the integral characteristics of the temperature on the relative locations of the cuts. Translated fromTeoreticheskaya i Prikladnaya Mekhanika, No. 24, 1993, pp. 50–54.     

Correctness of the formulation of symmetric problems of the mechanics of shallow shells with cuts

The behavior of the edges of cuts in shallow shells with the symmetric combined action of tension and flexure is investigated. For shells of different curvature with one and two parallel or collinear cuts, the load region in which there is no contact of the cut edges in the course of shell deformation is determined.Translated from Teoreticheskaya i Prikladnaya Mekhanika, No. 19, pp. 98–100, 1988.     

Improved convexity cuts for lattice point problems

The generalized lattice point (GLP) problem provides a formulation that accommodates a variety of discrete alternative problems. In this paper, we show how to substantially strengthen the convexity cuts for the GLP problem. The new cuts are based on the identification ofsynthesized lattice point conditions to replace those that ordinarily define the cut. The synthesized conditions give an alternative set of hyperplanes that enlarge the convex set, thus allowing the cut to be shifted deeper into the solution space. A convenient feature of the strengthened cuts is the evidence of linking relationships by which they may be constructively generated from the original cuts. Geometric examples are given in the last section to show how the new cuts improve upon those previously proposed for the GLP problem.     

Depth-Optimized Convexity Cuts

This paper presents a general, self-contained treatment of convexity or intersection cuts. It describes two equivalent ways of generating a cut—via a convex set or a concave function—and a partial-order notion of cut strength. We then characterize the structure of the sets and functions that generate cuts that are strongest with respect to the partial order. Next, we specialize this analytical framework to the case of mixed-integer linear programming (MIP). For this case, we formulate two kinds of the deepest cut generation problem, via sets or via functions, and subsequently consider some special cases which are amenable to efficient computation. We conclude with computational tests of one of these procedures on a large set of MIPLIB problems.     

Ancestor tree for arbitrary multi-terminal cut functions

In many applications, a function is defined on the cuts of a network. In the max-flow min-cut theorem, the function on a cut is simply the sum of all capacities of edges across the cut, and we want the minimum value of a cut separating a given pair of nodes. To find the minimum cuts separating pairs of nodes, we only needn – 1 computations to construct the cut-tree. In general, we can define arbitrary values associated with all cuts in a network, and assume that there is a routine which gives the minimum cut separating a pair of nodes. To find the minimum cuts separating pairs of nodes, we also only needn – 1 routine calls to construct a binary tree which gives all minimum partitions. The binary tree is analogous to the cut-tree of Gomory and Hu.     

The interaction of a system of longitudinal cuts in a closed cylindrical shell taking account of plastic strain

The problem of the limiting equilibrium of a closed cylindrical shell with evenly spaced longitudinal cuts, stated in the context of the analogy with the _k-model of Leonov-Panasyuk-Dagdeil, is reduced to a system of singular integral equations. An algorithm is constructed for the numerical solution of this system. For a shell under internal pressure we study the influence of the number of cuts, the magnitude of the applied load, and the length of a cut on the opening of its ends. Two figures. Bibliography: 4 titles.Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, Issue 30, 1989, pp. 50–55.     

Practical strategies for generating rank-1 split cuts in mixed-integer linear programming

In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the rows of the optimal simplex tableau, and deriving the corresponding Gomory mixed-integer cuts; potentially, we can generate a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank-1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split, Lift-and-Project, Flow and Knapsack cover): on MIPLIB instances, these generators close 24% of the integrality gap on average; adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a Branch-and-Cut framework, these new cuts can improve computing time on difficult instances.     

Monoidal cut strengthening revisited

There are two distinct strengthening methods for disjunctive cuts with some integer variables; they differ in the way they modularize the coefficients. In this paper, we introduce a new variant of one of these methods, the monoidal cut strengthening procedure, based on the paradox that sometimes weakening a disjunction helps the strengthening procedure and results in sharper cuts. We first derive a general result that applies to cuts from disjunctions with any number of terms. It defines the coefficients of the cut in a way that takes advantage of the option of adding new terms to the disjunction. We then specialize this result to the case of split cuts for mixed integer programs with some binary variables, in particular Gomory mixed integer cuts, and to intersection cuts from multiple rows of a simplex tableau. In both instances we specify the conditions under which the new cuts have smaller coefficients than the cuts obtained by either of the two currently known strengthening procedures.     

Excluding a Simple Good Pair Approach to Directed Cuts

In 1972, Mader proved that every undirected graph has a good pair, that is, an ordered pair (u,v) of nodes such that the star of v is a minimum cut separating u and v. In 1992, Nagamochi and Ibaraki gave a simple procedure to find a good pair as the basis of an elegant and very efficient algorithm to find minimum cuts in graphs. This paper rules out the simple good pair approach for the problem of finding a minimum directed cut in a digraph and for the more general problem of minimizing submodular functions. In fact, we construct a digraph with no good pair. Note that if a graph has no good pair, then it may not possess a so-called cut-equivalent tree. Benczúr constructed a digraph with no cut-equivalent tree; our counterexample thus extends Benczúr's one. Received: March 12, 1999 Final version received: June 19, 2000     

An analytic center quadratic cut method for the convex quadratic feasibility problem

 We consider a quadratic cut method based on analytic centers for two cases of convex quadratic feasibility problems. In the first case, the convex set is defined by a finite yet large number, N, of convex quadratic inequalities. We extend quadratic cut algorithm of Luo and Sun [3] for solving such problems by placing or translating the quadratic cuts directly through the current approximate center. We show that, in terms of total number of addition and translation of cuts, our algorithm has the same polynomial worst case complexity as theirs [3]. However, the total number of steps, where steps consist of (damped) Newton steps, function evaluations and arithmetic operations, required to update from one approximate center to another is , where ε is the radius of the largest ball contained in the feasible set. In the second case, the convex set is defined by an infinite number of certain strongly convex quadratic inequalities. We adapt the same quadratic cut method for the first case to the second one. We show that in this case the quadratic cut algorithm is a fully polynomial approximation scheme. Furthermore, we show that, at each iteration, k, the total number steps (as described above) required to update from one approximate center to another is at most , with ε as defined above. Received: April 2000 / Accepted: June 2002 Published online: September 5, 2002 Key words. convex quadratic feasibility problem – interior-point methods – analytic center – quadratic cuts – potential function     

Herbrand's theorem revisited

We present recent results on the deepening connection between proof theory and formal language theory. To each first-order proof with prenex cuts of complexity at most Π_n/Σ_n, we associate a typed (non-deterministic) tree grammar of order n (equivalently, an order n recursion scheme) that abstracts the computation of Herbrand sets obtained through Gentzen-style cut elimination. Apart from offering a means to compute Herbrand expansions directly from proofs with cuts, these grammars provide a structural counterpart to Herbrand's theorem that opens the door to tackling a number of questions in proof theory such as proof equivalence, proof compression and proof complexity. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The vertex separator problem: algorithms and computations

This is a companion paper to our polyhedral study [1] of the Vertex Separator (VS) Problem. Given an undirected graph G, the VS problem consists in identifying a minimum-weight vertex set whose removal disconnects G, subject to bounds on the size of the resulting components. In this paper, we describe versions of a branch-and-cut algorithm based on the results of that polyhedral study. It uses two families of cuts, symmetric and asymmetric, for which we develop polynomial-time greedy separation routines. A heuristic to generate feasible separators is also used. A computational experiment on several data sets from the literature compares the performance of three versions of our algorithm to that of the commercial MIP solver XPRESS. This experiment throws a sharp light on the role of cut density, known to software developers but never before documented in the literature. It convincingly shows that the practical usefulness of cuts in integer programming depends not only on their strength, but also on their sparsity: everything else being equal, the smaller the cut support, the better. The power of the inequalities proposed here is well illustrated by the computational tests on dense graphs. This is in accordance with the previous observation, since the support of these cuts tends to decrease with graph density.Research supported by the Brazilian agencies FAPESP (grant 01/14205–6), CAPES (grant BEX 04444/02–2) and CNPq (grants 302588/02–7 and Pronex 664107/97–4).Research supported by the National Science Foundation through grant #DMI-0098427 and by the Office of Naval Research through contract N00014-97-1-0196.     

Generalized intersection cuts and a new cut generating paradigm

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This characterization is minimal in the sense that every one of the inequalities it uses defines a facet of the closure.     

On mixed-integer sets with two integer variables

We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined in 2010). We extend this result to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables if the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixed-integer sets similar to the one on the equivalence of different definitions of split cuts presented in Cook et al. (1990) [4]. This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008) [8]. Finally, we extend our results to mixed-integer sets that are defined as the set of points (with some components being integral) inside a closed, bounded and convex set.     

On generating maximal nondominated Benders cuts

In this paper, we explore certain algorithmic strategies for accelerating the convergence of Benders decomposition method via the generation of maximal nondominated cuts. Based on interpreting the seminal work of Magnanti and Wong (Operations Research, 29(3), 464–484, 1981) for generating nondominated cuts within a multiobjective framework, we propose an algorithmic strategy that utilizes a preemptively small perturbation of the right-hand-side of the Benders subproblem to generate maximal nondominated Benders cuts, as well as a complimentary strategy that generates an additional cut in each iteration via an alternative emphasis on decision variable weights. We also examine the computational effectiveness of solving a secondary subproblem using an objective cut as proposed by Magnanti and Wong versus identifying the Pareto-optimality region for cut generation by utilizing complementary slackness conditions. In addition, we exhibit how a standard feasibility cut can be extracted from the solution of subproblems that generate only optimality cuts through the use of artificial variables. With Magnanti and Wong’s baseline procedure approximated during implementation via the use of a core point estimation technique (Papadakos in Computers and Operations Research, 36(1), 176–195, 2009), these algorithmic strategies are tested on instances from the literature concerning the fixed charge network flow program.     

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.     

Generic cuts in models of arithmetic

We present some general results concerning the topological space of cuts of a countable model of arithmetic given by a particular indicator Y. The notion of “indicator” is de.ned in a novel way, without initially specifying what property is indicated and is used to de.ne a topological space of cuts of the model. Various familiar properties of cuts (strength, regularity, saturation, coding properties) are investigated in this sense, and several results are given stating whether or not the set of cuts having the property is comeagre. A new notion of “generic cut” is introduced and investigated and it is shown in the case of countable arithmetically saturated models M ? PA that generic cuts exist, indeed the set of generic cuts is comeagre in the sense of Baire, and furthermore that two generic cuts within the same “small interval” of the model are conjugate by an automorphism of the model.The paper concludes by outlining some applications to constructions of cuts satisfying properties incompatible with genericity, and discussing in model‐theoretic terms those properties for which there is an indicator Y. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Optimizing over the split closure

The polyhedron defined by all the split cuts obtainable directly (i.e. without iterated cut generation) from the LP-relaxation P of a mixed integer program (MIP) is termed the (elementary, or rank 1) split closure of P. This paper deals with the problem of optimizing over the elementary split closure. This is accomplished by repeatedly solving the following separation problem: given a fractional point, say x, find a rank-1 split cut violated by x or show that none exists. Following Caprara and Letchford [17], we formulate this separation problem as a nonlinear mixed integer program that can be treated as a parametric mixed integer linear program (PMILP) with a single parameter in the objective function and the right hand side. We develop an algorithmic framework to deal with the resulting PMILP by creating and maintaining a dynamically updated grid of parameter values, and use the corresponding mixed integer programs to generate rank 1 split cuts. Our approach was implemented in the COIN-OR framework using CPLEX 9.0 as a general purpose MIP solver. We report our computational results on well-known benchmark instances from MIPLIB 3.0 and several classes of structured integer and mixed integer problems. Our computational results show that rank-1 split cuts close more than 98% of the duality gap on 15 out of 41 mixed integer instances from MIPLIB 3.0. More than 75% of the duality gap can be closed on an additional 10 instances. The average gap closed over all 41 instances is 72.78%. In the pure integer case, rank-1 split cuts close more than 75% of the duality gap on 13 out of 24 instances from MIPLIB 3.0. On average, rank 1 split cuts close about 72% of the duality gap on these 24 instances. We also report results on several classes of structured problems: capacitated versions of warehouse location, single-source facility location, p-median, fixed charge network flow, multi-commodity network design with splittable and unsplittable flows, and lot sizing. The fraction of the integrality gap closed varies for these problem classes between 100 and 67%. We also gathered statistics on the average coefficient size (absolute value) of the disjunctions generated. They turn out to be surprisingly small. Research was supported by the National Science Foundation through grant #DMI-0352885 and by the Office of Naval Research through contract N00014-03-1-0133.     

On the separation of split cuts and related inequalities

 The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split cuts, one has to solve the associated separation problem. The complexity of split cut separation was recently cited as an open problem by Cornuéjols & Li CL01. In this paper we settle this question by proving strong 𝒩𝒫-completeness of separation for split cuts. As a by-product we also show 𝒩𝒫-completeness of separation for several other classes of inequalities, including the MIR-inequalities of Nemhauser and Wolsey and some new inequalities which we call balanced split cuts and binary split cuts. We also strengthen 𝒩𝒫-completeness results of Caprara & Fischetti CF96 (for -cuts) and Eisenbrand E99 (for Chvátal-Gomory cuts). To compensate for this bleak picture, we also give a positive result for the Symmetric Travelling Salesman Problem. We show how to separate in polynomial time over a class of split cuts which includes all comb inequalities with a fixed handle. Received: October 23, 2000 / Accepted: October 03, 2001 Published online: September 5, 2002 Key words. cutting planes – separation – complexity – travelling salesman problem – comb inequalities