A closed-form representation of mixed-integer program value functions

We identify a class of formulas computable in polynomial time such that the functions defined by these formulas are precisely the value functions of mixed-integer programs with rational constraint coefficients.     

Constructive modal logics I

We often have to draw conclusions about states of machines in computer science and about states of knowledge and belief in artificial intelligence (AI) based on partial information. Nerode (1990) suggested using constructive (equivalently, intuitionistic) logic as the language to express such deductions and also suggested designing appropriate intuitionistic Kripke frames to express the partial information. Following this program, Nerode and Wijesekera (1990) developed syntax, semantics and completeness for a system of intuitionistic dynamic logic for proving properties of concurrent programs. Like all dynamics logics, this was a logic of many modalities, each expressing a program, but in intuitionistic rather than in classical logic. In that logic, both box and diamond are needed, but these two are not intuitionistically interdefinable and, worse, diamond does not distribute over ‘or’, except for sequential programs. This also happens in other contemplated computer science and AI applications, and leads outside the class of constructive logics investigated in the literature. The present paper fills this gap. We provide intuitionistic logics with independent box and diamond without assuming distribution of diamond over ‘or’. The completeness theorem is based on intuitionistic Kripke frames (partially ordered sets of increasing worlds), but equipped with an additional, quite separate accessibility relation between worlds. In the interpretation of Nerode and Wijesekera (1990), worlds under the partial order represent states of partial knowledge, the accessibility represents change in state of partial knowledge resulting from executing a specific program. But there are many other computer science interpretations. This formalism covers all computer science applications of which we are aware. We also give a cut elimination theorem and algebraic and topological formulations, since these present some new difficulties. Finally, these results were obtained prior to those in Nerode and Wijesekera (1990).     

Directional derivatives for the value-function in semi-infinite programming

For the problemP(λ): Maximizec ^T z subject toz∈Z(λ), whereZ(λ) is defined by an in general infinite set of linear inequalities, it is shown that the value-function has directional derivatives at every point such thatP( ) and its dual are both superconsistent. To compute these directional derivatives a min-max-formula, well-known in convex programming, is derived. In addition, it is shown that derivatives can be obtained more easily by a limit-process using only convergent selections of solutions ofP(λ _n ), λ _n → and their duals.     

The value-function of an infinite-horizon linear-quadratic problem

For a discrete-time infinite-horizon linear-quadratic optimal control problem, under the assumption of the nonemptyness of the set of the admissible processes, we prove the existence and the uniqueness of an optimal process, we prove that the value-function is a quadratic function of the initial state, and we characterize the matrix of this quadratic value-function among the solutions of an algebraic Riccati equation by using a fixed-point theorem.     

A compact formulation of a mixed-integer set

We consider mixed-integer sets of the form X = {(s, y) ∈ ?₊ × ? ⁿ : s + a _j y _j ≥ b _j , ?j ∈ N}. A polyhedral characterization for the case where X is defined by two inequalities is provided. From that characterization we give a compact formulation for the particular case where the coefficients of the integer variables can take only two possible integer values a ₁, a ₂ ∈ ?₊ : X _n,m = {(s, y) ∈ ?₊ × ? ^n+m : s + a ₁ y _j ≥ b _j , ?j ∈ N ₁, s + a ₂ y _j ≥ b _j , j ∈ N ₂} where N ₁ = {1, …, n}, N ₂ = {n + 1, …, n + m}. In addition, we discuss families of facet-defining inequalities for the convex hull of X _n,m .     

Constructive Descriptions of Functional Classes by Polynomial Approximations. I

The Hölder classes of functions analytic in a domain D are considered. In the case where D has bounded boundary rotation and no zero exterior angles, a collection of polynomial approximations describing these classes of functions is constructed, which is economical in a certain sense. Bibliography: 10 titles.     

Constructive characterizations of （γp, γ）- and （γp, γpr）-trees

Let G = （V, E） be a graph without isolated vertices. A set S lohtain in V is a domination set of G if every vertex in V - S is adjacent to a vertex in S, that is N[S] = V. The domination number of G, denoted by γ（G）, is the minimum cardinality of a domination set of G. A set S lohtain in V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S] has a perfect matching. The paired-domination number, denoted by γpr（G）, is defined to be the minimum cardinality of a paired-domination set S in G. A subset S lohtain in V is a power domination set of G if all vertices of V can be observed recursively by the following rules： （i） all vertices in N[S] are observed initially, and （ii） if an observed vertex u has all neighbors observed except one neighbor v, then v is observed （by u）. The power domination number, denoted by γp（G）, is the minimum cardinality of a power domination set of G. In this paper, the constructive characterizations for trees with γp=γ and γpr = γp are provided respectively.     

Biology as a Constructive Physics

Yuri Manin’s approach to Zipf’s law (Kolmogorov complexity as energy) is applied to investigation of biological evolution. Model of constructive statistical mechanics where complexity is a contribution to energy is proposed to model genomics. Scaling laws in genomics are discussed in relation to Zipf’s law. This gives a model of Eugene Koonin’s Third Evolutionary Synthesis – physical model which should describe scaling in genomics.     

Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs.     

Convex approximations for a class of mixed-integer recourse models

We consider mixed-integer recourse (MIR) models with a single recourse constraint. We relate the second-stage value function of such problems to the expected simple integer recourse (SIR) shortage function. This allows to construct convex approximations for MIR problems by the same approach used for SIR models.     

Branch-and-price for a class of nonconvex mixed-integer nonlinear programs

This work attempts to combine the strengths of two major technologies that have matured over the last three decades: global mixed-integer nonlinear optimization and branch-and-price. We consider a class of generally nonconvex mixed-integer nonlinear programs (MINLPs) with linear complicating constraints and integer linking variables. If the complicating constraints are removed, the problem becomes easy to solve, e.g. due to decomposable structure. Integrality of the linking variables allows us to apply a discretization approach to derive a Dantzig-Wolfe reformulation and solve the problem to global optimality using branch-andprice. It is a remarkably simple idea; but to our surprise, it has barely found any application in the literature. In this work, we show that many relevant problems directly fall or can be reformulated into this class of MINLPs. We present the branch-and-price algorithm and demonstrate its effectiveness (and sometimes ineffectiveness) in an extensive computational study considering multiple large-scale problems of practical relevance, showing that, in many cases, orders-of-magnitude reductions in solution time can be achieved.

     

The limiting behavior of the value-function for variational problems arising in continuum mechanics

In this paper we study the limiting behavior of the value-function for one-dimensional second order variational problems arising in continuum mechanics. The study of this behavior is based on the relation between variational problems on bounded large intervals and a limiting problem on [0,∞)$[0,\infty )$.     

Krasnosel'skii-type characterizations for a cone

Three combinatorial criteria for cones involving the concepts of R-visibility and clear R-visibility introduced for sets in Euclidean space are established. They are direct analogues of Krasnosel'skii-type theorems existing for starshaped sets.The author is with the Department of Mathematics, University of Notre Dame, Indiana, on leave from the Mathematical Institute of the Polish Academy of Sciences.