Two Conjectures on Graceful Digraphs

A digraph D with p vertices and q arcs is labeled by assigning a distinct integer value g(v) from {0,1, … , q} to each vertex v. The vertex values, in turn, induce a value g(u, v) on each arc (u, v) where g(u, v) = (g(v)? g(u))(mod q + 1). If the arc values are all distinct then the labeling is called a graceful labeling of a digraph. Bloom and Hsu (SIAM J Alg Discr Methods 6:519–536, 1985) conjectured that, all unicyclic wheels are graceful. Also, Zhao et al. (J Prime Res Math 4:118–126, 2008) conjectured that, for any positive even n and any integer m ≥ 14, the digraph ${n-\overrightarrow{C_m}}$ is graceful. In this paper, we prove both the conjectures.     

Constructive characterizations of the value-function of a mixed-integer program I

Recent work has provided explicit formulas for the value function of a pure integer program, and for indicator functions for the set of feasible right-hand sides. These formulas are based on linear functions, next-higher integer operations, sums, and maxima. In the present paper, we investigate possible extensions to mixed-integer programs.     

A note on constraint aggregation and value functions for two-stage stochastic integer programs

We consider a class of two-stage stochastic integer programs and their equivalent reformulation that uses the integer programming value functions in both stages. One class of solution methods in the literature is based on the idea of pre-computing and storing exact value functions, and then exploiting this information within a global branch-and-bound framework. Such methods are known to be very sensitive to the magnitude of feasible right-hand side values. In this note we propose a simple constraint-aggregation based approach that potentially alleviates this limitation.     

Minimal cut-generating functions are nearly extreme

We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory–Johnson setting as well as a recent extension by Y?ld?z and Cornuéjols (Math Oper Res 41:1381–1403, 2016). We show that for any continuous minimal or strongly minimal cut generating function, there exists an extreme cut generating function that approximates the (strongly) minimal function as closely as desired. In other words, the extreme functions are “dense” in the set of continuous (strongly) minimal functions.     

Existence of optimal controls for some nonlinear processes

We prove the existence of optimal controls for an ordinary differential system which is nonlinear in the state functionx but is linear in the control functionu, that is, $$dx/dt = f_1 (t,x) + f_2 (t,x)u$$ Rather weak regularity assumptions are made on the right-hand side of the above system, the constraints, and the cost functional.     

A Gilmore-Gomory construction of integer programming value functions

In this paper, we analyze how sequentially introducing decision variables into an integer program (IP) affects the value function and its level sets. We use a Gilmore-Gomory approach to find parametrized IP value functions over a restricted set of variables. We introduce the notion of maximal connected subsets of level sets - volumes in which changes to the constraint right-hand side have no effect on the value function - and relate these structures to IP value functions and optimal solutions.     

Upper bounds on the upper signed total domination number of graphs

Let G=(V,E) be a graph. A function f:V→{−1,+1} defined on the vertices of G is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function f is minimal if there does not exist a signed total dominating function g, f≠g, for which g(v)≤f(v) for every v∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of G. The upper signed total domination number of G is the maximum weight of a minimal signed total dominating function on G. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs.     

Integer programming as projection

We generalise polyhedral projection (Fourier–Motzkin elimination) to integer programming (IP) and derive from this an alternative perspective on IP that parallels the classical theory. We first observe that projection of an IP yields an IP augmented with linear congruence relations and finite-domain variables, which we term a generalised IP. The projection algorithm can be converted to a branch-and-bound algorithm for generalised IP in which the search tree has bounded depth (as opposed to conventional branching, in which there is no bound). It also leads to valid inequalities that are analogous to Chvátal–Gomory cuts but are derived from congruences rather than rounding, and whose rank is bounded by the number of variables. Finally, projection provides an alternative approach to IP duality. It yields a value function that consists of nested roundings as in the classical case, but in which ordinary rounding is replaced by rounding to the nearest multiple of an appropriate modulus, and the depth of nesting is again bounded by the number of variables. For large perturbations of the right-hand sides, the value function is shift periodic and can be interpreted economically as yielding “average” shadow prices.     

