Note on: N.E. Aguilera, M.S. Escalante, G.L. Nasini, “The disjunctive procedure and blocker duality”

Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–13] give a generalization of a theorem of Lehman through an extension of the disjunctive procedure defined by Balas, Ceria and Cornuéjols. This generalization can be formulated as(A) For every clutter , the disjunctive index of its set covering polyhedron coincides with the disjunctive index of the set covering polyhedron of its blocker, .In Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–3], (A) is indeed a corollary of the stronger result(B) .Motivated by the work of Gerards et al. [Math. Oper. Res. 28 (2003) 884–885] we propose a simpler proof of (B) as well as an alternative proof of (A), independent of (B). Both of them are based on the relationship between the “disjunctive relaxations” obtained by and the set covering polyhedra associated with some particular minors of .     

The continuity of two functions associated with a maximin problem with connected variables

A function being the sum of two bilinear functions with one and the same first vector argument belonging to a polyhedron and the other two vector arguments belonging to another polyhedron is considered. It is shown that a certain minimum function of this sum and the maximin function of the sum (on the second polyhedron of connected variables) are continuous on corresponding polyhedra, which can be used in solving a maximin problem that is considered in the article.     

A mathematical model for estimating the potential margin of state undecided voters for a candidate in a US Federal election

A US Federal election in which candidates from two major political parties compete for the votes of those undecided voters in a state who usually do not vote in US elections is considered. A mathematical model for evaluating the expectation of the margin of votes to be received from such voters by either candidate as a result of the election campaigns of all the competing candidates is proposed. On the basis of this model, finding the estimation under consideration is reducible to finding the minimum of the maximin function of the difference of two bilinear functions with one and the same first vector argument whose second vector arguments belong to a polyhedron of connected variables (strategies of the candidates), and this minimum is sought on another polyhedron.     

Finite-volume hyperbolic 4-manifolds that share a fundamental polyhedron

It is known that the volume function for hyperbolic manifolds of dimension 3 is finite-to-one. We show that the number of nonhomeomorphic hyperbolic 4-manifolds with the same volume can be made arbitrarily large. This is done by constructing a sequence of finite-sided finite-volume polyhedra with side-pairings that yield manifolds. In fact, we show that arbitrarily many nonhomeomorphic hyperbolic 4-manifolds may share a fundamental polyhedron. As a by-product of our examples, we also show in a constructive way that the set of volumes of hyperbolic 4-manifolds contains the set of even integral multiples of 4π²/3. This is “half” the set of possible values for volumes, which is the integral multiples of 4π²/3 due to the Gauss-Bonnet formula Vol(M) = 4π²/3 · χ(M).     

A strongly polynomial algorithm for line search in submodular polyhedra

A submodular polyhedron is a polyhedron associated with a submodular function. This paper presents a strongly polynomial time algorithm for line search in submodular polyhedra with the aid of a fully combinatorial algorithm for submodular function minimization. The algorithm is based on the parametric search method proposed by Megiddo.     

An unbounded matroid intersection polyhedron

A characterization of the maximum-cardinality common independent sets of two matroids via an unbounded convex polyhedron is proved, confirming a conjecture of D.R. Fulkerson. A similar result, involving a bounded polyhedron, is the well-known matroid intersection polyhedron theorem of Jack Edmonds; Edmonds's theorem is used in the proof.     

(A,B)-Invariant Polyhedral Sets of Linear Discrete-Time Systems

The problem of confining the trajectory of a linear discrete-time system in a given polyhedral domain is addressed through the concept of (A, B)-invariance. First, an explicit characterization of (A, B)-invariance of convex polyhedra is proposed. Such characterization amounts to necessary and sufficient conditions in the form of linear matrix relations and presents two major advantages compared to the ones found in the literature: it applies to any convex polyhedron and does not require the computation of vertices. Such advantages are felt particularly in the computation of the supremal (A, B)-invariant set included in a given polyhedron, for which a numerical method is proposed. The problem of computing a control law which forces the system trajectories to evolve inside an (A, B)-invariant polyhedron is treated as well. Finally, the (A, B)-invariance relations are generalized to persistently disturbed systems.     

