A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting

We study the set of 0–1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 0–1 knapsack polytope and the 0–1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions using sequence-independent lifting. For problems with a single cardinality constraint, we derive two-dimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints. Finally, we present preliminary computational results aimed at evaluating the strength of the cuts obtained from sequence-independent lifting with respect to those obtained from sequential lifting.     

The Relaxed Intertwining Lifting in the Coupling Approach

We discuss the relaxed lifting theorem by using a coupling framework. A simple proof of the existence of the relaxed lifting is given; the approach also yields a sufficient condition for uniqueness of the lifting. We investigate in more detail a particular case, in which a complete parametrization of solutions can be obtained.     

Nondecomposable solutions to group equations and an application to polyhedral combinatorics

This paper is based on the study of the set of nondecomposable integer solutions in a Gomory corner polyhedron, which was recently used in a reformulation method for integer linear programs. In this paper, we present an algorithm for efficiently computing this set. We precompute a database of nondecomposable solutions for cyclic groups up to order 52. As a second application of this database, we introduce an algorithm for computing nontrivial simultaneous lifting coefficients. The lifting coefficients are exact for a discrete relaxation of the integer program that consists of a group relaxation plus bound constraints. Received: November 2004 / Revised version: June 2005 AMS classification: 90C10, 90C57     

Regularity theory for the generalized Neumann problem for Yang-Mills Connections – Non-trivial examples in dimensions 3 and 4

We develop the existence and regularity theory for the generalized Neumann problem for Yang-Mills connections. This is the most general boundary value problem for connections on a compact manifold with smooth boundary, with geometric meaning. It is obtained by reflecting the base manifold across its boundary and lifting this action non-trivially to the bundle. The prescribed lifting corresponds to a geometric invariant, which is similar to the monopole number. When this invariant is non-zero, there exist non-trivial solutions of the generalized Neumann problem. We prove the existence of non-trivial solutions over the 3-dimensional disk and over the 4-dimensional manifold We outline the procedure for finding non-trivial examples of solutions over more general manifolds of dimension 3 and 4. Received: 20 June 1999     

Relaxation of metric constrained interpolation and a new lifting theorem

In this paper a new lifting interpolation problem is introduced and an explicit solution is given. The result includes the commutant lifting theorem as well as its generalizations in [27] and [2]. The main theorem yields explicit solutions to new natural variants of most of the metric constrained interpolation problems treated in [9]. It is also shown that via an infinite dimensional enlargement of the underlying geometric structure a solution of the new lifting problem can be obtained from the commutant lifting theorem. However, the new setup presented obtained from the commutant lifting theorem. However, the new setup presented in this paper appears to be better suited to deal with interpolations problems from systems and control theory than the commutant lifting theorem.Dedicated to Israel Gohberg, as a token of admiration for his inspiring work in analysis and operator theory, with its far reaching applications, in friendship and with great affection.     

Discrete time-variant interpolation as classical interpolation with an operator argument

Necessary and sufficient conditions are derived for the existence of solutions to discrete time-variant interpolation problems of Nevanlinna-Pick and Nudelman type. The proofs are based on a reduction scheme which allows one to treat these time-variant interpolation problems as classical interpolation problems for operator-valued functions with operator arguments. The latter ones are solved by using the commutant lifting theorem.     

Counting Fixed Points and Rooted Closed Walks of the Singular Map $$x \mapsto {x^{{x^n}}}$$x↦xxn Modulo Powers of a Prime

The “self-power” map x ⟼ xx modulo m and its generalized form $$x \mapsto {x^{{x^n}}}$$ modulo m are of considerable interest for both theoretical reasons and for potential applications to cryptography. In this paper, we use p-adic methods, primarily p-adic interpolation, Hensel’s lemma, and lifting singular points modulo p, to count fixed points and rooted closed walks of equations related to these maps when m is a prime power. In particular, we introduce a new technique for lifting singular solutions of several congruences in several unknowns using the left kernel of the Jacobian matrix.     

多机器人协调吊运系统逆运动学分析及优化

针对紧耦合多机器人协调吊运系统的逆运动学问题进行了分析,首先利用几何关系和力旋量平衡方程建立了系统的运动学模型和动力学模型;然后对系统的逆运动学进行分析,将其分为变柔索长度和固定柔索长度两种情况分别进行分析;随后对运动学逆解在某一时刻存在无穷多解、多组解和无解的情况分别给出了解决方法,对存在多组解的情况,提出一优化目标求解最优解;最后结合软件UG/ADAMS/MATLAB建立了系统的实验平台,通过实例仿真计算验证了方法的有效性,为后续进一步研究系统运动稳定性、优化拉力分布和控制算法奠定了基础.     