Bounds for Bessel functions

We establish lower and upper bounds for the Bessel functionJ _v (x) and the modified Bessel functionI _v(x) of the first kind. Our chief tool is the differential equation satisfied by these functions.     

Parametric integer linear programming: A synthesis of branch and bound with cutting planes

A branch and bound algorithm is designed to solve the general integer linear programming problem with parametric right-hand sides. The right-hand sides have the form b + θd where b and d are comformable vectors, d consists of nonnegative constants, and θ varies from zero to one.The method consists of first determining all possible right-hand side integer constants and appending this set of integer constants to the initial tableau to form an expanded problem with a finite number of family members. The implicit enumeration method gives a lower bound on the integer solutions. The branch and bound method is used with fathoming tests which allow one family member possibly to fathom other family members. A cutting plane option applies a finite number of cuts to each node before branching. In addition, the cutting plane method is invoked whenever some members are feasible at a node and others are infeasible. The branching and cutting process is repeated until the entire family of problem has been solved.     

An application of gomory cuts in number theory

Frobenius has stated the following problem. Suppose thata ₁, a₂, ?, a_n are given positive integers and g.c.d. (a ₁, ? , a_n) = 1. The problem is to determine the greatest positive integerg so that the equation $$\sum\limits_{i = 1}^n {a_i x_i = g} $$ has no nonnegative integer solution. Showing the interrelation of the original problem and discrete optimization we give lower bounds for this number using Gomory cuts which are tools for solving discrete programming problems. In the first section an important theorem is cited after some remarks. In Section 2 we state a parametric knapsack problem. The Frobenius problem is equivalent with finding the value of the parameter where the optimal objective function value is maximal. The basis of this reformulation is the above mentioned theorem. Gomory's cutting plane method is applied for the knapsack problem in Section 3. Only one cut is generated and we make one dual simplex step after cutting the linear programming optimum of the knapsack problem. Applying this result we gain lower bounds for the Frobenius problem in Section 4. In the last section we show that the bounds are sharp in the sense that there are examples with arbitrary many coefficients where the lower bounds and the exact solution of the Frobenius problem coincide.     

On <Emphasis Type="Italic">g</Emphasis><Subscript><Emphasis Type="Italic">c</Emphasis></Subscript>-colorings of nearly bipartite graphs

Let G be a simple graph, let d(v) denote the degree of a vertex v and let g be a nonnegative integer function on V (G) with 0 ≤ g(v) ≤ d(v) for each vertex v ∈ V (G). A g _c -coloring of G is an edge coloring such that for each vertex v ∈ V (G) and each color c, there are at least g(v) edges colored c incident with v. The g _c -chromatic index of G, denoted by χ′g _c (G), is the maximum number of colors such that a gc-coloring of G exists. Any simple graph G has the g _c -chromatic index equal to δ _g (G) or δ _g (G) ? 1, where \({\delta _g}\left( G \right) = \mathop {\min }\limits_{v \in V\left( G \right)} \left\lfloor {d\left( v \right)/g\left( v \right)} \right\rfloor \). A graph G is nearly bipartite, if G is not bipartite, but there is a vertex u ∈ V (G) such that G ? u is a bipartite graph. We give some new sufficient conditions for a nearly bipartite graph G to have χ′g _c (G) = δ _g (G). Our results generalize some previous results due to Wang et al. in 2006 and Li and Liu in 2011.     

Light on the infinite group relaxation II: sufficient conditions for extremality,sequences, and algorithms

This is the second part of a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled Some continuous functions related to corner polyhedra I, II (Math Program 3:23–85, 1972a; Math Program 3:359–389, 1972b). The survey presents the infinite group problem in the modern context of cut generating functions. It focuses on the recent developments, such as algorithms for testing extremality and breakthroughs for the k-row problem for general \(k\ge 1\) that extend previous work on the single-row and two-row problems. The survey also includes some previously unpublished results; among other things, it unveils piecewise linear extreme functions with more than four different slopes. An interactive companion program, implemented in the open-source computer algebra package Sage, provides an updated compendium of known extreme functions.     

