Solving multiobjective,multiconstraint knapsack problems using mathematical programming and evolutionary algorithms

In this paper, we solve instances of the multiobjective multiconstraint (or multidimensional) knapsack problem (MOMCKP) from the literature, with three objective functions and three constraints. We use exact as well as approximate algorithms. The exact algorithm is a properly modified version of the multicriteria branch and bound (MCBB) algorithm, which is further customized by suitable heuristics. Three branching heuristics and a more general purpose composite branching and construction heuristic are devised. Comparison is made to the published results from another exact algorithm, the adaptive ε-constraint method [Laumanns, M., Thiele, L., Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for Metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 932–942], using the same data sets. Furthermore, the same problems are solved using standard multiobjective evolutionary algorithms (MOEA), namely, the SPEA2 and the NSGAII. The results from the exact case show that the branching heuristics greatly improve the performance of the MCBB algorithm, which becomes faster than the adaptive ε -constraint. Regarding the performance of the MOEA algorithms in the specific problems, SPEA2 outperforms NSGAII in the degree of approximation of the Pareto front, as measured by the coverage metric (especially for the largest instance).     

A multi-level search strategy for the 0-1 Multidimensional Knapsack Problem

We propose an exact method based on a multi-level search strategy for solving the 0-1 Multidimensional Knapsack Problem. Our search strategy is primarily based on the reduced costs of the non-basic variables of the LP-relaxation solution. Considering that the variables are sorted in decreasing order of their absolute reduced cost value, the top level branches of the search tree are enumerated following Resolution Search strategy, the middle level branches are enumerated following Branch & Bound strategy and the lower level branches are enumerated according to a simple Depth First Search enumeration strategy. Experimentally, this cooperative scheme is able to solve optimally large-scale strongly correlated 0-1 Multidimensional Knapsack Problem instances. The optimal values of all the 10 constraint, 500 variable instances and some of the 30 constraint, 250 variable instances of the OR-Library were found. These values were previously unknown.     

On single processor scheduling problems with learning dependent on the number of processed jobs

The importance of the role that learning plays in manufacturing, industry and computer systems is undeniable as well as the profit that can be increased if this phenomenon is taken into consideration for short- and long-term optimization. In this paper, we focus on scheduling jobs on a single processor, where its effectiveness can increase with the number of processed jobs, to minimize one of the following objectives: the maximum completion time with the release dates, the maximum lateness and the number of late jobs. It is proved that these well known polynomially solvable problems become at least NP-hard with the considered learning models. To solve them we provide some elimination procedures that are used to construct a branch and bound algorithm. Furthermore, we propose some fast heuristics for the problem of minimizing the number of late jobs with the general model of the learning effect.     

An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time

In this article, we present a new exact algorithm for solving the simple assembly line balancing problem given a determined cycle time (SALBP-1). The algorithm is a station-oriented bidirectional branch-and-bound procedure based on a new enumeration strategy that explores the feasible solutions tree in a non-decreasing idle time order. The procedure uses several well-known lower bounds, dominance rules and a new logical test based on the assimilation of the feasibility problem for a given cycle time and number of stations (SALBP-F) to a maximum-flow problem.     

Infinite family of transmission irregular trees of even order

Distance between two vertices is the number of edges in a shortest path connecting them in a connected graph $G$. The transmission of a vertex $v$ is the sum of distances from $v$ to all the other vertices of $G$. If transmissions of all vertices are mutually distinct, then $G$ is a transmission irregular graph. It is known that almost no graphs are transmission irregular. Infinite families of transmission irregular trees of odd order were presented in Alizadeh and Klav?ar (2018). The following problem was posed in Alizadeh and Klav?ar (2018): do there exist infinite families of transmission irregular trees of even order? In this article, such a family is constructed.     

A simple metal free highly diastereoselective synthesis of heteroaryl substituted (±) cyclohexanols by a branched domino reaction

A self diastereoselective, simple metal free and efficient branch domino reaction gave multiple heteroaryl substituted (±) cyclohexanols with five chiral centres in >95% yields. The reactions that occur are Claisen Schmidt condensation followed by Michael addition and Aldol reactions of heteroaryl carbaldehydes and acetyl pyridine derivatives. Mechanistic study of the reactions shows excellent self diastereoselectivity (dr > 99%) in the intermediate steps which results selectively in the formation of one set of enantiomers out of sixteen possible enantiomeric pairs. The self diastereoselectivity of reaction in all the steps dominates due to the steric hindrance induced by the bulky heteroaryl groups. The stereochemistry of the synthesized compounds is established using single crystal XRD.     

A Branch and Contract Algorithm for Problems with Concave Univariate, Bilinear and Linear Fractional Terms

A new deterministic branch and bound algorithm is presented in this paper for the global optimization of continuous problems that involve concave univariate, bilinear and linear fractional terms. The proposed algorithm, the branch and contract algorithm, relies on the use of a bounds-contraction subproblem that aims at reducing the size of the search region by eliminating portions of the domain in which the objective function takes only values above a known upper bound. The solution of contraction subproblems at selected branch and bound nodes is performed within a finite contraction operation that helps reducing the total number of nodes in the branch and bound solution tree. The use of the proposed algorithm is illustrated with several numerical examples.     

指动脉分支在指尖离断再植中的应用

目的探讨指动脉分支在指尖离断再植中应用的方法和疗效.方法 1998年8月～2004年9月,应用指动脉分支移位法,对指尖离断进行再植27例,共32指.结果 32指中成活31指,成活率96.8%.术后随访4～6个月,再植指外形、指尖部感觉恢复优良,效果满意.结论指动脉分支移位法,适用于指尖离断再植.     

The Branch Processes of Chern-Simons (CS) <Emphasis Type="Italic">p</Emphasis>-Branes

In this paper, by making use of Duan’s topological current theory, the branch process of Chern-Simons (CS) p-branes is discussed in detail. Chern-Simons (CS) p-branes are found generating or annihilating at the limit points and encountering, splitting, or merging at the bifurcation points and higher degenerated points systematically of the vector order parameter field . Furthermore, it is also shown that CS p-branes are found splitting or merging at the degenerate point of field function but the total topological charges of the CS p-branes are still unchanged.