Stratification method in the theory of thin shells : PMM vol. 43, no. 6, 1979, pp. 1058–1064

It is shown that on the basis of certain simplifications induced in the physical and geometrical dependences, such a “stratification” of a shell can be achieved for which the fibers of each of two layers will be deformed just as thin rods whose axes agree with the lines of principal curvature of the shell middle surface. The approach to analyzing shells on the basis of the relationships to be obtained below is called the “stratification method”.     

Parametric resonance in the problem of a heavy rigid body rolling along a straight line on a plane

The problem of the stability of a heavy rigid body, bounded by the surface of an ellipsoid and with a cavity in the form of a coaxial ellipsoid, rolling along a straight line on a horizontal rough plane is investigated. It is shown that in the case of a body that is close to being dynamically symmetrical, parametric resonance always occurs leading to instability of the rolling. Each ellipsoid has its own “individual” resonance angular velocity. In the general case, regions in which the necessary stability conditions are satisfied can be distinguished in parameter space. The problem of calculating the resonance coefficient corresponding to instability for parametric resonance in a reversible third-order system is solved.     

Shape regularity conditions for polygonal/polyhedral meshes,exemplified in a discontinuous Galerkin discretization

This article concerns shape regularity conditions on arbitrarily shaped polygonal/polyhedral meshes. In (J. Wang and X. Ye, A weak Galerkin mixed finite element method for second‐order elliptic problems, Math Comp 83 (2014), 2101–2126), a set of shape regularity conditions has been proposed, which allows one to prove important inequalities such as the trace inequality, the inverse inequality, and the approximation property of the L² projection on general polygonal/polyhedral meshes. In this article, we propose a simplified set of conditions which provides similar mesh properties. Our set of conditions has two advantages. First, it allows the existence of “small” edges/faces, as long as the shape of the polygon/polyhedron is regular. Second, coupled with an extra condition, we are now able to deal with nonquasiuniform meshes. As an example, we show that the discontinuous Galerkin method for Laplacian equations on arbitrarily shaped polygonal/polyhedral meshes, satisfying the proposed set of shape regularity conditions, achieves optimal rate of convergence. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 308–325, 2015     

Scheduling of a machining center

A machining center is an advanced NC (Numerical Control) machine that has the capability to perform a variety of operations on a part by automatically changing the cutting tools. Because of its versatile processing capabilities, a machining center is often a production bottleneck, and effective scheduling can result in significant improvement of system performance. The problem, however, is very difficult since many factors such as machine setups, pallets, tool magazine, and possible tool overlapping among different part types, etc., have to be considered. This paper presents an optimization-based approach for the scheduling of a machining center with two pallets. A novel “separable” problem formulation that considers the above mentioned factors is presented. Lagrangian relaxation is applied to decompose the problem into simple subproblems, which are efficiently solved without encountering complexity difficulties. The subgradient method is then used to update the multipliers. Testing results indicate that the approach is effective, and the algorithm provides a valuable tool for solving stand-alone machining center problems. The approach also points out a direction on how to consider machining centers within a job shop environment.     

The Polytope of Non-Crossing Graphs on a Planar Point Set

For any set A of n points in ², we define a (3n - 3)-dimensional simple polyhedron whose face poset is isomorphic to the poset of non-crossing marked graphs with vertex set A, where a marked graph is defined as a geometric graph together with a subset of its vertices. The poset of non-crossing graphs on A appears as the complement of the star of a face in that polyhedron. The polyhedron has a unique maximal bounded face, of dimension 2n_i + n - 3 where n_i is the number of points of A in the interior of conv (A). The vertices of this polytope are all the pseudo-triangulations of A, and the edges are flips of two types: the traditional diagonal flips (in pseudo-triangulations) and the removal or insertion of a single edge. As a by-product of our construction we prove that all pseudo-triangulations are infinitesimally rigid graphs.     

The Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and Power-of-2 Rules

