A study of the difference-of-convex approach for solving linear programs with complementarity constraints

This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results, including comparisons with an existing nonlinear programming solver and the mixed-integer formulation, are presented to elucidate the effectiveness of the overall DC approach.     

A lattice Boltzmann model for Maxwell’s equations

In this paper, a lattice Boltzmann model for the Maxwell’s equations is proposed by taking separate sets of distribution functions for the electric and magnetic fields, and a lattice Boltzmann model for the Maxwell vorticity equations with third order truncation error is proposed by using the higher-order moment method. At the same time, the expressions of the equilibrium distribution function and the stability conditions for this model are given. As numerical examples, some classical electromagnetic phenomena, such as the electric and magnetic fields around a line current source, the electric field and equipotential lines around an electrostatic dipole, the electric and magnetic fields around oscillating dipoles are given. These numerical results agree well with classical ones.     

Directional fields algebraic non-linear solution equations for mobile robot planning

In this study, a novel approach to robot navigation/planning by using half-cell electrochemical potentials is presented. The half-cell electrode’s potential is modelled by the Nernst equation to yield automatic search/detection of pipeline flaws by using the direct current voltage gradient (DCVG) technique. We introduce a theory of spherical volumetric electric density in the soil to sustain our postulates for navigational potential fields. The Nernst potential is correlated with the distance to a pipe’s flaw by proposing a fitted theoretical-empirical nonlinear regression model. From this, volumetric derivatives are solved as gradient-based fields to control wheeled robot’s motion. A nonlinear system for trajectory planning is proposed, and analytically solved by an algebraic solution. This solution directly adjust robot’s speed kinematic values to lead it toward the flaw. The inverse/forward kinematic constraints are non-holonomic, and are recursively integrated into the general potential equation. Analytical modelling is reported, and a set of numerical simulations are presented to prove the feasibility of the proposed formulations.     

Nonholonomic Mechanical Systems and Kaluza–Klein Theory

In the first part of the paper we present a new point of view on the geometry of nonholonomic mechanical systems with linear and affine constraints. The main geometric object of the paper is the nonholonomic connection on the distribution of constraints. By using this connection and adapted frame fields, we obtain the Newton forms of Lagrange–d’Alembert equations for nonholonomic mechanical systems with linear and affine constraints. In the second part of the paper, we show that the Kaluza–Klein theory is best presented and explained by using the framework of nonholonomic mechanical systems. We show that the geodesics of the Kaluza–Klein space, which are tangent to the electromagnetic distribution, coincide with the solutions of Lagrange–d’Alembert equations for a nonholonomic mechanical system with linear constraints, and their projections on the spacetime are the geodesics from general relativity. Any other geodesic of the Kaluza–Klein space that is not tangent to the electromagnetic distribution is also a solution of Lagrange–d’Alembert equations, but for affine constraints. In particular, some of these geodesics project exactly on the solutions of the Lorentz force equations of the spacetime.     

New formulations of the Hop-Constrained Minimum Spanning Tree problem via Miller-Tucker-Zemlin constraints

Given an undirected network with positive edge costs and a natural number p, the Hop-Constrained Minimum Spanning Tree problem (HMST) is the problem of finding a spanning tree with minimum total cost such that each path starting from a specified root node has no more than p hops (edges). In this paper, we develop new formulations for HMST. The formulations are based on Miller-Tucker-Zemlin (MTZ) subtour elimination constraints, MTZ-based liftings in the literature offered for HMST, and a new set of topology-enforcing constraints. We also compare the proposed models with the MTZ-based models in the literature with respect to linear programming relaxation bounds and solution times. The results indicate that the new models give considerably better bounds and solution times than their counterparts in the literature and that the new set of constraints is competitive with liftings to MTZ constraints, some of which are based on well-known, strong liftings of Desrochers and Laporte (1991).     

A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints

In this paper, we present a new class of polynomial length formulations for the asymmetric traveling salesman problem (ATSP) by lifting an ordered path-based model using logical restrictions in concert with the Reformulation–Linearization Technique (RLT). We show that a relaxed version of this formulation is equivalent to a flow-based ATSP model, which in turn is tighter than the formulation based on the exponential number of Dantzig–Fulkerson–Johnson (DFJ) subtour elimination constraints. The proposed lifting idea is applied to derive a variety of new formulations for the ATSP, and we explore several dominance relationships among these. We also extend these formulations to include precedence constraints in order to enforce a partial order on the sequence of cities to be visited in a tour. Computational results are presented to exhibit the relative tightness of our formulations and the efficacy of the proposed lifting process.     

Constraint-Preserving Hybrid Finite Element Methods for Maxwell’s Equations

Foundations of Computational Mathematics - Maxwell’s equations describe the evolution of electromagnetic fields, together with constraints on the divergence of the magnetic and electric flux...     

Determination of Space-Time Structures from Gravitational Perturbations

We study inverse problems for the Einstein equations with source fields in a general form. Under a microlocal linearization stability condition, we show that by generating small gravitational perturbations and measuring the responses near a freely falling observer, one can uniquely determine the background Lorentzian metric up to isometries in a region where the gravitational perturbations can travel to and return. We apply the result to two concrete examples when the source fields are scalar fields (i.e., Einstein–scalar field equations) and electromagnetic fields (i.e., Einstein-Maxwell equations). © 2019 Wiley Periodicals, Inc.     

Two basic problems in reliability-based structural optimization

Optimization of structures with respect to performance, weight or cost is a well-known application of mathematical optimization theory. However optimization of structures with respect to weight or cost under probabilistic reliability constraints or optimization with respect to reliability under cost/weight constraints has been subject of only very few studies. The difficulty in using probabilistic constraints or reliability targets lies in the fact that modern reliability methods themselves are formulated as a problem of optimization. In this paper two special formulations based on the so-called first-order reliability method (FORM) are presented. It is demonstrated that both problems can be solved by a one-level optimization problem, at least for problems in which structural failure is characterized by a single failure criterion. Three examples demonstrate the algorithm indicating that the proposed formulations are comparable in numerical effort with an approach based on semi-infinite programming but are definitely superior to a two-level formulation.     

Improvements in the treatment of stress constraints in structural topology optimization problems

Topology optimization of continuum structures is a relatively new branch of the structural optimization field. Since the basic principles were first proposed by Bendsøe and Kikuchi in 1988, most of the work has been dedicated to the so-called maximum stiffness (or minimum compliance) formulations. However, since a few years different approaches have been proposed in terms of minimum weight with stress (and/or displacement) constraints.These formulations give rise to more complex mathematical programming problems, since a large number of highly non-linear (local) constraints must be taken into account. In an attempt to reduce the computational requirements, in this paper, we propose different alternatives to consider stress constraints and some ideas about the numerical implementation of these algorithms. Finally, we present some application examples.     

A hybrid formulation of eddy current problems

In this article we examine the well‐known magneto‐quasistatic eddy current model for the behavior of low‐frequency electromagnetic fields. We restrict ourselves to formulations in the frequency domain and linear materials, but admit rather general topological arrangements. The generic eddy current model allows two dual formulations, which may be dubbed E‐based and H‐based. We investigate the so‐called hybrid approach that combines both formulations by means of coupling conditions across the boundaries of conducting regions. The resulting continuous and discrete variational formulations will be discussed, and an optimal error estimate for edge finite elements will be proved. It is worthy to note that for this approach no difficulties arise from the topology of the conducting regions. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

Nonanticipative duality,relaxations, and formulations for chance-constrained stochastic programs

We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small.     

Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows

In this paper, we develop a simultaneous column-and-row generation algorithm that could be applied to a general class of large-scale linear programming problems. These problems typically arise in the context of linear programming formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either too many to be included in the formulation directly, or the full set of linking constraints can only be identified, if all variables are generated explicitly. Due to this dependence between columns and rows, we refer to this class of linear programs as problems with column-dependent-rows. To solve these problems, we need to be able to generate both columns and rows on-the-fly within an efficient solution approach. We emphasize that the generated rows are structural constraints and distinguish our work from the branch-and-cut-and-price framework. We first characterize the underlying assumptions for the proposed column-and-row generation algorithm. These assumptions are general enough and cover all problems with column-dependent-rows studied in the literature up until now to the best of our knowledge. We then introduce in detail a set of pricing subproblems, which are used within the proposed column-and-row generation algorithm. This is followed by a formal discussion on the optimality of the algorithm. To illustrate our approach, the paper is concluded by applying the proposed framework to the multi-stage cutting stock and the quadratic set covering problems.     

