Hadamard well-posedness for a set-valued optimization problem

In this paper, we introduce a kind of Hadamard well-posedness for a set-valued optimization problem. By virtue of a scalarization function, we obtain some relationships between weak ${(\varepsilon, e)}$ -minimizers of the set-valued optimization problem and ${\varepsilon}$ -approximate solutions of a scalar optimization problem. Then, we establish a scalarization theorem of P.K. convergence for sequences of set-valued mappings. Based on these results, we also derive a sufficient condition of Hadamard well-posedness for the set-valued optimization problem.     

A branch-and-price algorithm for the two-dimensional level strip packing problem

The two-dimensional level strip packing problem (2LSPP) consists in packing rectangular items of given size into a strip of given width divided into levels. Items packed into the same level cannot be put on top of one another and their overall width cannot exceed the width of the strip. The objective is to accommodate all the items while minimizing the overall height of the strip. The problem is -hard and arises from applications in logistics and transportation. We present a set covering formulation of the 2LSPP suitable for a column generation approach, where each column corresponds to a feasible combination of items inserted into the same level. For the exact optimization of the 2LSPP we present a branch-and-price algorithm, in which the pricing problem is a penalized knapsack problem. Computational results are reported for benchmark instances with some hundreds items.     

A new greedy algorithm for the quadratic assignment problem

The classical greedy algorithm for discrete optimization problems where the optimal solution is a maximal independent subset of a finite ground set of weighted elements, can be defined in two ways which are dual to each other. The Greedy-In where a solution is constructed from the empty set by adding the next best element, one at a time, until we reach infeasibility, and the Greedy-Out where starting from the ground set we delete the next worst element, one at a time, until feasibility is reached. It is known that while the former provides an approximation ratio for maximization problems, its worst case performance is not bounded for minimization problems, and vice-versa for the later. However the Greedy-Out algorithm requires an oracle for checking the existence of a maximal independent subset which for most discrete optimization problems is a difficult task. In this work we present a Greedy-Out algorithm for the quadratic assignment problem by providing a combinatorial characterization of its solutions.     

Exploiting algebraic structure in global optimization and the Belgian chocolate problem

The Belgian chocolate problem involves maximizing a parameter \(\delta \) over a non-convex region of polynomials. In this paper we detail a global optimization method for this problem that outperforms previous such methods by exploiting underlying algebraic structure. Previous work has focused on iterative methods that, due to the complicated non-convex feasible region, may require many iterations or result in non-optimal \(\delta \). By contrast, our method locates the largest known value of \(\delta \) in a non-iterative manner. We do this by using the algebraic structure to go directly to large limiting values, reducing the problem to a simpler combinatorial optimization problem. While these limiting values are not necessarily feasible, we give an explicit algorithm for arbitrarily approximating them by feasible \(\delta \). Using this approach, we find the largest known value of \(\delta \) to date, \(\delta = 0.9808348\). We also demonstrate that in low degree settings, our method recovers previously known upper bounds on \(\delta \) and that prior methods converge towards the \(\delta \) we find.     

A polynomial algorithm for a continuous bilevel knapsack problem

In this note, we analyze a bilevel interdiction problem, where the follower’s program is a parametrized continuous knapsack. Based on the structure of the problem and an inverse optimization strategy, we propose for its solution an algorithm with worst-case complexity $O\left(n^2\right)$.     

An open optimization problem in statistical quality control

We ask the experts in global optimization if there is an efficient solution to an optimization problem in acceptance sampling: Here, one often has incomplete prior information about the quality of incoming lots. Given a cost model, a decision rule for the inspection of a lot may then be designed that minimizes the maximum loss compatible with the available information. The resulting minimax problem is sometimes hard to solve, as the loss functions may have several local maxima which vary in an unpredictable way with the parameters of the decision rule.     

Computing a global optimal solution to a design centering problem