Solvability of an inhomogeneous boundary value problem for steady MHD equations

In this paper, we consider the steady MHD equations with inhomogeneous boundary conditions for the velocity and the tangential component of the magnetic field. Using a new construction of the magnetic lifting, we obtain existence of weak solutions under sharp assumption on boundary data for the magnetic field.     

The Inverse Commutant Lifting Problem. I: Coordinate-Free Formalism

It is known that the set of all solutions of a commutant lifting and other interpolation problems admits a Redheffer linear-fractional parametrization. The method of unitary coupling identifies solutions of the lifting problem with minimal unitary extensions of a partially defined isometry constructed explicitly from the problem data. A special role is played by a particular unitary extension, called the central or universal unitary extension. The coefficient matrix for the Redheffer linear-fractional map has a simple expression in terms of the universal unitary extension. The universal unitary extension can be seen as a unitary coupling of four unitary operators (two bilateral shift operators together with two unitary operators coming from the problem data) which has special geometric structure. We use this special geometric structure to obtain an inverse theorem (Theorem 8.4) which characterizes the coefficient matrices for a Redheffer linear-fractional map arising in this way from a lifting problem. The main tool is the formalism of unitary scattering systems developed in Boiko et al. (Operator theory, system theory and related topics (Beer-Sheva/Rehovot 1997), pp. 89–138, 2001) and Kheifets (Interpolation theory, systems theory and related topics, pp. 287–317, 2002)     

Column Generation for Extended Formulations

Working in an extended variable space allows one to develop tight reformulations for mixed integer programs (MIP). However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. When the extended formulation stems from a decomposition principle, as typical in practice, a column generation procedure that mimics that for the Dantzig-Wolfe reformulation can be applied to the extended formulation. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solution. Such “column-and-row generation” procedure is reviewed with the goal to analyse the approachʼs potential benefits compared to a standard column generation approach. Numerical experiments highlight a key observation: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.     

A methodology to create robust job rotation schedules

This research proposes a methodology for developing robust job rotation schedules to reduce the likelihood of low back injury due to lifting. We consider settings that have uncertain task demands and different worker profiles in order to simulate real settings. We begin by considering deterministic versions of the problem and solve these using mathematical programming. Because mathematical programming cannot be readily applied to stochastic versions of the problem, heuristic solution methods are developed. The effectiveness of these methods is demonstrated by comparing the results with provably optimal solutions from the deterministic problems and with an enumerative approach that is applied to the stochastic version of the problem. Across the test problems, the proposed heuristics are effective at finding good job rotation solutions. The proposed methods could also be applied to solve other job rotation objectives such as maximizing productivity and reducing exposure to other work environmental factors such as excessive noise.     

An ensemble of idempotent lifting hypotheses

Lifting idempotents modulo ideals is an important tool in studying the structure of rings. This paper lays out the consequences of lifting other properties modulo ideals, including lifting of von Neumann regular elements, lifting isomorphic idempotents, and lifting conjugate idempotents. Applications are given for IC rings, perspective rings, and Dedekind-finite rings, which improve multiple results in the literature. We give a new characterization of the class of exchange rings; they are rings where regular elements lift modulo all left ideals.We also uncover some hidden connections between these lifting properties. For instance, if regular elements lift modulo an ideal, then so do isomorphic idempotents. The converse is true when units lift. The logical relationships between these and several other important lifting properties are completely characterized. Along the way, multiple examples are developed that illustrate limitations to the theory.     

二进小波的构造方法研究

提出两种二进小波的构造方法.首先,将Mallat构造的B-样条二进小波推广得到一种构造B-样条二进小波的新方法;其次,基于二进提升方案提出构造二进小波的另一种新方法—–构造定理,并通过调整定理中提升参数的形式、以新的B-样条二进小波作为初始二进小波,具体构造了具有有限长单位脉冲响应、高阶消失矩、线性相位的提升二进小波,这些提升二进小波不能由Sweldens提升方案得到.     

Lifting the facets of zero–one polytopes

We discuss a procedure to obtain facets and valid inequalities for the convex hull of the set of solutions to a general zero–one programming problem. Basically, facets and valid inequalities defined on lower dimensional subpolytopes are lifted into the space of the original problem. The procedure generalizes the previously known techniques for lifting facets in two respects. First, the general zero–one programming problem is considered rather than various special cases. Second, the procedure is exhaustive in the sense that it accounts for all the facets (valid inequalities) which are liftings of a given lower dimensional facet (valid inequality).