Light on the infinite group relaxation I: foundations and taxonomy

This is a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled Some continuous functions related to corner polyhedra I, II (Math Program 3:23–85, 359–389, 1972a, b). The survey presents the infinite group problem in the modern context of cut generating functions. It focuses on the recent developments, such as algorithms for testing extremality and breakthroughs for the k-row problem for general \(k\ge 1\) that extend previous work on the single-row and two-row problems. The survey also includes some previously unpublished results; among other things, it unveils piecewise linear extreme functions with more than four different slopes. An interactive companion program, implemented in the open-source computer algebra package Sage, provides an updated compendium of known extreme functions.     

Cyclic group blocking polyhedra

Gomory (Linear Algebra Appl 2:451–558, 1969) gave a subadditive characterization of the facets of the group polyhedron. Although there are exponentially many facets (see Gomory and Johnson in Math Program 3:359–389, 1972, Example 4.6) and exponentially many vertices for the group polyhedron for the master cyclic group problem, Gomory’s characterization of the non-trivial facets has polynomially many subadditive inequalities, in fact of order |G|² for a finite Abelian group G. We reduce this subadditive inequality system to its minimal representation by a triple system of the same order and show the dimensionality of the polytope of non-trivial facets. The system of all triples corresponds to all solution vectors of length three into which every solution vector can be decomposed. Our minimal representation leads to a characterization of the vertices of length three. Gomory et al. (Math Program 96:321–339, 2003) introduced a shooting experiment involving solving the shooting linear program repeatedly to find important facets. We develop a topological network flow model of the dual problem of the shooting linear program in a reverse procedure from the decomposition of solution vectors into triples. Hunsaker (2003) gave a knapsack shooting experiment, which we use to find a simple pattern for the most hit knapsack facets.     

Representation of the Singularities of a Function

We show that a functionfhaving a little uniform smoothness can be locally represented at any pointx₀as [equation] wheregis an indefinitely oscillatin function; the value of β of the regularity ofrare related by the 2-microlocal regularity iff.     

Lower negative decision number in a graph

Let G=(V,E) be a graph. A function f:V(G)→{?1,1} is called bad if ∑ _v∈N(v) f(v)≤1 for every v∈V(G). A bad function f of a graph G is maximal if there exists no bad function g such that g≠f and g(v)≥f(v) for every v∈V. The minimum of the values of ∑ _v∈V f(v), taken over all maximal bad functions f, is called the lower negative decision number and is denoted by β _D ^* (G). In this paper, we present sharp lower bounds on this number for regular graphs and nearly regular graphs, and we also characterize the graphs attaining those bounds.     

On the rank of odd hyper-quasi-polynomials

Given any nonzero entire function g: ? → ?, the complex linear space F(g) consists of all entire functions f decomposable as f(z + w)g(z - w)=φ₁(z)ψ₁(w)+???+ φ_n(z)ψ_n(w) for some φ₁, ψ₁, …, φ_n, ψ_n: ? → ?. The rank of f with respect to g is defined as the minimum integer n for which such a decomposition is possible. It is proved that if g is an odd function, then the rank any function in F(g) is even.     

On the Stability of the Zero Solution of a Second-Order Differential Equation under a Periodic Perturbation of the Center

Small periodic perturbations of the oscillator \(\ddot x + {x^{2n}}\) sgn x = Y(t, x, \(\dot x\)) are considered, where n < 1 is a positive integer and the right-hand side is a small perturbation periodic in t, which is an analytic function in \(\dot x\) and x in a neighborhood of the origin. New Lyapunov-type periodic functions are introduced and used to investigate the stability of the equilibrium position of the given equation. Sufficient conditions for asymptotic stability and instability are given.     

Evaluating mixed-integer programming models over multiple right-hand sides

A critical measure of model quality for a mixed-integer program (MIP) is the difference, or gap, between its optimal objective value and that of its linear programming relaxation. In some cases, the right-hand side is not known exactly; however, there is no consensus metric for evaluating a MIP model when considering multiple right-hand sides. In this paper, we provide model formulations for the expectation and extrema of absolute and relative MIP gap functions over finite discrete sets.