Search

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

When the meta-heuristic algorithm solves the joint resource allocation problem of multi-beam satellites, the computational complexity increases and the algorithm is difficult to converge due to the time delay constraint and capacity constraint. This paper introduced a penalty mechanism in the objective function, and added a penalty value to the objective function of the invalid solution, so that the optimized solution adaptively satisfied these two constraints. Based on this, this paper proposed a joint resource allocation algorithm based on quantum-behaved particle swarm optimization. Simulation results show that the introduction of the penalty strategy solves the problem of difficulty in handling the delay constraint and capacity constraint when applying the meta-heuristic algorithm. The quantum-behaved particle swarm optimization algorithm with penalty mechanism outperforms the existing joint allocation algorithm in terms of allocation fairness index and total system capacity. [ABSTRACT FROM AUTHOR]

Recently, numerous meta-heuristic-based approaches are deliberated to reduce the computational complexities of several existing approaches that include tricky derivations, very large memory space requirement, initial value sensitivity, etc. However, several optimization algorithms namely firefly algorithm, sine–cosine algorithm, and particle swarm optimization algorithm have few drawbacks such as computational complexity and convergence speed. So to overcome such shortcomings, this paper aims in developing a novel chaotic sine–cosine firefly (CSCF) algorithm with numerous variants to solve optimization problems. Here, the chaotic form of two algorithms namely the sine–cosine algorithm and the firefly algorithms is integrated to improve the convergence speed and efficiency thus minimizing several complexity issues. Moreover, the proposed CSCF approach is operated under various chaotic phases and the optimal chaotic variants containing the best chaotic mapping are selected. Then numerous chaotic benchmark functions are utilized to examine the system performance of the CSCF algorithm. Finally, the simulation results for the problems based on engineering design are demonstrated to prove the efficiency, robustness and effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch-and-cut solvers for mixed-integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a closed-form expression. In this paper, we use the lift-and-project framework introduced by Balas and Perregaard to provide the basis, and the reduce-and-split algorithm as described by Cornuéjols and Nannicini to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory mixed-integer cut and alternates between lift-and-project and reduce-and-split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable to split disjunctions on multiple variables. Second, we apply the reduce-and-split algorithm to nonoptimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods. [ABSTRACT FROM AUTHOR]

In this paper, the berth allocation problem with stochastic vessel handling times is formulated as a bi-objective problem. To solve the resulting problem, an evolutionary algorithm-based heuristic and a simulation-based Pareto front pruning algorithm is proposed. Computational examples show that the proposed approach provides solutions superior to the ones where the expected value of the vessel handling times is used. [ABSTRACT FROM AUTHOR]

This paper describes a generic branch-and-cut algorithm applicable to the solution of multiobjective optimization problems for which a lower bound can be defined as a polynomially solvable multiobjective problem. The algorithm closely follows standard branch and cut except for the definition of the lower and upper bounds and some optional speed-up mechanisms. It is applied to a routing problem called the multilabel traveling salesman problem, a variant of the traveling salesman problem in which labels are attributed to the edges. The goal is to find a Hamiltonian cycle that minimizes the tour length and the number of labels in the tour. Implementations of the generic multiobjective branch-and-cut algorithm and speed-up mechanisms are described. Computational experiments are conducted, and the method is compared to the classical ∈-constraint method. [ABSTRACT FROM AUTHOR]

This paper proposes an improved subspace-based optimization method (SOM) by using a new construction method for the ambiguous part of the induced current. The new current construction method reduces not only the computational complexity of the current construction in every iteration of the optimization but also the computational complexity of the singular-value decomposition of the mapping from the induced current to scattered fields. Thus, the improved SOM is able to deal with the 3-D inverse-scattering problems. Numerical tests validate the algorithm. [ABSTRACT FROM AUTHOR]

In the last two decades, a number of algorithms for the linear single-commodity min-cost flow (MCF) problem have been proposed, and several efficient codes are available that implement different variants of the algorithms. The practical significance of the algorithms has been tested by comparing the time required by their implementations for solving "from-scratch" instances of MCF, of different classes, as the size of the problem (number of nodes and arcs) increases. However, in many applications several closely related instances of MCF have to be sequentially solved, so that reoptimization techniques can be used to speed up computations, and the most attractive algorithm is the one that minimizes the total time required to solve all the instances in the sequence. In this paper we compare the performances of four different efficient implementations of algorithms for MCF under cost reoptimization in the context of decomposition algorithms for the multicommodity min-cost flow (MMCF) problem, showing that for some classes of instances the relative performances of the codes doing "from-scratch" optimization do not accurately predict the relative performances when reoptimization is used. Because the best solver depends both on the class and on the size of the instance, this work also shows the usefulness of a standard interface for MCF problem solvers that we have proposed and implemented. [ABSTRACT FROM AUTHOR]