Search

The Cell Formation Problem (CFP) is an important optimisation problem in manufacturing. It has been introduced in the Group Technology (GT) and its goal is to group machines and parts processed on them into production cells minimising the movement of parts to other cells for processing and maximising for each cell the loading of its machines with operations on its parts. We consider one of the computationally hardest formulations of this problem - the CFP with a variable number of cells and the grouping efficacy objective, which is a fractional function. The CFP literature contains many heuristic algorithms, but only a small number of exact approaches especially for this formulation. In the current paper, we present an exact branch-and-bound algorithm for the same hard CFP formulation. To linearise the fractional objective function, we apply the Dinkelbach approach. We have been able to solve 24 of the 35 instances from the well known GT benchmark. For the remaining 11 instances, the difference in the grouping efficacy with the best known solutions is less than 2.6%. [ABSTRACT FROM AUTHOR]

This paper deals with the multi-degree cyclic single-hoist scheduling problem with time window constraints, in which multiple identical parts enter and leave the system during each cycle. We propose an analytical mathematical model and a branch-and-bound algorithm so as to find a cyclic sequence of hoist moves that maximises the throughput. The branch-and-bound algorithm implicitly enumerates the sequence of hoist moves and requires the solution of a specific set of linear programming problems (LPPs). Computational results on benchmark instances and randomly generated test instances are presented. [ABSTRACT FROM AUTHOR]

The two-dimensional cutting problem requires maximising the sum of the profits of small rectangular pieces, each of which has its own profit and size, obtained from a large rectangular plate. In this paper, a best-first branch-and-bound algorithm is proposed for the unconstrained problem, which has no limit on the number of pieces cut. Each small piece can have its own profit or can use the area of the piece instead of the profit. The proposed algorithm extends the concept of dominated patterns to remove the dominated patterns efficiently. Our proposed algorithm can also remove duplicate patterns and reduce the search space. The existing upper bound is revised and a new bounding strategy that can prune several nodes simultaneously is proposed. Additionally, new data structures are introduced to improve the performance of the algorithm. Computational results using the proposed algorithm on some benchmark examples were compared to the performance of previous algorithms to show the efficiency of the new algorithm. The proposed algorithm reduced the average computational time by up to 93% for 48 sample problems, excluding those problems that required almost no time using existing algorithms. Additionally, a large-scale problem that could not be solved in a reasonable time by the existing exact algorithms was solved successfully using the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this study we consider the operational fixed job scheduling problem under working time limitations. The problem has several practical implications in both production and service operations; however the relevant research is scarce. We analyse pre-emptive and non pre-emptive versions of the problem and its special cases. We provide polynomial-time algorithms for some special cases. We show that the non pre-emptive jobs problem is strongly NP-hard, and propose a branch-and-bound algorithm that employs efficient bounding procedures and dominance properties. We conduct a numerical experiment to observe the effects of parameters on the quality of the solution. The results of our computational tests for the branch-and-bound algorithm reveal that our algorithm can solve the instances with up to 100 jobs in reasonable times. To the best of our knowledge our branch-and-bound algorithm is the first optimisation attempt to solve the problem. [ABSTRACT FROM AUTHOR]

This paper presents a new branch and bound procedure for scheduling a flow-line manufacturing cell. This procedure and an existing procedure are tested on several problem sets with varying numbers of families, jobs and machines, and varying setup time distributions. The results show that the new procedure solves small problems dramatically faster than the existing procedure. Three heuristic procedures, based on the new branch and bound procedure, are developed. These heuristic procedures as well as a tabu search procedure are tested on problem sets with larger problem sizes. The results show that one of the new procedures generates solutions with improved makespans compared to the tabu search procedure. [ABSTRACT FROM AUTHOR]

In this paper, we address an interesting variant of the vehicle routing problem with time windows (VRPTW) faced by the China National Petroleum Corporation (CNPC). The CNPC owns a limited number of tanker trucks for delivering the petroleum to oil stations within specific time windows in the regular seasons. However, during the peak seasons, some requests need to be outsourced to external third-party logistics companies. These companies provide several bids, each of which includes the oil stations to be served and the corresponding charges. The CNPC needs to select some bids and design routes for the self-owned trucks, so that all requests are satisfied and the total cost is minimized. To study this problem, we formulate it into an arc-flow model and a set-partitioning model, and propose six families of valid inequalities to strengthen the set-partitioning model. Based on the set-partitioning model, we propose a branch-and-price-and-cut algorithm and a branch-and-bound algorithm to solve the problem exactly. The proposed algorithms are tested on instances generated according to the well-known Solomon's benchmark instances for the VRPTW and read-world data of the CNPC. The computational experiments demonstrate the effectiveness of the proposed algorithms. The online appendix is available at https://doi.org/10.1287/trsc.2018.0835. [ABSTRACT FROM AUTHOR]

Given a graph whose arc traversal times vary over time, the Time‐Dependent Travelling Salesman Problem consists of finding a Hamiltonian tour of least total duration. In this paper we exploit some properties of the problem and develop a branch‐and‐bound algorithm which outperforms the state‐of‐the‐art branch‐and‐cut procedure by Cordeau et al. [5]. [ABSTRACT FROM AUTHOR]

The performance of branch-and-bound algorithms for deterministic global optimization is strongly dependent on the ability to construct tight and rapidly convergent schemes of lower bounds. One metric of the efficiency of a branch-and-bound algorithm is the convergence order of its bounding scheme. This article develops a notion of convergence order for lower bounding schemes for constrained problems, and defines the convergence order of convex relaxation-based and Lagrangian dual-based lower bounding schemes. It is shown that full-space convex relaxation-based lower bounding schemes can achieve first-order convergence under mild assumptions. Furthermore, such schemes can achieve second-order convergence at KKT points, at Slater points, and at infeasible points when second-order pointwise convergent schemes of relaxations are used. Lagrangian dual-based full-space lower bounding schemes are shown to have at least as high a convergence order as convex relaxation-based full-space lower bounding schemes. Additionally, it is shown that Lagrangian dual-based full-space lower bounding schemes achieve first-order convergence even when the dual problem is not solved to optimality. The convergence order of some widely-applicable reduced-space lower bounding schemes is also analyzed, and it is shown that such schemes can achieve first-order convergence under suitable assumptions. Furthermore, such schemes can achieve second-order convergence at KKT points, at unconstrained points in the reduced-space, and at infeasible points under suitable assumptions when the problem exhibits a specific separable structure. The importance of constraint propagation techniques in boosting the convergence order of reduced-space lower bounding schemes (and helping mitigate clustering in the process) for problems which do not possess such a structure is demonstrated. [ABSTRACT FROM AUTHOR]

We present a branch-and-bound (B&B) framework for the asymmetric prizecollecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prizecollecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS), and node-weighted Steiner tree problem (NWSTP). The main component of our framework is a new dual ascent algorithm for the rooted APCSTP, which generalizes Wong's dual ascent algorithm for the Steiner arborescence problem. The lower bounds and dual information obtained from the algorithm are exploited within powerful boundbased reduction tests and for guiding primal heuristics. The framework is complemented by additional alternative-based reduction tests. Extensive computational results on benchmark instances for the PCSTP,MWCS, andNWSTP indicate the framework's effectiveness, as most instances from literature are solved to optimality within seconds, including most of the (previously unsolved) largest instances from the recent DIMACS Challenge on Steiner trees. Moreover, results on newasymmetric instances for the APCSTP are reported. Since the addressed network design problems are frequently used for modeling various real-world applications (e.g., in bioinformatics), the implementation of the presented B&B framework has been made publicly available. [ABSTRACT FROM AUTHOR]

Combinatorial branch and bound searches are a common technique for solving global optimisation and decision problems. Their performance often depends on good search order heuristics, refined over decades of algorithms research. Parallel search necessarily deviates from the sequential search order, sometimes dramatically and unpredictably, e.g. by distributing work at random. This can disrupt effective search order heuristics and lead to unexpected and highly variable parallel performance. The variability makes it hard to reason about the parallel performance of combinatorial searches. This paper presents a generic parallel branch and bound skeleton, implemented in Haskell, with replicable parallel performance. The skeleton aims to preserve the search order heuristic by distributing work in an ordered fashion, closely following the sequential search order. We demonstrate the generality of the approach by applying the skeleton to 40 instances of three combinatorial problems: Maximum Clique, 0/1 Knapsack and Travelling Salesperson. The overheads of our Haskell skeleton are reasonable: giving slowdown factors of between 1.9 and 6.2 compared with a class-leading, dedicated, and highly optimised C++ Maximum Clique solver. We demonstrate scaling up to 200 cores of a Beowulf cluster, achieving speedups of 100x for several Maximum Clique instances. We demonstrate low variance of parallel performance across all instances of the three combinatorial problems and at all scales up to 200 cores, with median Relative Standard Deviation (RSD) below 2%. Parallel solvers that do not follow the sequential search order exhibit far higher variance, with median RSD exceeding 85% for Knapsack. [ABSTRACT FROM AUTHOR]

We consider the problem of finding a degree‐based γ‐quasi‐clique of maximum cardinality in a given graph for some fixed γ ∈ ( 0 , 1 ]. A degree‐based γ‐quasi‐clique (often referred to as simply a quasi‐clique) is a subgraph, where the degree of each vertex is at least γ times the maximum possible degree of a vertex in the subgraph. A degree‐based γ‐quasi‐clique is a relative clique relaxation model, where the case of γ = 1 corresponds to the well‐known concept of a clique. In this article, we first prove that the problem is N P‐hard for any fixed γ ∈ ( 0 , 1 ], which addresses one of the open questions in the literature. More importantly, we also develop new exact solution methods for solving the problem and demonstrate their advantages and limitations in extensive computational experiments with both random and real‐world networks. Finally, we outline promising directions of future research including possible functional generalizations of the considered clique relaxation model. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(2), 136–152 2018 [ABSTRACT FROM AUTHOR]

Branch and Bound (B&B) algorithms are known to exhibit an irregularity of the search tree. Therefore, developing a parallel approach for this kind of algorithms is a challenge. The efficiency of a B&B algorithm depends on the chosen Branching, Bounding, Selection, Rejection, and Termination rules. The question we investigate is how the chosen platform consisting of programming language, used libraries, or skeletons influences programming effort and algorithm performance. Selection rule and data management structures are usually hidden to programmers for frameworks with a high level of abstraction, as well as the load balancing strategy, when the algorithm is run in parallel. We investigate the question by implementing a multidimensional Global Optimization B&B algorithm with the help of three frameworks with a different level of abstraction (from more to less): Bobpp, Threading Building Blocks (TBB), and a customized Pthread implementation. The following has been found. The Bobpp implementation is easy to code, but exhibits the poorest scalability. On the contrast, the TBB and Pthread implementations scale almost linearly on the used platform. The TBB approach shows a slightly better productivity. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We propose a new branch-and-bound framework for global optimization of disjunctive programs with general logical expressions. We do not assume the logical expressions to be in any normal form, and, under slightly stronger assumptions, we allow the use of negations and implications. In contrast to the widely used reformulation as a mixed-integer program, we compute the lower bounds and evaluate the logical expression in one step. Thus, we reduce the size of the problem and work exclusively with continuous variables, which is computationally advantageous. We present preliminary numerical results as proof of concept. [ABSTRACT FROM AUTHOR]

We describe a project of an exact parallel algorithm for traveling salesman problems (TSPs) of large sizes. It is based on the algorithm developed by E. Balas and N. Christofides almost 40 years ago. Balas’ and Christofides’ algorithm uses branch-and-bound, Hungarian algorithm for assignment problem, and several heuristics to effectively eliminate unnecessary branches of the solution tree. We propose several modifications (including parallelization) of the simplified version of their algorithm which should improve its performance. The modified algorithm was implemented in C++ with OpenMP and tested on graphs with around 1000 nodes. Computational results indicate a possibility of getting exact solutions of TSPs with 10000 nodes in minutes. New heuristic algorithms could be derived from the exact algorithm to solve even bigger problems. Such algorithms could be applied to genome assembly. [ABSTRACT FROM AUTHOR]

Effectively parallelizing of branch-and-bound (BnB) solvers for mathematical programming problems with discrete variables in distributed computing environment is an important issue. Recently Everest web-based environment has been equipped with a generic message service. This improvement enables BnB-solvers to run in parallel and to exchange incumbents values. Thus Everest environment got generic application that parallelizes BnB-solvers (SCIP and COIN-OR CBC) in a rather simple way. Initially, the application was based on preliminary decomposition of feasible domain, e.g. by fixing values of some integer variables. In the current article further improvement of this Everest application is presented. It supports so called “concurrent parallelization” when all BnB-solvers work with the same optimization problem but with different settings defining search path in BnB-tree. Thus, running solvers have more chance to find incumbents, to exchange their values and to reduce BnB search. Preliminary testing of improved BnB-service on Traveling Salesman Problem shows noticeable speedup. [ABSTRACT FROM AUTHOR]

Branch-and-bound (B&B) approaches are widely investigated in resource constrained scheduling (RCS). However, due to the lack of approaches that can generate a tight schedule at the beginning of the search, B&B approaches usually start with a large initial search space, which makes the following search of an optimal schedule time-consuming. To address this problem, this paper proposes a parallel two-phase B&B approach that can drastically reduce the overall RCS time. This paper makes three major contributions: i) it proposes three partial-search heuristics that can quickly find a tight schedule to compact the initial search space; ii) it presents a two-phase search framework that supports the efficient parallel search of an optimal schedule; iii) it investigates various bound sharing and speculation techniques among collaborative tasks to further improve the parallel search performance at different search phases. The experimental results based on well-established benchmarks demonstrate the efficacy of our proposed approach. [ABSTRACT FROM AUTHOR]

This paper examines the coarse-grained approach to parallelization of the branch-and-bound (B&B) algorithm in a distributed computing environment. This approach is based on preliminary decomposition of a feasible domain of mixed-integer programming problem into a set of subproblems. The produced subproblems are solved in parallel by a distributed pool of standalone B&B solvers. The incumbent values found by individual solvers are intercepted and propagated to other solvers to speed up the traversal of B&B search tree. Presented implementation of the approach is based on SCIP, a non-commercial MINLP solver, and Everest, a web-based distributed computing platform. The implementation was tested on several mixed-integer programming problems and a noticeable speedup has been achieved. In the paper, results of a number of experiments with the Traveling Salesman Problem are presented. [ABSTRACT FROM AUTHOR]

To globally solve linear multiplicative programming problem (LMP), this paper presents a practicable branch-and-bound method based on the framework of branch-and-bound algorithm. In this method, a new linear relaxation technique is proposed firstly. Then, the branch-and-bound algorithm is developed for solving problem LMP. The proposed algorithm is proven that it is convergent to the global minimum by means of the subsequent solutions of a series of linear programming problems. Some experiments are reported to show the feasibility and efficiency of this algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a branch-and-bound algorithm for finding a global optimal solution for a nonconvex quadratic program with convex quadratic constraints (NQPCQC). We first reformulate NQPCQC by adding some nonconvex quadratic constraints induced by eigenvectors of negative eigenvalues associated with the nonconvex quadratic objective function to Shor's semidefinite relaxation. Under the assumption of having a bounded feasible domain, these nonconvex quadratic constraints can be further relaxed into linear ones to form a special semidefinite programming relaxation. Then an efficient branch-and-bound algorithm branching along the eigendirections of negative eigenvalues is designed. The theoretic convergence property and the worst-case complexity of the proposed algorithm are proved. Numerical experiments are conducted on several types of quadratic programs to show the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

We study a variant of an abstract scheduling problem inspired by the management of reclaimers in the stockyard of a coal export terminal. We prove NP-completeness of the problem and formulate it as a mixed-integer program. We show that for a given reclaiming sequence, the problem can be solved in pseudo-polynomial time. In addition, we provide simple, constant-factor approximation algorithms as well as exact branch-and-bound algorithms. An extensive computational study analyzes the performance of the algorithms. [ABSTRACT FROM AUTHOR]

In this paper, the focus is put on multi-core branch-and-bound algorithms for solving large-scale permutation-based optimization problems. We investigate five work stealing (WS) strategies with a new data structure called integer-vector-matrix (IVM). In these strategies, each thread has a private IVM allowing the local management of a set of subproblems enumerated using a factorial system. The WS strategies differ in the way the victim thread is selected and the granularity of stolen work units (intervals of factoradics). To assess the efficiency of the private IVM-based WS approach, the five WS strategies have been extensively experimented on the flowshop scheduling permutation problem and compared with their conventional linked-list-based counterparts. The obtained results demonstrate that the IVM-based WS outperforms the linked-list-based one in terms of CPU time, memory usage and number of performed WS operations. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper describes a new initial vertexordering procedure NEW_SORT designed to enhance approximate-colour exact algorithms for the maximum clique problem (MCP). NEW_SORT considers two different vertex orderings: degree and colour-based. The degree-based vertex ordering describes an improvement over a well-known vertex ordering used by exact solvers. Moreover, colour-based vertex orderings for the MCP have been traditionally considered suboptimal with respect to degree-based ones. NEW_SORT chooses the 'best' of the two orderings according to a new evaluation function. The reported experiments on graphs taken from public datasets show that a leading exact solver using NEW_SORT -and further enhanced with a strong initial solution- can improve its performance very significantly (sometimes even exponentially). [ABSTRACT FROM AUTHOR]

Branch-and-bound approaches are promising in pruning fruitless search space during the resource constrained scheduling. However, such approaches only compare the estimated upper and lower bounds of an incomplete schedule to the length of the best feasible schedule at that iteration, which does not fully exploit the potential of the pruning during the search. Aiming to improve the performance of resource constrained scheduling, this paper proposes a parallel structure-aware pruning approach that can traverse the search space significantly faster than state-of-the-art branch-and-bound techniques. This paper makes three major contributions: i) it proposes an efficient pruning technique using the structural scheduling information of the obtained best feasible schedules; ii) it investigates how to perform parallel search to enable efficient multi-directional search and generation of effective fences by tuning the operation enumeration order; and iii) it presents a framework that supports the sharing of minimum upper-bound and fence information among different search tasks to enable efficient parallel structure-aware pruning. The experimental results demonstrate that our parallel pruning approach can drastically reduce the overall resource constrained scheduling time under a wide variety of resource constraints. [ABSTRACT FROM PUBLISHER]

In this paper, a new variable partitioning strategy in Benders decomposition method is applied that enables us to deal with a wide class of mixed-integer nonlinear programming problems including fixed-charge multicommodity network design (FMND) problems under congestion effects. It is proved that the proposed technique for an FMND problem leads to a simple branch-and-bound algorithm such that each node of the branching tree includes a single conic quadratic representable problem consisting of only continuous (flow) variables. Preliminary numerical results are reported. [ABSTRACT FROM AUTHOR]

This paper deals with the no-wait job shop scheduling problem resolution. The problem is to find a schedule to minimize the makespan ( $$C_{max}$$ ), that is, the total completeness time of all jobs. The no-wait constraint occurs when two consecutive operations in a job must be processed without any waiting time either on or between machines. For this, we have proposed two different resolution methods, the first is an exact method based on the branch-and-bound algorithm, in which we have defined a new technique of branching. The second is a particular swarm optimization (PSO) algorithm, extended from the discrete version of PSO. In the proposed algorithm, we have defined the particle and the velocity structures, and an efficient approach is developed to move a particle to the new position. Moreover, we have adapted the timetabling procedure to find a good solution while respecting the no-wait constraint. Using the PSO method, we have reached good results compared to those in the literature. [ABSTRACT FROM AUTHOR]

Nowadays water distribution operation systems are accomplished with the aid of qualified professionals who use their experience in order to achieve a satisfactory performance of the several hydromechanical devices, which are part of the system, such as boosters and valves. In general, these operational rules are empirical and the main goal is to assure the availability of water for the population, with no special concerns about saving energy used in pumping systems. Besides, these empirical rules often disregard hours of lower energy rates. There are several research works concerning the developments of operational rules optimization applied to specific water distribution systems. However, in this work, a general optimization routine integrated with EPANET is presented, which allows the determination of strategic optimal rules of operation for any type of water distribution system. Moreover, a Branch-and-Bound algorithm is also used, where finding the global optimal solution is guaranteed, in admissible computational times. The water distribution system used in this work corresponds to a hypothetical network proposed in the specialized literature. [ABSTRACT FROM AUTHOR]

Two-mode partitioning applications are increasingly common in the physical and social sciences with a variety of models and methods spanning these applications. Two-mode KL-means partitioning (TMKLMP) is one type of two-mode partitioning model with a conceptual appeal that stems largely from the fact that it is a generalization of the ubiquitous (one-mode) K-means clustering problem. A number of heuristic methods have been proposed for TMKLMP, ranging from a two-mode version of the K-means heuristic to metaheuristic approaches based on simulated annealing, genetic algorithms, variable neighborhood search, fuzzy steps, and tabu search. We present an exact algorithm for TMKLMP based on branch-and-bound programming and demonstrate its utility for the clustering of brand switching, manufacturing cell formation, and journal citation data. Although the proposed branchand-bound algorithm does not obviate the need for approximation methods for large two-mode data sets, it does provide a first step in the development of methods that afford a guarantee of globally-optimal solutions for TMKLMP. [ABSTRACT FROM AUTHOR]

Knowledge about tautomer forms of a structure is important since, e.g., a property prediction for a molecule can yield to different results which depend on the individual tautomer. Tautomers are isomers that can be transformed to each other through chemical equilibrium reactions. In this paper the first exact Branch-and-Bound (B&B) algorithm to calculate tautomer structures is proposed. The algorithm is complete in the sense of tautomerism and generates all possible tautomers of a structure according to the tautomer definition, it is initialized with. To be efficient, the algorithm takes advantage of symmetric and formation properties. Some restrictions are used to enable an early pruning of some branches of the B&B tree. This is important, since a simple enumeration strategy would lead to number of candidate tautomers that is exponentially increasing with the number of hydrogen atoms and their attachment sites. The proposed implementation of the B&B algorithm covers the majority of the prototropic tautomer cases, but can be adapted to other kinds of tautomerism too. Furthermore, a computer processable definition of tautomerism is given in the form of the moving hydrogen atom problem. [ABSTRACT FROM AUTHOR]

Solving convex quadratic integer minimization problems by a branch-and-bound algorithm requires tight lower bounds on the optimal objective value. To obtain such dual bounds, we follow the approach of [C. Buchheim, A. Caprara, and A. Lodi, Math. Program., 135 (2012), pp. 369-395] and underestimate the objective function by another convex quadratic function that can be minimized over the integers by simply rounding its continuous minimizer. In geometric terms, we approximate the sublevel sets of the original objective function by auxiliary ellipsoids having the strong rounding property, introduced by [R. Hübner and A. Schöbel, European J. Oper. Res., 237 (2014), pp. 404-410]. We first consider axisparallel ellipsoids (corresponding to separable convex quadratic functions) and show how to efficiently compute an axisparallel ellipsoid yielding the tightest lower bound, both in the situation where the location of the continuous minimizer is given and in the situation where it varies, as it happens in a branch-and-bound approach. In the latter case, we compute both worst-case and average-case optimal ellipsoids. Moreover, we consider the class of quasi-round ellipsoids (from Hübner and Schöbel). In this case, we do not know whether optimal auxiliary ellipsoids can be computed efficiently. However, we present a heuristic for computing an appropriate quasi-round ellipsoid that still yields valid dual bounds; it turns out that using this approach within a branch-and-bound scheme outperforms the approaches based on axisparallel ellipsoid in terms of running times. We finally combine both approaches by introducing the concept of quasi-axisparallel ellipsoids and present a corresponding extension of the heuristic bound computation. [ABSTRACT FROM AUTHOR]

The problem of finding structures with minimum stabbing number has received considerable attention from researchers. Particularly, [10] study the minimum stabbing number of perfect matchings (mspm), spanning trees (msst) and triangulations (mstr) associated to set of points in the plane. The complexity of the mstr remains open whilst the other two are known to be 퓝퓟-hard. This paper presents integer programming (ip) formulations for these three problems, that allowed us to solve them to optimality through ip branch-and-bound (b&b) or branch-and-cut (b&c) algorithms. Moreover, these models are the basis for the development of Lagrangian heuristics. Computational tests were conducted with instances taken from the literature where the performance of the Lagrangian heuristics were compared with that of the exact b&b and b&c algorithms. The results reveal that the Lagrangian heuristics yield solutions with minute, and often null, duality gaps for instances with several hundreds of points in small computation times. To our knowledge, this is the first computational study ever reported in which these three stabbing problems are considered and where provably optimal solutions are given. [ABSTRACT FROM PUBLISHER]

The security-constrained optimal power flow problem considers both the normal state and contingency constraints, and it is formulated as a large-scale nonconvex optimization problem. We propose a global optimization algorithm based on Lagrangian duality to solve the nonconvex problem to optimality. As usual, the global approach is often time-consuming, thus, for practical uses when dealing with a large number of contingencies, we investigate two decomposition algorithms based on Benders cut and the alternating direction method of multipliers. These decomposition schemes often generate solutions with a smaller objective function values than those generated by the conventional approach and very close to the globally optimal points. [ABSTRACT FROM AUTHOR]

This article considers a differentiation flow-shop model, where the jobs are divided into various categories, each of which consists of two stages of operations. All products should be processed first on the single common machine at stage 1. At the second stage, each individual product proceeds to a dedicated machine according to its type. The problem of makespan minimization under the setting with two product types is known to be strongly NP hard. This article considers an arbitrary number of job types by developing a lower bound and two dominance rules, based upon which branch-and-bound algorithms are designed. Computational experiments are carried out to examine the performance of the proposed properties. The statistics show that the proposed properties can substantially reduce the computing efforts required for finding optimal solutions. [ABSTRACT FROM PUBLISHER]

Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex Mixed-Integer Nonlinear Programming (MINLP) problems. It is well-known that carrying out branching in a nonsimplistic manner can greatly enhance the practicality of B&B in the context of Mixed-Integer Linear Programming (MILP). No detailed study of branching has heretofore been carried out for MINLP. In this article, we study and identify useful sophisticated branching methods for MINLP, including novel approaches based on approximations of the nonlinear relaxations by linear and quadratic programs. [ABSTRACT FROM AUTHOR]

SUMMARY By realizing the feedback paths over communication networks, we get a class of networked control systems (NCSs), where the network's quality-of-service (QoS) is commonly characterized by the average dropout rate of feedback data packets. The control performance of an NCS however, is determined not only by the average dropout rate but also by the dropout pattern of feedback data packets. This paper provides a systematic way to determine the optimal dropout pattern (policy) under a given average dropout rate, where the performance is measured by the output signal power under an exogenous white noise. By modeling the finite-memory dropout policies with the general Markov chain, this paper formulates the optimal dropout policy design into the optimization of parameters of a dropout Markov chain. That optimization is first solved by an augmented Lagrangian gradient method, which may be stuck at local optima because of the problem's non-convexity. To compensate this weakness, we apply the branch-and-bound method to the optimization whose constraints are bilinear. The branch-and-bound method can approach the global optimal solution with any desired tolerance in finite steps. The obtained optimal dropout policy may be interpreted as a network's QoS constraint whose enforcement provides a hard guarantee on the control system's performance. An example is used to illustrate the effectiveness of the achieved results. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Highlights: [•] Propose the concept of transit-time-sensitive demand. [•] Containership schedule with transit-time-sensitive demand. [•] Branch-and-bound based ε-optimal solution methodology. [ABSTRACT FROM AUTHOR]

This article examines the problem of scheduling preemptive open shops to minimize the total completion time. The problem is known to be NP-hard. An efficient constructive heuristic is developed for solving large sized problems. A new lower bound scheme based on the solution of another special type of preemptive open shop problem is presented. Both of the proposed upper and lower bounds are incorporated into a branch-and-bound algorithm to solve medium sized problems. Computational results are reported. The branch-and-bound algorithm can handle problems of up to 14 jobs and 14 machines in size within a reasonable amount of time. The solution obtained by the heuristic has an average deviation of less than 0.14% from the optimal value, while the initial lower bound has an average deviation of less than 2.12% from the optimal value. Moreover, the heuristic finds approved optimal solutions for over 70% of the problem instances completely solved. [ABSTRACT FROM AUTHOR]

This paper presents branch-and-bound algorithms for the partial inverse mixed integer linear programming (PInvMILP) problem, which is to find a minimal perturbation to the objective function of a mixed integer linear program (MILP), measured by some norm, such that there exists an optimal solution to the perturbed MILP that also satisfies an additional set of linear constraints. This is a new extension to the existing inverse optimization models. Under the weighted $$L_1$$ and $$L_\infty $$ norms, the presented algorithms are proved to finitely converge to global optimality. In the presented algorithms, linear programs with complementarity constraints (LPCCs) need to be solved repeatedly as a subroutine, which is analogous to repeatedly solving linear programs for MILPs. Therefore, the computational complexity of the PInvMILP algorithms can be expected to be much worse than that of MILP or LPCC. Computational experiments show that small-sized test instances can be solved within a reasonable time period. [ABSTRACT FROM AUTHOR]

The design of circuits which are robust against variations in operating and process conditions is crucial in today's IC industry. In the analog design flow this problem can be tackled during the sizing of a new circuit. However, hardly any methods are available which support the designer to compute such a robust design if discrete parameters should be considered in this design step. Discrete parameters arise predominantly if a layout-friendly sizing should be computed in the sense that, e.g., a manufacturing grid for the transistor lengths and widths is considered or that transistor multipliers are used to allow the layout of a transistor as multifinger or common centroid structure without applying rounding operations to the carefully computed sizing. This paper presents a new Branch-and-Bound based approach which allows the automatic computation of a robust design using classical and realistic worst case analysis. The results of the sizing of three circuits show that the new approach is highly efficient. The robustness of the results computed by the new approach is validated by Monte Carlo analyses. [ABSTRACT FROM AUTHOR]

In this paper we present an exact algorithm for the Maximum Common Induced Subgraph Problem ( MCIS) by addressing it directly, using Integer Programming ( IP) and polyhedral combinatorics. We study the MCIS polytope and introduce strong valid inequalities, some of which we prove to define facets. Besides, we show an equivalence between our IP model for MCIS and a well-known formulation for the Maximum Clique problem. We report on computational results of branch-and-bound ( B&B) and branch-and-cut ( B&C) algorithms we implemented and compare them to those yielded by an existing combinatorial algorithm. [ABSTRACT FROM AUTHOR]

This work studies how to adapt the number of threads of a parallel Interval Branch and Bound algorithm to the available computational resources based on its current performance. Basically, a thread can create a new thread that will process part of the ancestor workload. In this way, load balancing is inherent to the creation of threads. The applications in which we are interested use branch-and-bound algorithms which are highly irregular and therefore difficult to predict. The proposed methods can be used for more predictable algorithms as well. This research complements and does not substitute other devices that improve the exploitation of the system, such as dynamic scheduling policies or work-stealing. Several approaches are presented. They differ in the metrics used and in the need or not having to modify the Operating System (O.S.). The scenario for this research is just one multithreaded application running in a multicore architecture. Experimental results show that the appropriate number of running threads can be determined at run-time, avoiding having to statically establish the number of threads of an application. Thread creation decisions have to be made frequently to obtain better results, but are time-consuming. One of the presented models uses the existence of an idle processor to carry out these decisions, obtaining the desired results. [ABSTRACT FROM AUTHOR]

In this study, we present a heterogeneous cooperative parallel search that integrates branch-and-bound method and tabu search algorithm. These two algorithms perform searches in parallel and cooperate by asynchronously exchanging information about the best solutions found and new initial solutions for tabu search. The rapid production of a good solution from the tabu search process provides the branch-and-bound process with a better feasible solution to accelerate the elimination of subproblems that do not contain an optimal solution. The new initial solution produced from the subproblem with a least-cost lower bound of the branch-and-bound method suggests the best potential area for tabu search to explore. We use a master-slave model to reduce the complexity of communication and enhance the performance of data exchange. A branch-and-bound process is used as the master process to control the exchange of information and the termination of computation. Several tabu search processes are executed simultaneously as the slave processes and cooperate by asynchronously exchanging information on the best solutions found and the new initial solutions by the master process of branch-and-bound. Based on the computation experiments of solving traveling salesman problems (TSP), the proposed heterogeneous parallel search algorithm outperforms a conventional parallel branch-and-bound method and a conventional parallel tabu search. We also present the computational results showing the efficiency of heterogeneous cooperative parallel search when we use more processors to accelerate search time. Thus, the proposed heterogeneous parallel search algorithm achieves linear accelerations. [ABSTRACT FROM AUTHOR]

This paper investigates an exact method for the Robotic Cell Problem. We present a branch-and-bound algorithm which is the first exact procedure specifically designed with regard to this complex flow shop scheduling variant. Also, we propose a new mathematical programming model as well as new lower bounds. Furthermore, we describe an effective genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that medium-sized instances, with up to 176 operations, can be optimally solved. Also, we found that the new proposed lower bounds outperform lower bounds from the literature. Finally, we show, that the genetic algorithm delivers good solutions while requiring short CPU times. [ABSTRACT FROM AUTHOR]

Abstract: Deciding what question to branch on at each node is a key element of search algorithms. In this paper, we describe a collection of techniques for branching decisions that are motivated from an information-theoretic perspective. The idea is to drive the search to reduce the uncertainty (entropy) in the current subproblem. We present four families of methods for branch question selection in mixed integer programming that use this idea. In the first, a variable to branch on is selected based on lookahead. This method performs comparably to strong branching on MIPLIB, and better than strong branching on hard real-world procurement optimization instances on which CPLEX’s default strong branching outperforms CPLEX’s default branching strategy. The second family combines this idea with strong branching. The third family does not use lookahead, but instead exploits the tie between indicator variables and the variables they govern. This significantly outperforms the state-of-the-art branching strategies on both combinatorial procurement problems and facility location problems. The fourth family concerns branching using carefully constructed linear inequality constraints over sets of variables. [Copyright &y& Elsevier]

This paper considers an optimal base station clustering problem for designing a mobile (wireless) communication network. For a given network with a set of nodes (base stations), the problem is to optimally partition the set of nodes into subsets (each called a cluster) such that the associated inter-cluster traffic is minimized under certain topological constraints and cluster capacity constraints. In the problem analysis, the problem is formulated as an integer programming problem. The integer programming problem is then transformed into a binary integer programming problem, for which the associated linear programming relaxation is solved in a column generation approach assisted by a branch-and-bound procedure. For the column generation, both a heuristic algorithm and a valid inequality approach are exploited. Various numerical examples are solved to evaluate the effectiveness of the LP (Linear Programming) based branch-and-bound algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with clustering algorithms for vertical partitioning. In particular, we examine the use of a branch-and-bound scheme. An existing algorithm using such a scheme may produce infeasible solutions to some problems. We adopt the same branch-and-bound scheme and develop a new branching strategy to avoid infeasibility. Illustrative examples are used to demonstrate the effectiveness of our new approach. In addition, we also show how to formulate the horizontal partitioning problem such that the same algorithm can be applied. [ABSTRACT FROM AUTHOR]

Abstract: This paper addresses scheduling a set of jobs on a single machine for delivery in batches to one customer or to another machine for further processing. The problem is a natural extension of that of minimising the sum of weighted flow times, considering the possibility of delivering jobs in batches and introducing batch delivery costs. The scheduling objective adopted is that of minimising the sum of weighted flow times and delivery costs. The extended problem arises in the context of coordination between machine scheduling and a distribution system in a supply chain network. Structural properties of the problem are investigated and used to devise a branch-and-bound solution method. For the special case, when the maximum number of batches is fixed, the branch-and-bound scheme provided shows significant improvements over an existing dynamic-programming algorithm. [ABSTRACT FROM AUTHOR]

The Bilevel Knapsack Problem (BKP) is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions of parametric Knapsack Problem. In this paper, we propose two stages exact method for solving the BKP. In the first stage, a dynamic programming algorithm is used to compute the set of reactions of the follower. The second stage consists in solving an integer program reformulation of BKP. We show that the integer program reformulation is equivalent to the BKP. Numerical results show the efficiency of our method compared with those obtained by the algorithm of Moore and Bard [ABSTRACT FROM PUBLISHER]

This paper presents an effective parallel complete anytime procedure for the resource-constrained project scheduling problem. The procedure finds a sequence of solutions in which every solution improves the previous one. To accelerate the convergence of the sequence to the optimal solution, the procedure simultaneously works in the forward and backward directions. While in the forward direction, it solves the problem at hand; in the backward direction, it solves its mirror problem. Performing simultaneously in the forward and backward directions exploits the power of double processors that are now available on most personal computers. The results of computational experiments on 2,040 benchmark instances are promising and indicate that, for many instances, a fast convergence to optimal solutions is obtained. [ABSTRACT FROM AUTHOR]