Abstract In this paper we consider nonconvex diagonal Quadratically Constrained Quadratic Programming (QCQP) problems, where at least one constraint is strictly convex. A lower bound for such problems can be computed through a Lagrangian relaxation, where all constraints, except the strictly convex constraint, are moved into the objective function, suitably weighted by a vector of Lagrange multipliers. The search for the best (largest) Lagrangian bound leads to the definition of the dual Lagrangian problem. The aim of this paper is to provide sufficient as well as necessary and sufficient conditions under which exactness of the dual Lagrangian bound (i.e., the equivalence of its optimal value with the optimal value of the original nonconvex problem) is guaranteed. Some of these conditions are based on the solution of linear feasibility problems defined over the space of the Lagrange multipliers, some others on the solution of convex problems over the same space. We specialize the results proved for general diagonal QCQPs to the special case where the constraints are linear, ball and reverse ball constraints, i.e., the Hessian matrices of the constraint quadratic functions are null matrices (linear constraints), identity matrices (ball constraints), and the opposite of identity matrices (reverse ball constraints). We show that in this special case the conditions can be evaluated much more efficiently. Finally, we perform experiments over random instances to identify relevant factors which affect both exactness of the dual Lagrangian bound and the ability of detecting such exactness through the proposed sufficient conditions.

On an assigned graph, the problem of Multi-Agent Pathfinding (MAPF) consists in finding paths for multiple agents, avoiding collisions. Finding the minimum-length solution is known to be NP-hard, and computation times grows exponentially with the number of agents. However, in industrial applications, it is important to find feasible, suboptimal solutions, in a time that grows polynomially with the number of agents. Such algorithms exist for undirected and biconnected directed graphs. Our main contribution is to generalize these algorithms to the more general case of strongly connected directed graphs. In particular, we describe a procedure that checks the problem feasibility in linear time with respect to the number of vertices n , and we find a necessary and sufficient condition for feasibility of any MAPF instance. Moreover, we present an algorithm (diSC) that provides a feasible solution of length O ( k n 2 c ) , where k is the number of agents and c the maximum length of the corridors of the graph.

The pebble motion on trees (PMT) problem consists in finding a feasible sequence of moves that repositions a set of pebbles to assigned target vertices. This problem has been widely studied because, in many cases, the more general Multi-Agent path finding (MAPF) problem on graphs can be reduced to PMT. We propose a simple and easy to implement procedure, which finds solutions of length O(|P|nc + n2), where n is the number of nodes, P is the set of pebbles, and c the maximum length of corridors in the tree. This complexity result is more detailed than the current best known result O(n3), which is equal to our result in the worst case, but does not capture the dependency on c and |P|.

Abstract Linear least squares is one of the most widely used regression methods in many fields. The simplicity of the model allows this method to be used when data is scarce and allows practitioners to gather some insight into the problem by inspecting the values of the learnt parameters. In this paper we propose a variant of the linear least squares model allowing practitioners to partition the input features into groups of variables that they require to contribute similarly to the final result. We show that the new formulation is not convex and provide two alternative methods to deal with the problem: one non-exact method based on an alternating least squares approach; and one exact method based on a reformulation of the problem. We show the correctness of the exact method and compare the two solutions showing that the exact solution provides better results in a fraction of the time required by the alternating least squares solution (when the number of partitions is small). We also provide a branch and bound algorithm that can be used in place of the exact method when the number of partitions is too large as well as a proof of NP-completeness of the optimization problem.

In a high-speed palletizing machine, packages of various sizes are inserted on a conveyor belt. Then, cooperating multiple robotic manipulators move them to obtain a desired final layout. The throughput of this palletizing process critically hinges upon the strategic selection of the insertion sequence and the careful choice of robot manipulations. Pursuing a higher throughput in this context holds great importance due to its potential to enhance productivity, however, reaching such goal constitutes a challenging task. Indeed, the problem of maximizing the throughput of the palletizing machine is a nontrivial one and, despite its relevant importance in industrial settings, it has not received much attention in existing literature. In this work, we present a Dynamic Programming-based algorithm, together with some reduction techniques, that allows finding the shortest packages sequence and the corresponding robot manipulations that maximize production. We include some numerical experiments on randomly generated problems and on actual industrial scenarios, which show the good performance of the proposed method.Note to Practitioners—This work is motivated by the need of high-speed palletizing machine manufacturers to automate the generation of packages sequences, and the corresponding robot manipulations tasks assignment. We solve this problem with a Dynamic Programming-based algorithm. The benefit of the proposed method is twofold. On one hand, it allows palletizing machines manufacturers not to waste their employees’ time on the often lengthy task of manually planning packages sequences and manipulations. On the other hand, the proposed approach allows minimizing the time required to assemble an assigned layout, increasing the overall throughput of the production chain. The proposed algorithm can be implemented in any programming language of choice (e.g., C$++$) and integrated by manufacturers in their production software. The main limitation of this approach is the computational time which grows exponentially with the number of packages. However, given that the application is an off-line one, this approach allows handling most of the industrial layouts, which usually consist of a few tens of packages, in a reasonable amount of time. As future developments, the approach could be generalized to handle more complicated manipulator movements and/or allow robots to manipulate each package more than once. This would add a layer of complexity that would require nontrivial tailored solution strategies in order to handle these new degrees of freedom.