In this paper we present a method for solving a special three-dimensional design centering problem arising in diamond manufacturing: Find inside a given (not necessarily convex) polyhedral rough stone the largest diamond of prescribed shape and orientation. This problem can be formulated as the one of finding a global maximum of a difference of two convex functions over ³ and can be solved efficiently by using a global optimization algorithm provided that the objective function of the maximization problem can be easily evaluated. Here we prove that with the information available on the rough stone and on the reference diamond, evaluating the objective function at a pointx amounts to computing the distance, with respect to a Minkowski gauge, fromx to a finite number of planes. We propose a method for finding these planes and we report some numerical results.     

A problem with free boundary

One considers the Dirichlet problem for the equation u=(u), where is the Heaviside function. Under special assumptions one constructs the solution of this problem with convex and smooth level surfaces and, in particular, with a regular free surface, which coincides with the set of level zero. One proves the solvability in the small of the problem in the neighborhood of the constructed regular solution under perturbations of the boundary condition and a smooth boundary of the domain .Translated from Problemy Matematicheskogo Analiza, No. 10, pp. 72–83, 1986.     

A continuous characterization of the maximum-edge biclique problem

The problem of finding large complete subgraphs in bipartite graphs (that is, bicliques) is a well-known combinatorial optimization problem referred to as the maximum-edge biclique problem (MBP), and has many applications, e.g., in web community discovery, biological data analysis and text mining. In this paper, we present a new continuous characterization for MBP. Given a bipartite graph $G$ , we are able to formulate a continuous optimization problem (namely, an approximate rank-one matrix factorization problem with nonnegativity constraints, R1N for short), and show that there is a one-to-one correspondence between (1) the maximum (i.e., the largest) bicliques of $G$ and the global minima of R1N, and (2) the maximal bicliques of $G$ (i.e., bicliques not contained in any larger biclique) and the local minima of R1N. We also show that any stationary points of R1N must be close to a biclique of $G$ . This allows us to design a new type of biclique finding algorithm based on the application of a block-coordinate descent scheme to R1N. We show that this algorithm, whose algorithmic complexity per iteration is proportional to the number of edges in the graph, is guaranteed to converge to a biclique and that it performs competitively with existing methods on random graphs and text mining datasets. Finally, we show how R1N is closely related to the Motzkin–Strauss formalism for cliques.     

The cluster problem in constrained global optimization

Deterministic branch-and-bound algorithms for continuous global optimization often visit a large number of boxes in the neighborhood of a global minimizer, resulting in the so-called cluster problem (Du and Kearfott in J Glob Optim 5(3):253–265, 1994). This article extends previous analyses of the cluster problem in unconstrained global optimization (Du and Kearfott 1994; Wechsung et al. in J Glob Optim 58(3):429–438, 2014) to the constrained setting based on a recently-developed notion of convergence order for convex relaxation-based lower bounding schemes. It is shown that clustering can occur both on nearly-optimal and nearly-feasible regions in the vicinity of a global minimizer. In contrast to the case of unconstrained optimization, where at least second-order convergent schemes of relaxations are required to mitigate the cluster problem when the minimizer sits at a point of differentiability of the objective function, it is shown that first-order convergent lower bounding schemes for constrained problems may mitigate the cluster problem under certain conditions. Additionally, conditions under which second-order convergent lower bounding schemes are sufficient to mitigate the cluster problem around a global minimizer are developed. Conditions on the convergence order prefactor that are sufficient to altogether eliminate the cluster problem are also provided. This analysis reduces to previous analyses of the cluster problem for unconstrained optimization under suitable assumptions.     

An optimization problem with volume constraint for a degenerate quasilinear operator

We consider the optimization problem of minimizing with a constraint on the volume of {u>0}. We consider a penalization problem, and we prove that for small values of the penalization parameter, the constrained volume is attained. In this way we prove that every solution u is locally Lipschitz continuous and that the free boundary, ∂{u>0}∩Ω, is smooth.     

The dynamic programming method in the generalized traveling salesman problem

A procedure of the dynamic programming (DP) for the discrete-continuous problem of a route optimization is considered. It is possible to consider this procedure as a dynamic method of optimization of the towns choice in the well-known traveling salesman problem. In the considered version of DP, elements of a dynamic optimization are used. Two variants of the function of the aggregations of losses are investigated:

