On coderivatives and Lipschitzian properties of the dual pair in optimization

In this paper, we apply the concept of coderivative and other tools from the generalized differentiation theory for set-valued mappings to study the stability of the feasible sets of both the primal and the dual problem in infinite-dimensional linear optimization with infinitely many explicit constraints and an additional conic constraint. After providing some specific duality results for our dual pair, we study the Lipschitz-like property of both mappings and also give bounds for the associated Lipschitz moduli. The situation for the dual shows much more involved than the case of the primal problem.     

Normal analytic polyhedra in ℂ2 with a noncompact automorphism group

Let P be a bounded analytic polyhedron in ℂ² whose boundary is smooth except for normal crossing singularities. We show that P is a holomorphic quotient of the bidisc, if its automorphism group is noncompact.     

Local branching

The availability of effective exact or heuristic solution methods for general Mixed-Integer Programs (MIPs) is of paramount importance for practical applications. In the present paper we investigate the use of a generic MIP solver as a black-box ``tactical' tool to explore effectively suitable solution subspaces defined and controlled at a ``strategic' level by a simple external branching framework. The procedure is in the spirit of well-known local search metaheuristics, but the neighborhoods are obtained through the introduction in the MIP model of completely general linear inequalities called local branching cuts. The new solution strategy is exact in nature, though it is designed to improve the heuristic behavior of the MIP solver at hand. It alternates high-level strategic branchings to define the solution neighborhoods, and low-level tactical branchings to explore them. The result is a completely general scheme aimed at favoring early updatings of the incumbent solution, hence producing high-quality solutions at early stages of the computation. The method is analyzed computationally on a large class of very difficult MIP problems by using the state-of-the-art commercial software ILOG-Cplex 7.0 as the black-box tactical MIP solver. For these instances, most of which cannot be solved to proven optimality in a reasonable time, the new method exhibits consistently an improved heuristic performance: in 23 out of 29 cases, the MIP solver produced significantly better incumbent solutions when driven by the local branching paradigm. Mathematics Subject Classification (2000):90C06, 90C10, 90C11, 90C27, 90C59     

Integer linear programming models for 2-staged two-dimensional Knapsack problems

 We are given a unique rectangular piece of stock material S, with height H and width W, and a list of m rectangular shapes to be cut from S. Each shape's type i (i = 1, ..., m) is characterized by a height , a width , a profit , and an upper bound ub _i indicating the maximum number of items of type i which can be cut. We refer to the Two-Dimensional Knapsack (TDK) as the problem of determining a cutting pattern of S maximizing the sum of the profits of the cut items. In particular, we consider the classical variant of TDK in which the maximum number of cuts allowed to obtain each item is fixed to 2, and we refer to this problem as 2-staged TDK (2TDK). For the 2TDK problem we present two new Integer Linear Programming models, we discuss their properties, and we compare them with other formulations in terms of the LP bound they provide. Finally, both models are computationally tested within a standard branch-and-bound framework on a large set of instances from the literature by reinforcing them with the addition of linear inequalities to eliminate symmetries. Received: October 17, 2000 / Accepted: December 19, 2001 Published online: September 27, 2002 Key words. packing – cutting – integer linear programming     

Primal separation algorithms

Given an integer polyhedron , an integer point , and a point , the primal separation problem is the problem of finding a linear inequality which is valid for P _I , violated by x ^*, and satisfied at equality by . The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well-known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.Received: November 2002, Revised: March 2003,     

Primal cutting plane algorithms revisited

Dual fractional cutting plane algorithms, in which cutting planes are used to iteratively tighten a linear relaxation of an integer program, are well-known and form the basis of the highly successful branch-and-cut method. It is rather less well-known that various primal cutting plane algorithms were developed in the 1960s, for example by Young. In a primal algorithm, the main role of the cutting planes is to enable a feasible solution to the original problem to be improved. Research on these algorithms has been almost non-existent.  In this paper we argue for a re-examination of these primal methods. We describe a new primal algorithm for pure 0-1 problems based on strong valid inequalities and give some encouraging computational results. Possible extensions to the case of general mixed-integer programs are also discussed.     

On Weighted Poincaré Inequalities

We are concerned with the problem of finding sharp summability conditions on the weights which render certain weighted inequalities of Poincaré - type true. The conditions we find consist of proper integral balances between the growths of the rearrangements of the weights.     

Is breaking of ensemble equivalence monotone in the number of constraints?

Breaking of ensemble equivalence between the microcanonical ensemble and the canonical ensemble may occur for random graphs whose size tends to infinity, and is signaled by a non-zero specific relative entropy between the two ensembles. In Garlaschelli et al. (2017) and Garlaschelli et al. (0000) it was shown that breaking occurs when the constraint is put on the degree sequence (configuration model). It is not known what is the effect on the relative entropy when the number of constraints is reduced, i.e., when only part of the nodes are constrained in their degree (and the remaining nodes are left unconstrained). Intuitively, the relative entropy is expected to decrease. However, this is not a trivial issue because when constraints are removed both the microcanonical ensemble and the canonical ensemble change. In this paper a formula for the relative entropy valid for generic discrete random structures, recently formulated by Squartini and Garlaschelli, is used to prove that the relative entropy is monotone in the number of constraints when the constraint is on the degrees of the nodes. It is further shown that the expression for the relative entropy corresponds, in the dense regime, to the degrees in the microcanonical ensemble being asymptotically multivariate Dirac and in the canonical ensemble being asymptotically Gaussian.     

Nonlinear Double-well Schrödinger Equations in the Semiclassical Limit

We consider time-dependent Schrödinger equations with a double well potential and an external nonlinear, both local and non-local, perturbation. In the semiclassical limit, the finite dimensional eigenspace associated to the lowest eigenvalues of the linear operator is almost invariant for times of the order of the beating period and the dominant term of the wavefunction is given by means of the solutions of a finite dimensional dynamical system. In the case of local nonlinear perturbation, we assume the spatial dimension d=1 or d=2.     

Global symplectic coordinates on gradient Kähler–Ricci solitons

A classical result of McDuff [14] asserts that a simply connected complete Kähler manifold $(M,g,\omega )$ with non positive sectional curvature admits global symplectic coordinates through a symplectomorphism $\Psi \ : M \rightarrow \mathbb{R }^{2n}$ (where $n$ is the complex dimension of $M$ ), satisfying the following property (proved by E. Ciriza in [4]): the image $\Psi (T)$ of any complex totally geodesic submanifold $T\subset M$ through the point $p$ such that $\Psi (p)=0$ , is a complex linear subspace of $\mathbb C ^n\simeq \mathbb{R }^{2n}$ . The aim of this paper is to exhibit, for all positive integers $n$ , examples of $n$ -dimensional complete Kähler manifolds with non-negative sectional curvature globally symplectomorphic to $\mathbb{R }^{2n}$ through a symplectomorphism satisfying Ciriza’s property.