Scattering relations for point‐source excitation in chiral media

A spherical electromagnetic wave propagating in a chiral medium is scattered by a bounded chiral obstacle which can have any of the usual properties. Reciprocity and general scattering theorems, relating the scattered fields due to scattering of waves from a point source put in any two different locations are established. Applying the general scattering theorem for appropriate locations and polarizations of the point source we prove an associated forward scattering theorem. Mixed scattering relations, relating the scattered fields due to a plane wave and the far‐field patterns due to a spherical wave, are also established. Copyright © 2005 John Wiley & Sons, Ltd.     

Mathematical modeling of electromagnetic wave propagation in nonlinear electrodynamics

The eikonal method for an electromagnetic wave propagating according to the laws of non-linear electrodynamics in vacuum in external electromagnetic and gravitational fields is developed. A mathematical model of the propagation of electromagnetic signals in the parameterized post-Maxwellian electrodynamics in vacuum is constructed. As an example of using the proposed method, the angles of the nonlinear electrodynamical and gravitational curvature of the normal wave rays propagating in the field of a charged collapsar are calculated.     

Modeling disjunctive constraints with a logarithmic number of binary variables and constraints

Many combinatorial constraints over continuous variables such as SOS1 and SOS2 constraints can be interpreted as disjunctive constraints that restrict the variables to lie in the union of a finite number of specially structured polyhedra. Known mixed integer binary formulations for these constraints have a number of binary variables and extra constraints linear in the number of polyhedra. We give sufficient conditions for constructing formulations for these constraints with a number of binary variables and extra constraints logarithmic in the number of polyhedra. Using these conditions we introduce mixed integer binary formulations for SOS1 and SOS2 constraints that have a number of binary variables and extra constraints logarithmic in the number of continuous variables. We also introduce the first mixed integer binary formulations for piecewise linear functions of one and two variables that use a number of binary variables and extra constraints logarithmic in the number of linear pieces of the functions. We prove that the new formulations for piecewise linear functions have favorable tightness properties and present computational results showing that they can significantly outperform other mixed integer binary formulations.     

Multicommodity flow models for spanning trees with hop constraints

In this paper we compare the linear programming relaxations of undirected and directed multicommodity flow formulations for the terminal layout problem with hop constraints. Hop constraints limit the number of hops (links) between the computer center and any terminal in the network. These constraints model delay constraints since a smaller number of hops decreases the maximum delay transmission time in the network. They also model reliability constraints because with a smaller number of hops there is a lower route loss probability. Hop constraints are easily modelled with the variables involved in multicommodity flow formulations. We give some empirical evidence showing that the linear programming relaxation of such formulations give sharp lower bounds for this hop constrained network design problem. On the other hand, these formulations lead to very large linear programming models. Therefore, for bounding purposes we also derive several lagrangean based procedures from a directed multicommodity flow formulation and present some computational results taken from a set of instances with up to 40 nodes.     

Formalism of two potentials for the numerical solution of Maxwell’s equations

A new formulation of Maxwell’s equations based on the introduction of two vector and two scalar potentials is proposed. As a result, the electromagnetic field equations are written as a hyperbolic system that contains, in contrast to the original Maxwell system, only evolution equations and does not involve equations in the form of differential constraints. This makes the new equations especially convenient for the numerical simulation of electromagnetic processes. Specifically, they can be solved by applying powerful modern shock-capturing methods based on the approximation of spatial derivatives by upwind differences. The cases of an electromagnetic field in a vacuum and an inhomogeneous material are considered. Examples are given in which electromagnetic wave propagation is simulated by solving the formulated system of equations with the help of modern high-order accurate schemes.     

A control-theoretic approach to the plasma confinement problem

The problem of confining a collisionless plasma by means of external electromagnetic fields is formulated as an optimal control or variational problem. The paper begins with a formal development of the equations governing the plasma motion. Then, various mathematical formulations of the confinement problem are discussed. Specific results are obtained for the simplified case where confinement is achieved by means of a spatially uniform, time-varying magnetic field. Physical interpretations of these results are also given.This work was supported by the Office of Scientific Research of the United States Air Force under Grant No. AFOSR-68-1547.