RENS

This article introduces rens, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programs (MINLPs). It uses a sub-MINLP to explore the set of feasible roundings of an optimal solution $\bar{x}$ of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables $x_j$ with $\bar{x} _{j} \in \mathbb {Z}$ and bounding the remaining integer variables to $x_{j} \in \{ \lfloor \bar{x} _{j} \rfloor , \lceil \bar{x} _{j} \rceil \}$ . We describe two different applications of rens: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver. We use the former to compare different kinds of relaxations and the impact of cutting planes on the so-called roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework scip. Finally, we study the impact of rens when it is applied as a primal heuristic inside scip. All experiments were performed on three publicly available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLP s, using solely software which is available in source code. It turns out that for these problem classes 60 to 70 % of the instances have roundable relaxation optima and that the success rate of rens does not depend on the percentage of fractional variables. Last but not least, rens applied as primal heuristic complements nicely with existing primal heuristics in scip.     

On the approximation performance of fictitious play in finite games

We study the performance of Fictitious Play (FP), when used as a heuristic for finding an approximate Nash equilibrium of a two-player game. We exhibit a class of two-player games having payoffs in the range $[0,1]$ that show that FP fails to find a solution having an additive approximation guarantee significantly better than $1/2$ . Our construction shows that for $n\times n$ games, in the worst case both players may perpetually have mixed strategies whose payoffs fall short of the best response by an additive quantity $1/2 - O(1/n^{1-\delta })$ for arbitrarily small $\delta $ . We also show an essentially matching upper bound of $1/2 - O(1/n)$ .     

The General Solution of Abel-Type Functional Equations

The general measurable solution of (A) was found by Stamate [8]. Aczél [3] and Lajkô [6] proved that the general solution of (A) for unknown functions ψ, g, h: ? → ? are (1), (2) and (3), respectively. Filipescu [5] found the general measurable solution of (B). We establish an elementary prof for the general solution of equation (A) (Theorem 1.). Our method is suitable for finding the general solution of (B) (Theorem 2.).     

Representations of the Restricted Lie Color Algebras

Let $ \mathfrak{g} $ be a restricted Lie color algebra. We define the p-character χ and study the χ-reduced enveloping algebras. We define the reductive Lie color algebras and FP triples, and study the representations associated with FP triples. As an application, we prove an analogue of the Kac-Weisfeiler theorem and determine the simplicity of the baby Verma module for the general linear Lie color algebra $ \mathfrak{g}= {\rm{gl}} (V)$ .     

Multi-bump positive solutions for a nonlinear elliptic problem in expanding tubular domains

In this paper we study the existence of multi-bump positive solutions of the following nonlinear elliptic problem: $$\begin{aligned} -\Delta u=u^p \quad \text{ in }\; \Omega _t,\quad u=0 \quad \text{ on }\; \partial \Omega _t. \end{aligned}$$ Here $1<p<\frac{N+2}{N-2}$ when $N\ge 3,\,1<p<\infty $ when $N=2$ and $\Omega _t$ is a tubular domain which expands as $t\rightarrow \infty $ . See (1.6) below for a precise definition of expanding tubular domain. When the section $D$ of $\Omega _t$ is a ball, the existence of multi-bump positive solutions is shown by Dancer and Yan (Commun Partial Differ Equ, 27(1–2), 23–55, 2002) and by Ackermann et al. (Milan J Math, 79(1), 221–232, 2011) under the assumption of a non-degeneracy of a solution of a limit problem. In this paper we introduce a new local variational method which enables us to show the existence of multi-bump positive solutions without the non-degeneracy condition for the limit problem. In particular, we can show the existence for all $N\ge 2$ without the non-degeneracy condition. Moreover we can deal with more general domains, for example, a domain whose section is an annulus, for which least energy solutions of the limit problem are really degenerate.     

An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general solution method based on quadratic convex reformulation, that we called MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach Compact Quadratic Convex Reformulation (CQCR). We evaluate CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that CQCR is much faster than MIQCR and than the general non-linear solver BARON (Sahinidis and Tawarmalani, User??s manual, 2010) to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare MIQCR and CQCR on instances of the Constrained Task Assignment Problem. These experiments show that CQCR can solve instances that MIQCR and other existing methods fail to solve.     

Rounding Procedures for the Discrete Version of the Capacitated Economic Order Quantity Problem

The capacitated Economic Order Quantity problem (capacitated EOQ) is a well-known problem where products have to be shipped between two points with a vehicle of given capacity. Each shipment has a fixed cost, independent of the shipped quantity, and an inventory cost is generated in the two points. The problem consists in finding the optimal time between consecutive shipments, which minimizes the total cost. The problem is a capacitated variant of the EOQ problem and has a closed form solution. Since such solution is often irrational, it is often rounded to an integer value. In this paper we investigate the errors which are generated by rounding procedures to integer and powers-of-two values. We show that, although in the worst case a tight general relative error of 2 is generated by all the considered rounding procedures, the procedure which rounds to the best between the lower and upper values (integer or powers-of-two) has a performance of $\frac{1}{2}$ ( $\sqrt 2 + 1/\sqrt 2 $ )≈1.06 on classes of instances of high practical relevance.     

Problems with resource allocation constraints and optimization over the efficient set

The paper studies a nonlinear optimization problem under resource allocation constraints. Using quasi-gradient duality it is shown that the feasible set of the problem is a singleton (in the case of a single resource) or the set of Pareto efficient solutions of an associated vector maximization problem (in the case of $k>1$ resources). As a result, a nonlinear optimization problem under resource allocation constraints reduces to an optimization over the efficient set. The latter problem can further be converted into a quasiconvex maximization over a compact convex subset of $\mathbb{R }^k_+.$ Alternatively, it can be approached as a bilevel program and converted into a monotonic optimization problem in $\mathbb{R }^k_+.$ In either approach the converted problem falls into a common class of global optimization problems for which several practical solution methods exist when the number $k$ of resources is relatively small, as it often occurs.     

From pointwise to local regularity for solutions of Hamilton–Jacobi equations

It is well-known that solutions to the Hamilton–Jacobi equation $$\begin{aligned} u_{t}(t,x)+H(x,u_{x}(t,x))=0 \end{aligned}$$ fail to be everywhere differentiable. Nevertheless, suppose a solution $u$ turns out to be differentiable at a given point $(t,x)$ in the interior of its domain. May then one deduce that $u$ must be continuously differentiable in a neighborhood of $(t,x)$ ? Although this question has a negative answer in general, our main result shows that it is indeed the case when the proximal subdifferential of $u(t,\cdot )$ at $x$ is nonempty. Our approach uses the representation of $u$ as the value function of a Bolza problem in the calculus of variations, as well as necessary conditions for such a problem.     

The extremal solution for the fractional Laplacian

We study the extremal solution for the problem \((-\Delta )^s u=\lambda f(u)\) in \(\Omega \) , \(u\equiv 0\) in \(\mathbb R ^n\setminus \Omega \) , where \(\lambda >0\) is a parameter and \(s\in (0,1)\) . We extend some well known results for the extremal solution when the operator is the Laplacian to this nonlocal case. For general convex nonlinearities we prove that the extremal solution is bounded in dimensions \(n<4s\) . We also show that, for exponential and power-like nonlinearities, the extremal solution is bounded whenever \(n<10s\) . In the limit \(s\uparrow 1\) , \(n<10\) is optimal. In addition, we show that the extremal solution is \(H^s(\mathbb R ^n)\) in any dimension whenever the domain is convex. To obtain some of these results we need \(L^q\) estimates for solutions to the linear Dirichlet problem for the fractional Laplacian with \(L^p\) data. We prove optimal \(L^q\) and \(C^\beta \) estimates, depending on the value of \(p\) . These estimates follow from classical embedding results for the Riesz potential in \(\mathbb R ^n\) . Finally, to prove the \(H^s\) regularity of the extremal solution we need an \(L^\infty \) estimate near the boundary of convex domains, which we obtain via the moving planes method. For it, we use a maximum principle in small domains for integro-differential operators with decreasing kernels.     

Existence of entire solutions for a class of quasilinear elliptic equations

The paper deals with the existence of entire solutions for a quasilinear equation ${(\mathcal E)_\lambda}$ in ${\mathbb{R}^N}$ , depending on a real parameter λ, which involves a general elliptic operator in divergence form A and two main nonlinearities. The competing nonlinear terms combine each other, being the first subcritical and the latter supercritical. We prove the existence of a critical value λ* > 0 with the property that ${(\mathcal E)_\lambda}$ admits nontrivial non-negative entire solutions if and only if λ ≥ λ*. Furthermore, when ${\lambda > \overline{\lambda} \ge \lambda^*}$ , the existence of a second independent nontrivial non-negative entire solution of ${(\mathcal{E})_\lambda}$ is proved under a further natural assumption on A.     

Doubly periodic self-dual vortices in a relativistic non-Abelian Chern–Simons model

In this paper we establish a multiplicity result concerning the existence of doubly periodic solutions in a $2\times 2$ nonlinear elliptic system arising in the study of self-dual non-Abelian Chern–Simons vortices. We show that the system admits at least two solutions when the Chern–Simons coupling parameter $\kappa >0$ is sufficiently small; while no solution exists for $\kappa >0$ sufficiently large. As in Nolasco and Tarantello (Commun Math Phys 213:599–639, 2000), we use a variational formulation of the problem. Thus, we obtain a first solution via a constrained minimization method and show that it is asymptotically gauge-equivalent to the (broken) principal embedding vacuum of the system, as $\kappa \rightarrow 0$ . Then we obtain a second solution by a min-max procedure of “mountain pass” type.     

Uniqueness of almost periodic-in-time solutions to Navier�CStokes equations in unbounded domains

We present a uniqueness theorem for almost periodic-in-time solutions to the Navier?CStokes equations in 3-dimensional unbounded domains. Thus far, uniqueness of almost periodic-in-time solutions to the Navier?CStokes equations in unbounded domain, roughly speaking, is known only for a small almost periodic-in-time solution in ${BC(\mathbb {R};L^{3}_w)}$ within the class of solutions that have sufficiently small ${L^{\infty}(L^{3}_w)}$ -norm. In this paper, we show that a small almost periodic-in-time solution in ${BC(\mathbb {R};L^{3}_w\cap L^{6,2})}$ is unique within the class of all almost periodic-in-time solutions in ${BC(\mathbb {R};L^{3}_w\cap L^{6,2})}$ . The proof of the present uniqueness theorem is based on the method of dual equations.     

New approaches to multi-objective optimization

A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Many classical optimization problems, such as maximum spanning tree and forest, shortest path, maximum weight (perfect) matching, maximum weight independent set (basis) in a matroid or in the intersection of two matroids, become NP-hard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. Not much is known however about the case of two or more budgets: filling this gap, at least partially, is the main goal of this paper. In more detail, we obtain the following main results: Using iterative rounding for the first time in multi-objective optimization, we obtain multi-criteria PTASs (which slightly violate the budget constraints) for spanning tree, matroid basis, and bipartite matching with \(k=O(1)\) budget constraints. We present a simple mechanism to transform multi-criteria approximation schemes into pure approximation schemes for problems whose feasible solutions define an independence system. This gives improved algorithms for several problems. In particular, this mechanism can be applied to the above bipartite matching algorithm, hence obtaining a pure PTAS. We show that points in low-dimensional faces of any matroid polytope are almost integral, an interesting result on its own. This gives a deterministic approximation scheme for \(k\) -budgeted matroid independent set. We present a deterministic approximation scheme for \(k\) -budgeted matching (in general graphs), where \(k=O(1)\) . Interestingly, to show that our procedure works, we rely on a non-constructive result by Stromquist and Woodall, which is based on the Ham Sandwich Theorem.     

An empirical evaluation of walk-and-round heuristics for mixed integer linear programs

Feasibility pump is a general purpose technique for finding feasible solutions of mixed integer programs. In this paper we report our computational experience on using geometric random walks and a random ray approach to provide good points for the feasibility pump. Computational results on MIPLIB2003 and COR@L test libraries show that the walk-and-round approach improves the upper bounds of a large number of test problems when compared to running the feasibility pump either at the optimal solution or the analytic center of the continuous relaxation. In our experiments the hit-and-run walk (a specific type of random walk strategy) started from near the analytic center is generally better than other random search approaches, when short walks are used. The performance may be improved by expanding the feasible region before walking. Although the upper bound produced in the geometric random walk approach are generally inferior than the best available upper bounds for the test problems, we managed to prove optimality of three test problems which were considered unsolved in the COR@L benchmark library (though the COR@L bounds available to us seem to be out of date).     

Elliptic equations with jumping nonlinearities involving high eigenvalues

We present some multiplicity results concerning semilinear elliptic Dirichlet problems with jumping nonlinearities where the jumping condition involves a set of high eigenvalues not including the first one. Using a variational method we show that the number of solutions may be arbitrarily large provided the number of jumped eigenvalues is large enough. Indeed, we prove that for every positive integer $k$ there exists a positive integer $n(k)$ such that, if the number of jumped eigenvalues is greater than $n(k),$ then the problem has at least a solution which presents $k$ peaks. Moreover, we describe the asymptotic behaviour of the solutions as the number of jumped eigenvalues tends to infinity; in particular, we analyse some concentration phenomena of the peaks (near points or suitable manifolds), we describe the asymptotic profile of the rescaled peaks, etc $\ldots $      

On linear and semidefinite programming relaxations for hypergraph matching

The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are the following:

We consider the standard linear programming relaxation of the problem. We provide an algorithmic proof of a result of Füredi, Kahn and Seymour, showing that the integrality gap is exactly ${k-1+\frac{1}{k}}$ for k-uniform hypergraphs, and is exactly k ? 1 for k-partite hypergraphs. This yields an improved approximation algorithm for the weighted 3-dimensional matching problem. Our algorithm combines the use of the iterative rounding method and the fractional local ratio method, showing a new way to round linear programming solutions for packing problems.

We study the strengthening of the standard LP relaxation by local constraints. We show that, even after linear number of rounds of the Sherali-Adams lift-and-project procedure on the standard LP relaxation, there are k-uniform hypergraphs with integrality gap at least k ? 2. On the other hand, we prove that for every constant k, there is a strengthening of the standard LP relaxation by only a polynomial number of constraints, with integrality gap at most ${\frac{k+1}{2}}$ for k-uniform hypergraphs. The construction uses a result in extremal combinatorics.

We consider the standard semidefinite programming relaxation of the problem. We prove that the Lovász ${\vartheta}$ -function provides an SDP relaxation with integrality gap at most ${\frac{k+1}{2}}$ . The proof gives an indirect way (not by a rounding algorithm) to bound the ratio between any local optimal solution and any optimal SDP solution. This shows a new connection between local search and linear and semidefinite programming relaxations.

     

Branch-and-cut approaches for chance-constrained formulations of reliable network design problems

We study solution approaches for the design of reliably connected networks. Specifically, given a network with arcs that may fail at random, the goal is to select a minimum cost subset of arcs such the probability that a connectivity requirement is satisfied is at least $1 - \epsilon $ , where $\epsilon $ is a risk tolerance. We consider two types of connectivity requirements. We first study the problem of requiring an $s$ - $t$ path to exist with high probability in a directed graph. Then we consider undirected graphs, where we require the graph to be fully connected with high probability. We model each problem as a stochastic integer program with a joint chance constraint, and present two formulations that can be solved by a branch-and-cut algorithm. The first formulation uses binary variables to represent whether or not the connectivity requirement is satisfied in each scenario of arc failures and is based on inequalities derived from graph cuts in individual scenarios. We derive additional valid inequalities for this formulation and study their facet-inducing properties. The second formulation is based on probabilistic graph cuts, an extension of graph cuts to graphs with random arc failures. Inequalities corresponding to probabilistic graph cuts are sufficient to define the set of feasible solutions and violated inequalities in this class can be found efficiently at integer solutions, allowing this formulation to be solved by a branch-and-cut algorithm. Computational results demonstrate that the approaches can effectively solve instances on large graphs with many failure scenarios. In addition, we demonstrate that, by varying the risk tolerance, our model yields a rich set of solutions on the efficient frontier of cost and reliability.     

Singular Solutions of the Generalized Dhombres Functional Equation

We consider singular solutions of the functional equation ${f(xf(x)) = \varphi (f(x))}$ where ${\varphi}$ is a given and f an unknown continuous map ${\mathbb R_{+} \rightarrow \mathbb R_{+}}$ . A solution f is regular if the sets ${R_f \cap (0, 1]}$ and ${R_f \cap [1, \infty)}$ , where R _f is the range of f, are ${\varphi}$ -invariant; otherwise f is singular. We show that for singular solutions the associated dynamical system ${({R_f}, \varphi|_{R_f})}$ can have strange properties unknown for the regular solutions. In particular, we show that ${\varphi |_{R_f}}$ can have a periodic point of period 3 and hence can be chaotic in a strong sense. We also provide an effective method of construction of singular solutions.     

How Far Can Chemotactic Cross-diffusion Enforce Exceeding Carrying Capacities?

We consider nonnegative solutions of the Neumann initial-boundary value problem for the chemotaxis-growth system $$\begin{aligned} \left\{ \begin{array}{l} u_t=\varepsilon u_{xx} -(uv_x)_x +ru -\mu u^2, \qquad x\in \Omega , \ t>0, \\ 0=v_{xx}-v+u, \qquad x\in \Omega , \ t>0, \end{array} \right. \quad (\star ) \end{aligned}$$ in \(\Omega :=(0,L)\subset \mathbb {R}\) with \(L>0, \varepsilon >0, r\ge 0\) and \(\mu >0\) , along with the corresponding limit problem formally obtained upon taking \(\varepsilon \searrow 0\) . For the latter hyperbolic–elliptic problem, we establish results on local existence and uniqueness within an appropriate generalized solution concept. In this context we shall moreover derive an extensibility criterion involving the norm of \(u(\cdot ,t)\) in \(L^\infty (\Omega )\) . This will enable us to conclude that in this case \(\varepsilon =0\) ,

• if \(\mu \ge 1\) , then all solutions emanating from sufficiently regular initial data are global in time, whereas
• if \(\mu <1\) , then some solutions blow-up in finite time.

The latter will reveal that the original parabolic–elliptic problem ( \(\star \) ), though known to possess no such exploding solutions, exhibits the following property of dynamical structure generation: given any \(\mu \in (0,1)\) , one can find smooth bounded initial data with the property that for each prescribed number \(M>0\) the solution of ( \(\star \) ) will attain values above \(M\) at some time, provided that \(\varepsilon \) is sufficiently small. In particular, this means that the associated carrying capacity given by \(\frac{r}{\mu }\) can be exceeded during evolution to an arbitrary extent. We finally present some numerical simulations that illustrate this type of solution behavior and that, moreover, inter alia, indicate that achieving large population densities is a transient dynamical phenomenon occurring on intermediate time scales only.