Queue-mergesort is introduced by Golin and Sedgewick as an optimal variant of mergesorts in the worst case. In this paper, we present a complete analysis of the cost distribution of queue-mergesort, including the best, average, and variance cases. The asymptotic normality of its cost is also established under the uniform permutation model. We address the corresponding optimality problems and we show that if we fix the merging scheme then the optimal mergesort as far as the average number of comparisons is concerned is to divide as evenly as possible at each recursive stage (top-down mergesort). On the other hand, the variance of queue-mergesort reaches asymptotically the minimum value. We also characterize a class of mergesorts with the latter property. A comparative discussion is given on the probabilistic behaviors of top-down mergesort, bottom-up mergesort, and queue-mergesort. We derive an “invariance principle” for asymptotic linearity of divide-and-conquer recurrences based on general “power-of-2” rules of which the underlying dividing rule of queue-mergesort is a special case. These analyses reveal an interesting algorithmic feature for general power-of-2 rules.     

Optimization over the polyhedron determined by a submodular function on a co-intersecting family

A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most 1/2n(n – 1) augmentations, wheren is the number of the variables and we assume a certain oracle for computing multiple exchange capacities.     

Matching,Euler tours and the Chinese postman

The solution of the Chinese postman problem using matching theory is given. The convex hull of integer solutions is described as a linear programming polyhedron. This polyhedron is used to show that a good algorithm gives an optimum solution. The algorithm is a specialization of the more generalb-matching blossom algorithm. Algorithms for finding Euler tours and related problems are also discussed.     

Octahedral Projections of a Point onto a Polyhedron

In computational methods and mathematical modeling, it is often required to find vectors of a linear manifold or a polyhedron that are closest to a given point. The “closeness” can be understood in different ways. In particular, the distances generated by octahedral, Euclidean, and Hölder norms can be used. In these norms, weight coefficients can also be introduced and varied. This paper presents the results on the properties of a set of octahedral projections of the origin of coordinates onto a polyhedron. In particular, it is established that any Euclidean and Hölder projection can be obtained as an octahedral projection due to the choice of weights in the octahedral norm. It is proven that the set of octahedral projections of the origin of coordinates onto a polyhedron coincides with the set of Pareto-optimal solutions of the multicriterion problem of minimizing the absolute values of all components.     

Finding a best approximation pair of points for two polyhedra

Given two disjoint convex polyhedra, we look for a best approximation pair relative to them, i.e., a pair of points, one in each polyhedron, attaining the minimum distance between the sets. Cheney and Goldstein showed that alternating projections onto the two sets, starting from an arbitrary point, generate a sequence whose two interlaced subsequences converge to a best approximation pair. We propose a process based on projections onto the half-spaces defining the two polyhedra, which are more negotiable than projections on the polyhedra themselves. A central component in the proposed process is the Halpern–Lions–Wittmann–Bauschke algorithm for approaching the projection of a given point onto a convex set.     

The optimum shape of a bending beam

The problem of minimizing the static deflection of an elastic beam of variable cross-section and fixed volume in the case of free supported and rigidly clamped ends is considered. In the first case it is proved that the solutions obtained earlier, based on the necessary conditions for an extremum, satisfy the sufficient conditions. In the case of clamped ends, which is of the most interest from the point of view of applications, it is proved that the optimum solutions must necessarily have points inside the solution range in which the distribution of the beam thicknesses degenerates to zero (“internal hinges”). A qualitative, analytical and numerical analysis of this phenomenon is given. In particular, in the case of clamped ends for a class of point loads, analytical solutions for which the beam splits into two cantilevers are obtained.     

On Potential Theoretic Skeletons of Polyhedra

We prove that any polyhedron in two dimensions admits a type of potential theoretic skeleton called mother body. We also show that the mother bodies of any polyhedron in any number of dimensions are in one-to-one correspondence with certain kinds of decompositions of the polyhedron into convex subpolyhedra. A consequence of this is that there can exist at most finitely many mother bodies of any given polyhedron. The main ingredient in the proof of the first mentioned result consists of showing that any polyhedron in two dimensions contains a convex subpolyhedron which sticks to it in the sense that every face of the subpolyhedron has some part in common with a face of the original polyhedron.