In this article, we discuss a sequential algorithm for the computation of a minimum-time speed profile over a given path, under velocity, acceleration, and jerk constraints. Such a problem arises in industrial contexts, such as automated warehouses, where LGVs need to perform assigned tasks as fast as possible in order to increase productivity. It can be reformulated as an optimization problem with a convex objective function, linear velocity and acceleration constraints, and nonconvex jerk constraints, which, thus, represent the main source of the difficulty. While existing nonlinear programming (NLP) solvers can be employed for the solution of this problem, it turns out that the performance and robustness of such solvers can be enhanced by the sequential line-search algorithm proposed in this article. At each iteration, a feasible direction, with respect to the current feasible solution, is computed, and a step along such direction is taken in order to compute the next iterate. The computation of the feasible direction is based on the solution of a linearized version of the problem, and the solution of the linearized problem, through an approach that strongly exploits its special structure, represents the main contribution of this work. The efficiency of the proposed approach with respect to existing NLP solvers is proven through different computational experiments. Note to Practitioners—This article was motivated by the needs of LGV manufacturers. In particular, it presents an algorithm for computing the minimum-time speed law for an LGV along a preassigned path, respecting assigned velocity, acceleration, and jerk constraints. The solution algorithm should be: 1) fast, since speed planning is made continuously throughout the workday, not only when an LGV receives a new task but also during the execution of the task itself, since conditions may change, e.g., if the LGV has to be halted for security reasons and 2) reliable, i.e., it should return solutions of high quality, because a better speed profile allows to save time and even small percentage improvements, say a 5% improvement, has a considerable impact on the productivity of the warehouse, and, thus, determines a significant economic gain. The algorithm that we propose meets these two requirements, and we believe that it can be a useful tool for LGV manufacturers and users. It is obvious that the proposed method also applies to the speed planning problem for vehicles other than LGVs, e.g., road vehicles.

In this paper, we consider the speed planning problem for a robotic manipulator. In particular, we present an algorithm for finding the time-optimal speed law along an assigned path that satisfies velocity and acceleration constraints and respects the maximum forces and torques allowed by the actuators. The addressed optimization problem is a finite-dimensional reformulation of the continuous-time speed optimization problem, obtained by discretizing the speed profile with n points. The proposed algorithm has linear complexity with respect to n and to the number of degrees of freedom. Such complexity is the best possible for this problem. Numerical tests show that the proposed algorithm is significantly faster than algorithms already existing in literature.

Consider a multi-tone multi-user communication system with K interfering users and N available tones. An effective approach to mitigate interference is through power control at transmitters. In this paper, we consider optimal power allocation to maximize a system utility function, and show that for the two tone cases (N=2) with min-rate, harmonic mean, and geometric mean utility functions, the corresponding optimal power allocation problem is NP-hard. This result fills an important gap in the existing literature, which settled the complexity status of different cases involving various utility functions and values of N. Our proof is through a reduction from the partitioning problem for the min-rate utility function, and from the independent set problem for the harmonic mean and geometric mean utility functions.

In this paper, we define a discrete dynamical system that governs the evolution of a population of agents. From the dynamical system, a variant of differential evolution (DE) is derived. It is then demonstrated that, under some assumptions on the differential mutation strategy and on the local structure of the objective function, the proposed dynamical system has fixed points toward which it converges with probability one for an infinite number of generations. This property is used to derive an algorithm that performs better than standard DE on some space trajectory optimization problems. The novel algorithm is then extended with a guided restart procedure that further increases the performance, reducing the probability of stagnation in deceptive local minima.

In this paper we propose a generalized formulation of the evolutionary heuristic governing the movement of the individuals of differential evolution in the search space. The basic heuristic of differential evolution is casted in form of discrete dynamical system and extended to improve local convergence. It is demonstrated that under some assumptions on the local structure of the objective function, the proposed dynamical system, has fixed points towards which it converges asymptotically. This property is used to derive an algorithm that performs better than standard differential evolution on some space trajectory optimization problems. The novel algorithm is then extended with a guided restart procedure that further increases the performance reducing the probability of stagnation in deceptive local minima.

We present a new computational approach to the problem of placing n identical nonoverlapping disks in the unit square in such a way that their radii are maximized. The problem has been studied in a large number of papers, from both a theoretical and a computational point of view. In this paper, we conjecture that the problem possesses a so-called funneling landscape, a feature that is commonly found in molecular conformation problems. Based on this conjecture, we develop a stochastic search algorithm that displays excellent numerical performance. Thanks to this algorithm, we could improve over previously known putative optima in the range n ≤ 130 in as many as 32 instances, the smallest of which is n = 53.

The Morse potential is a simple model for the potential energy of atoms with a single parameter ρ that determines the width of the potential well and allows a wide variety of materials to be modeled. Morse clusters are particularly important for applications, but their global optimization is also an extremely hard problem, highly relevant to methods that are to be applied to find the optimal configuration of a biomolecule. In particular, large ρ values are very challenging and, until now, no unbiased global-optimization method has been able to detect all the (putative) global minima at ρ = 14 for clusters with up to N = 80 atoms. In this paper we introduce some techniques for transforming the original Morse potential that allow us to increase considerably the efficiency in locating the known global minima and also to discover some new optimal clusters. These methods are promising candidates for application to the optimization of biomolecules.