• 1.(1) the additive functions;
• 2.(2) the function characterizing the aggregation of losses in the bottle-neck problem.

     

Monotonic optimization for sensor cover energy problem

We study the sensor cover energy problem (SCEP) in wireless communication—a difficult nonconvex problem with nonconvex constraints. A local approach based on DC programming called DCA was proposed by Astorino and Miglionico (Optim Lett 10(2):355–368, 2016) for solving this problem. In the present paper, we propose a global approach to (SCEP) based on the theory of monotonic optimization. By using an appropriate reformulation of (SCEP) we propose an algorithm for finding quickly a local optimal solution along with an efficient algorithm for computing a global optimal solution. Computational experiments are reported which demonstrate the practicability of the approach.     

The interactive fixed charge inhomogeneous flows optimization problem

An optimization problem of interactive inhomogenous flows (Steiner multicommodity network flow problem) is formulated. The problem's main characteristic is a fixed charge change when combining multicommodity communications. In this paper we propose a method for solving this problem which, in order to restrict the search on the feasible domain, reduces the original problem to a concave programming problem in the form: min {f(x)|xX} wheref:ⁿ is a concave function, andX ₀ ⁿ is a flow polytope defined by network transportation constraints. For practical large-scale problems arising from planning transportation networks on inhomogeneous surfaces defined by a digital model, a method of local optimization over a flow polytope vertex set is proposed, which is far more effective in comparison with the Gallo and Sodini method under polytope strong degeneracy conditions.     

Local minima of the trust region problem

We consider the minimization of a quadratic formzVz+2zq subject to the two-norm constraint z=. The problem received considerable attention in the literature, notably due to its applications to a class of trust region methods in nonlinear optimization. While the previous studies were concerned with just the global minimum of the problem, we investigate the existence of all local minima. The problem is approached via the dual Lagrangian, and the necessary and sufficient conditions for the existence of all local minima are derived. We also examine the suitability of the conventional numerical techniques used to solve the problem to a class of single-instruction multiple-data computers known as processor arrays (in our case, AMT DAP 610). Simultaneously, we introduce certain hardware-oriented multisection algorithms, showing their efficiency in the case of small to medium size problems.This research was partially supported by the National Physical Laboratories of England under Contract RTP2/155/127.     

On positive solutions for fourth-order boundary value problem with impulse

In this paper, we consider a fourth-order boundary value problem with impulse. First, we establish criteria for the existence of one or more than one positive solution of a non-eigenvalue problem. Second, we are concerned with determining values of λ$\lambda$, for which there exist positive solutions for an eigenvalue problem. In both problems, we shall use the Krasnoselskii fixed point theorem.     

An improved semidefinite programming relaxation for the satisfiability problem

The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that the formula is satisfied. It is well known that SAT is in general NP-complete, although several important special cases can be solved in polynomial time. Semidefinite programming (SDP) refers to the class of optimization problems where a linear function of a matrix variable X is maximized (or minimized) subject to linear constraints on the elements of X and the additional constraint that X be positive semidefinite. We are interested in the application of SDP to satisfiability problems, and in particular in how SDP can be used to detect unsatisfiability. In this paper we introduce a new SDP relaxation for the satisfiability problem. This SDP relaxation arises from the recently introduced paradigm of higher liftings for constructing semidefinite programming relaxations of discrete optimization problems. To derive the SDP relaxation, we first formulate SAT as an optimization problem involving matrices. Relaxing this formulation yields an SDP which significantly improves on the previous relaxations in the literature. The important characteristics of the SDP relaxation are its ability to prove that a given SAT formula is unsatisfiable independently of the lengths of the clauses in the formula, its potential to yield truth assignments satisfying the SAT instance if a feasible matrix of sufficiently low rank is computed, and the fact that it is more amenable to practical computation than previous SDPs arising from higher liftings. We present theoretical and computational results that support these claims.Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

A combined local search and integer programming approach to the traveling tournament problem

The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances.