Search

Tree search algorithms, such as branch-and-bound, are the most widely used tools for solving combinatorial and non-convex problems. For example, they are the foremost method for solving (mixed) integer programs and constraint satisfaction problems. Tree search algorithms come with a variety of tunable parameters that are notoriously challenging to tune by hand. A growing body of research has demonstrated the power of using a data-driven approach to automatically optimize the parameters of tree search algorithms. These techniques use a training set of integer programs sampled from an application-specific instance distribution to find a parameter setting that has strong average performance over the training set. However, with too few samples, a parameter setting may have strong average performance on the training set but poor expected performance on future integer programs from the same application. Our main contribution is to provide the first sample complexity guarantees for tree search parameter tuning. These guarantees bound the number of samples sufficient to ensure that the average performance of tree search over the samples nearly matches its future expected performance on the unknown instance distribution. In particular, the parameters we analyze weight scoring rules used for variable selection. Proving these guarantees is challenging because tree size is a volatile function of these parameters: we prove that, for any discretization (uniform or not) of the parameter space, there exists a distribution over integer programs such that every parameter setting in the discretization results in a tree with exponential expected size, yet there exist parameter settings between the discretized points that result in trees of constant size. In addition, we provide data-dependent guarantees that depend on the volatility of these tree-size functions: our guarantees improve if the tree-size functions can be well approximated by simpler functions. Finally, via experiments, we illustrate that learning an optimal weighting of scoring rules reduces tree size. [ABSTRACT FROM AUTHOR]

In the slab warehouses of iron and steel enterprises, the slabs are stacked on top of others. Thus, some slabs will be blocked by others from being retrieved directly. In this study, we focus on optimising slab storage and pre-marshalling moves in advance so as to minimise the numbers of slabs which may block retrieval slab, the number of stacks occupied by slabs, and the number of required moves. We also address the practical concern of moving no more than two slabs together. To solve this problem, we present an integer linear programming model and further propose valid inequalities to enhance the model. Based on the labelled data from this modelling approach, a self-training technique is applied to train two functions which can predict the optimal following pre-marshalling move and storage move. By combining these functions, heuristics and branch-and-bound algorithm with the dominance rules, a multi-stage hybrid algorithm is proposed to solve practical problems. The experimental results show the effectiveness of the model, the valid inequalities, and the different components of hybrid algorithm which can produce high-quality solutions within seconds. [ABSTRACT FROM AUTHOR]

This paper concentrates on the scheduling problem in seru production system (SPS), which is a new-type advanced system with high manufacturing flexibility to response the volatile market. Motivated by practical scenarios, the seru scheduling problem in this paper considers the sequence-dependent setup time and release date to minimize the total weighted tardiness. A mixed integer programming (MIP) model is formulated, and the branch-and-bound (B & B) algorithm combining dominance propositions and the lower bound strategy is designed subsequently. Finally, computational experiments are conducted. A series of experimental results show that the proposed B & B algorithm performs very well in finding high-quality solutions, and it can find exact and near-exact solutions for 216 randomly generated instances quickly. Even when CPLEX is unable to solve the problems in five-hour, the B & B algorithm can return optimal solutions for as many as 5 serus and 22 products in a very short CPU time. [ABSTRACT FROM AUTHOR]

This paper investigates a single-machine scheduling problem of a software test with shared common setup operations. Each job has a corresponding set of setup operations, and the job cannot be executed unless its setups are completed. If two jobs have the same supporting setups, the common setups are performed only once. No preemption of any processing is allowed. This problem is known to be computationally intractable. In this study, we propose sequence-based and position-based integer programming models and a branch-and-bound algorithm for finding optimal solutions. We also propose an ant colony optimization algorithm for finding approximate solutions, which will be used as the initial upper bound of the branch-and-bound algorithm. The computational experiments are designed and conducted to numerically appraise all of the proposed methods. [ABSTRACT FROM AUTHOR]

We focus on an extension of the maximum weight perfect matching problem with additional disjunctive conflict constraints in conjunction with the degree and binary restrictions. Given a simple graph with a nonnegative weight associated with each edge and a set of conflicting edges, the perfect matching problem with conflict constraints consists of finding a maximum weight perfect matching without any conflicting edge pair. Unlike the well‐known ordinary maximum weight perfect matching problem this one is strongly 풩풫‐hard. We propose two branch‐and‐bound algorithms for the exact solution of the problem. The first one is based on an equivalent maximum weight stable set formulation with an additional cardinality restriction obtained on the graph representing conflict relations and uses the information coming from its maximal stable sets. The second one is essentially a recursive depth first search scheme that benefits from simple upper bounds incorporated with a fast infeasibility detection procedure to prune the branch‐and‐bound tree. According to the extensive computational tests it is possible to say that they are both very efficient. [ABSTRACT FROM AUTHOR]

Rescheduling can help to improve the quality of a schedule with respect to an initially given sequence. In this paper, we consider the possibility of rescheduling jobs arriving for processing at a single machine under the following limitations: (a) jobs can only be moved toward the end of the schedule and not toward the front, and (b) when a job is taken out of the sequence, it is put on a buffer of limited capacity before being reinserted in its new position closer to the end of the sequence. The buffer is organized as a stack with a last-in/first-out policy. As an objective function, we consider the minimization of the weighted number of late jobs. For this NP-hard problem, we first provide two different integer linear programming (ILP) formulations. Furthermore, we develop a branch-and-bound algorithm with a branching rule based on the movement of jobs. Then a new pseudo-polynomial dynamic programming algorithm is presented which utilizes dominance criteria and an efficient handling of states. Our computational experiments with up to 100 jobs show that this algorithm performs remarkably well and can be seen as the current method of choice. [ABSTRACT FROM AUTHOR]

This paper focuses on seru scheduling problems considering the sequence-dependent setup time in seru production system, which is a new-type manufacturing system originated in Japanese production practice recently that can better adapt to the fluctuate market demand. A mixed integer programming (MIP) model with the objective of minimizing the sum of the makespan and the total weighted tardiness is constructed for the seru scheduling problem. The branch-and-bound (B&B) algorithm with two main steps is designed subsequently, where the first step solves the assignment of products to serus, while the second step solves the scheduling optimization in each seru. Finally, the computational experiments and comparative analysis with CPLEX 12.8 are made, and the report of results verifies that the effectiveness and practicability of the proposed MIP and B&B algorithm. [ABSTRACT FROM AUTHOR]

We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We extend a result of Dash (International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 145–160, 2002) to the nonlinear setting which shows that for convex 0/1 problems, CP does at least as well as BB, with variable disjunctions. We sharpen this by giving instances of the stable set problem where we can provably establish that CP does exponentially better than BB. We further show that if one moves away from 0/1 sets, this advantage of CP over BB disappears; there are examples where BB finishes in O(1) time, but CP takes infinitely long to prove optimality, and exponentially long to get to arbitrarily close to the optimal value (for variable disjunctions). We next show that if the dimension is considered a fixed constant, then the situation reverses and BB does at least as well as CP (up to a polynomial blow up factor), for quite general families of disjunctions. This is also complemented by examples where this gap is exponential (in the size of the input data). [ABSTRACT FROM AUTHOR]

The primary role of cutting planes is to separate fractional solutions of the linear programming relaxation, which results in tighter bounds for pruning the search tree and reducing its size. Bounding, however, has an indirect impact on the size of the search tree. Cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching, which directly reduces the tree size. A partial assignment is inconsistent with a constraint set when it cannot be extended to a full feasible assignment. The constraint programming community has studied consistency extensively and used it as an effective tool for the reduction of backtracking. We extend this approach to integer programming by defining concepts of consistency that are useful in a branch-and-bound context. We present a theoretical framework for studying these concepts, their connection with the convex hull and their power to exclude infeasible partial assignments. We introduce a new class of cutting planes that target achieving consistency rather than improving dual bounds. Computational experiments on both synthetic and benchmark instances show that the new class of cutting planes can significantly outperform classical cutting planes, such as disjunctive cuts, by reducing the size of the search tree and the solution time. More broadly, we suggest that consistency concepts offer a new perspective on integer programming that can lead to a better understanding of what makes cutting planes work when used in branch-and-bound search. [ABSTRACT FROM AUTHOR]

For a binary integer program (IP) max c T x , A x ≤ b , x ∈ { 0 , 1 } n , where A ∈ R m × n and c ∈ R n have independent Gaussian entries and the right-hand side b ∈ R m satisfies that its negative coordinates have ℓ 2 norm at most n/10, we prove that the gap between the value of the linear programming relaxation and the IP is upper bounded by poly (m) (log n) 2 / n with probability at least 1 - 2 / n 7 - 2 - poly (m) . Our results give a Gaussian analogue of the classical integrality gap result of Dyer and Frieze (Math OR, 1989) in the case of random packing IPs. In constrast to the packing case, our integrality gap depends only polynomially on m instead of exponentially. Building upon recent breakthrough work of Dey, Dubey and Molinaro (SODA, 2021), we show that the integrality gap implies that branch-and-bound requires n poly (m) time on random Gaussian IPs with good probability, which is polynomial when the number of constraints m is fixed. We derive this result via a novel meta-theorem, which relates the size of branch-and-bound trees and the integrality gap for random logconcave IPs. [ABSTRACT FROM AUTHOR]

This paper investigates a single-machine scheduling problem of a software test with shared common setup operations. Each job has a corresponding set of setup operations, and the job cannot be executed unless its setups are completed. If two jobs have the same supporting setups, the common setups are performed only once. No preemption of any processing is allowed. This problem is known to be computationally intractable. In this study, we propose sequence-based and position-based integer programming models and a branch-and-bound algorithm for finding optimal solutions. We also propose an ant colony optimization algorithm for finding approximate solutions, which will be used as the initial upper bound of the branch-and-bound algorithm. The computational experiments are designed and conducted to numerically appraise all of the proposed methods.

Motivated by the call of the International Maritime Organization to meet the emission targets of 2030, this study considers two important practical aspects of quay crane scheduling: efficiency and energy consumption. More precisely, we introduce the bi-objective quay crane scheduling problem where the objective is to minimize the vessel's completion time and the crane's energy consumption. This is done by formulating a bi-objective mixed-integer programming model. A branch-and-bound algorithm was developed as the exact solution approach to find the full set of Pareto-optimal solutions. We consider (i) various lower bounds for both objectives, (ii) specific upper bounds, (iii) additional branching criteria, and (iv) fathoming criteria to detect Pareto-optimal solutions. Numerical experiments on benchmark instances show that the branch-and-bound algorithm can efficiently solve small- and medium-sized problems. [ABSTRACT FROM AUTHOR]

Finding solutions to least-squares problems with low cardinality has found many applications, including portfolio optimization, subset selection in statistics, and inverse problems in signal processing. Although most works consider local approaches that scale with high-dimensional problems, some others address its global optimization via mixed integer programming (MIP) reformulations. We propose dedicated branch-and-bound methods for the exact resolution of moderate-size, yet difficult, sparse optimization problems, through three possible formulations: cardinality-constrained and cardinality-penalized least-squares, and cardinality minimization under quadratic constraints. A specific tree exploration strategy is built. Continuous relaxation problems involved at each node are reformulated as ℓ 1 -norm-based optimization problems, for which a dedicated algorithm is designed. The obtained certified solutions are shown to better estimate sparsity patterns than standard methods on simulated variable selection problems involving highly correlated variables. Problem instances selecting up to 24 components among 100 variables, and up to 15 components among 1000 variables, can be solved in less than 1000 s. Unguaranteed solutions obtained by limiting the computing time to 1s are also shown to provide competitive estimates. Our algorithms strongly outperform the CPLEX MIP solver as the dimension increases, especially for quadratically-constrained problems. The source codes are made freely available online. [ABSTRACT FROM AUTHOR]

The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) for the clique problem that have more desirable worst-case properties, especially for sparse graphs. The smallest MIP that we propose has just O (n + m) nonzeros for graphs with n vertices and m edges. Nevertheless, it ensures a root LP bound of at most d + 1 , where d denotes the graph's degeneracy (a measure of density), and is solved in O (2 d n) branch-and-bound nodes. Meanwhile, the strongest MIP that we propose visits fewer nodes, O (1. 62 d n) . Further, when a best-bound node selection strategy is used, O (2 g n) nodes are visited, where g = (d + 1) - ω is the clique-core gap. Often, g is so small that it can be treated as a constant in which case O(n) nodes are visited. Experiments are conducted to understand their performance in practice. [ABSTRACT FROM AUTHOR]

In this paper, we present a branch-and-bound based algorithm to generate all non dominated points for a multiobjective integer programming problem with convex objective functions and linear constraints (MOICP). The principle is to solve a single objective program (P) defined from the original MOICP program with relaxed integrality constraints. Whenever an integer solution is found through the branching process, a node is created in the search tree for each criterion. That is, by adding a cutting plane that locally approximates the criterion, as to exclude a subset of dominated points. The nodes are traversed according to the depth-first strategy and the same process is repeated for the obtained programs as (P). Finally, as to illustrate the efficiency of the suggested algorithm, we present an experimental study, where we assess its efficiency using randomly generated quadratic multiobjective integer problems with linear constraints. [ABSTRACT FROM AUTHOR]

We introduce the referenced vertex ordering problem (revorder) as a combinatorial decision problem generalizing several vertex ordering problems that already appeared in the scientific literature under different guises. In other words, revorder is a generic problem with several possible extensions corresponding to various real-life applications. Given a simple undirected graph $G=(V,E)$, revorder basically asks whether the vertices of $G$ can be sorted in a way to guarantee that every vertex is adjacent to a minimal number of its predecessors in the order. Previous works show that revorder, as well as its optimization counterpart, denoted in our work as min revorder, are NP-hard. We give a survey of methods and algorithms that can be applied to the solution of min revorder, and we develop a new enumeration scheme for its solution. Our theoretical analysis of this scheme yields several pruning techniques aimed at the reduction of the number of enumeration nodes. We then discuss how upper and lower bounds can be computed during the enumeration to design a branch-and-bound algorithm. Finally, we validate our branch-and-bound algorithm by conducting a large set of computational experiments on instances coming from various real-life applications. Our results highlight that the newly introduced pruning techniques allow the computation of good-quality solutions (in comparison with other solver’s solutions) while reducing the overall computational cost. Our branch-and-bound outperforms other existing solution methods: among 180 instances with 60 vertices, it solves 179 instances to optimality whereas the best existing method is only able to solve 109 of them. Moreover, our tests show that our algorithm can solve medium-scale instances up to 500 vertices, which opens the perspective of handling new real-life problems. Our implementation of the branch-and-bound algorithm, together with all instances we have used, is publicly available on GitLabGitLab repository: https://gitlab.insa-rennes.fr/Jeremy.Omer/min-revorder.git.

Applications of mixed integer programming can be found in many industries, such as transportation, healthcare, energy, and finance, and their economic impact is significant. It is also well known that mixed integer programs (MIPs) can be very difficult to solve. Their challenge continues to stimulate research in the design and implementation of efficient and effective techniques that can better solve them. In this study, we introduce a novel and powerful approach for solving certain classes of mixed integer programs (MIPs): decomposition branching. Two seminal and widely used techniques for solving MIPs, branch-and-bound and decomposition, form its foundation. Computational experiments with instances of a weighted set covering problem and a regionalized p-median facility location problem with assignment range constraints demonstrate its efficacy: it explores far fewer nodes and can be orders of magnitude faster than a commercial solver and an automatic Dantzig-Wolfe approach. We introduce a novel and powerful approach for solving certain classes of mixed integer programs (MIPs): decomposition branching. Two seminal and widely used techniques for solving MIPs, branch-and-bound and decomposition, form its foundation. Computational experiments with instances of a weighted set covering problem and a regionalized p-median facility location problem with assignment range constraints demonstrate its efficacy: it explores far fewer nodes and can be orders of magnitude faster than a commercial solver and an automatic Dantzig-Wolfe approach. [ABSTRACT FROM AUTHOR]

In the context of the maximum stable set problem, rank inequalities impose that the cardinality of any set of vertices contained in a stable set be, at most, as large as the stability number of the subgraph induced by such a set. Rank inequalities are very general, as they subsume many classical inequalities such as clique, hole, antihole, web, and antiweb inequalities. In spite of their generality, the exact separation of rank inequalities has never been addressed without the introduction of topological restrictions on the induced subgraph and the tightness of their closure has never been investigated systematically. In this work, we propose a methodology for optimizing over the closure of all rank inequalities with a right-hand side no larger than a small constant without imposing any restrictions on the topology of the induced subgraph. Our method relies on the exact separation of a relaxation of rank inequalities, which we call relaxed k-rank inequalities, whose closure is as tight. We investigate the corresponding separation problem, a bilevel programming problem asking for a subgraph of maximum weight with a bound on its stability number, whose study could be of independent interest. We first prove that the problem is Σ 2 P -hard and provide some insights on its polyhedral structure. We then propose two exact methods for its solution: a branch-and-cut algorithm (which relies on a family of faced-defining inequalities which we introduce in this paper) and a purely combinatorial branch-and-bound algorithm. Our computational results show that the closure of rank inequalities with a right-hand side no larger than a small constant can yield a bound that is stronger, in some cases, than Lovász's Theta function, and substantially stronger than bounds obtained with standard inequalities that are valid for the stable set problem, including odd-cycle inequalities and wheel inequalities. Summary of Contribution: This paper proposes two original methods for solving a challenging cut-separation problem (of bilevel type) for a large class of inequalities valid for one of the key operations research problems, namely, the max stable set problem. An extensive set of experimental results validates the proposed methods. All the source code and data sets are available online on GitHub. [ABSTRACT FROM AUTHOR]

We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the decision variables, akin to single objective problems, although we also sometimes split gaps and branch in the objective space. The various algorithms are implemented using a data structure for storing Pareto sets. Computational experiments are carried out on literature instances and on a new set of instances that we generate using a benchmark library (MIPLIB2017) for single objective problems. We also perform comparisons against the triangle splitting method from literature, which is an objective space search algorithm. Summary of Contribution: Biobjective mixed-integer optimization problems have two linear objectives and a mixed-integer feasible region. Such problems have many applications in operations research, because many real-world optimization problems naturally comprise two conflicting objectives to optimize or can be approximated in such a manner and are even harder than single objective mixed-integer programs. Solving them exactly requires the computation of all the nondominated solutions in the objective space, whereas some applications may also require finding at least one solution in the decision space corresponding to each nondominated solution. This paper provides an exact algorithm for solving these problems using the branch-and-bound method, which works predominantly in the decision space. Of the many ingredients of this algorithm, some parts are direct extensions of the single-objective version, but the main parts are newly designed algorithms to handle the distinct challenges of optimizing over two objectives. The goal of this study is to improve solution quality and speed and show that decision-space algorithms perform comparably to, and sometimes better than, algorithms that work mainly in the objective-space. [ABSTRACT FROM AUTHOR]

Motivated by the call of the International Maritime Organization to meet the emission targets of 2030, this study considers two important practical aspects of quay crane scheduling: efficiency and energy consumption. More precisely, we introduce the bi-objective quay crane scheduling problem where the objective is to minimize the vessel’s completion time and the crane’s energy consumption. This is done by formulating a bi-objective mixed-integer programming model. A branch-and-bound algorithm was developed as the exact solution approach to find the full set of Pareto-optimal solutions. We consider (i) various lower bounds for both objectives, (ii) specific upper bounds, (iii) additional branching criteria, and (iv) fathoming criteria to detect Pareto-optimal solutions. Numerical experiments on benchmark instances show that the branch-and-bound algorithm can efficiently solve small- and medium-sized problems.

The generalization of mixed integer program (MIP) techniques to deal with nonlinear, potentially nonconvex, constraints has been a fruitful direction of research for computational mixed integer nonlinear programs (MINLPs) in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers toward the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared toward two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality. Summary of Contribution: This original article concerns the advancement of exact general-purpose algorithms for solving one of the largest and most prominent problem classes in optimization, mixed integer nonlinear programs (MINLPs). It demonstrates how methods for conflict analysis that learn from infeasible subproblems can be transferred to nonlinear optimization. Further, it develops theory for how nonlinear dual infeasibility proofs can be derived from a nonlinear relaxation. This paper features a thoroughly computational study regarding the impact of conflict analysis techniques on the overall performance of a state-of-the-art MINLP solver when solving MINLPs to global optimality. [ABSTRACT FROM AUTHOR]

Two essential ingredients of modern mixed-integer programming solvers are diving heuristics, which simulate a partial depth-first search in a branch-and-bound tree, and conflict analysis, which learns valid constraints from infeasible subproblems. So far, these techniques have mostly been studied independently: primal heuristics for finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. In this paper, we pose the question of whether and how the orthogonal goals of proving infeasibility and generating improving solutions can be pursued in a combined manner such that a state-of-the-art solver can benefit. To do so, we integrate both concepts in two different ways. First, we develop a diving heuristic that simultaneously targets the generation of valid conflict constraints from the Farkas dual and the generation of improving solutions. We show that, in the primal, this is equivalent to the optimistic strategy of diving toward the best bound with respect to the objective function. Second, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classic coefficient diving. In a detailed computational study, both methods are evaluated on the basis of an implementation in the source-open-solver SCIP. The experimental results underline the potential of combining both diving heuristics and conflict analysis. Summary of Contribution. This original article concerns the advancement of exact general-purpose algorithms for solving one of the largest and most prominent problem classes in optimization, mixed-integer linear programs. It demonstrates how methods for conflict analysis that learn from infeasible subproblems can be combined successfully with diving heuristics that aim at finding primal solutions. For two newly designed diving heuristics, this paper features a thoroughly computational study regarding their impact on the overall performance of a state-of-the-art MIP solver. [ABSTRACT FROM AUTHOR]

In bi-objective integer optimization the optimal result corresponds to a set of nondominated solutions. We propose a generic bi-objective branch-and-bound algorithm that uses a problem-independent branching rule exploiting available integer solutions and takes advantage of integer objective coefficients. The developed algorithm is applied to bi-objective facility location problems and the bi-objective set covering problem, as well as to the bi-objective team orienteering problem with time windows. In the latter case, lower bound sets are computed by means of column generation. Comparison with state-of-the-art exact algorithms shows the effectiveness of the proposed branch-and-bound algorithm. [ABSTRACT FROM AUTHOR]

• Consideration of the optimal phasor measurement unit placement problem without radial buses. • Phasor measurement unit is pre-assigned at each bus connected to radial bus. • A two-phase branch-and-bound algorithm is used to determine the strategic locations for placement of phasor measurement unit. • The redundancy measurement is performed for ranking the obtained multiples solutions. This paper proposes a mixed integer nonlinear programming (MINLP) formulation with binary-valued variables for the optimal installation of the phasor measurement units (PMUs) in a power network. The MINLP framework has been solved by a two-phase branch-and-bound algorithm (BBA) for the optimal PMU placement (OPP) problem. The present work deals with the solution of the OPP problem without considering the radial buses including in the optimal solution. PMU is pre-assigned to each bus connected to a radial bus such that the radial buses are excluded from the list of potential PMU locations. The programming technique is used to determine the optimum number of PMUs and their locations to make the interconnected power network completely observable. The proposed BBA may provide multiple solutions at the lowest objective value, each time the optimizer routine restarts. Therefore, the obtained optimal solutions are being ranked regarding the measurement redundancy index. The two-phase branch-and-bound algorithm is applied to IEEE standard test systems as well as to New England 39- bus and a northern regional power grid 246- bus system. The proposed algorithm has been compared with the existing programming techniques in the recent literature. The simulation results obtained by the proposed BBA indicate the effectiveness and the efficiency to detect the desired target. [ABSTRACT FROM AUTHOR]

Modern mixed-integer programming (MIP) solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three distinct phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behaviour of the non-commercial MIP solver Scip at the predicted phase transition points. [ABSTRACT FROM AUTHOR]

This paper introduces the problem of backfeed fiber cables network design. It considers cable separation operations and costs as well as a non-linear cable line cost, and the feedback technique. An integer programming based solution is proposed, and some associated valid inequalities are introduced. The problem is proven to be NP-Hard. The formulation is assessed on real-life instances. [ABSTRACT FROM AUTHOR]

This paper considers a joint scheduling problem of macro-level yard section allocation and transfer manpower assignment in automobile RO-RO terminals. The joint scheduling problem is formulated as a mixed integer programming model with the objective of minimizing the total necessary driving distance of vehicles. Relaxation cases derived from a series of ingenious problem analyses and dual segmentation techniques based on mathematical derivations are presented. In addition, compressed strategies are applied to reduce the complexity of our problem. Then, we develop an amalgamated algorithm consisting of a rule-based stepwise algorithm, a reinforced column generation, and a multi-root branch-and-bound. Numerical experiments based on random data and a case study based on real operation data are conducted to evaluate the performance of our algorithms. The results show that the proposed algorithms are capable of generating high-quality solutions efficiently and are of great practical value in daily operations. • A joint scheduling problem of RO-RO terminals is studied. • A mixed integer programming model is built. • Relaxation and dual segmentation are applied to develop algorithms. • A column generation based heuristic algorithm is proposed. • A series of experiments with case study are conducted. [ABSTRACT FROM AUTHOR]

Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a mixed-integer linear programming solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, we present the basic concept of having two parallel extensions, and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator), including an implementation of deterministic parallelization. Second, we discuss the difficulties in achieving a good performance that utilizes all resources on an actual computing environment, and the difficulties of performance evaluation of the parallel solvers. Third, we present a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions. Finally, we demonstrate the current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer nonlinear programs (MINLPs) in parallel. The online appendix is available at . [ABSTRACT FROM AUTHOR]

Many studies regarding environmental concerns in forest harvest scheduling problems deal with constraints on the maximum clearcut size. However, these constraints tend to disperse harvests across the forest and thus to generate a more fragmented landscape. When a forest is fragmented, the amount of edge increases at the expense of the core area. Highly fragmented forests can neither provide the food, cover, nor the reproduction needs of core-dependent species. This study presents a branch-and-bound procedure designed to find good feasible solutions, in a reasonable time, for forest harvest scheduling problems with constraints on maximum clearcut size and minimum core habitat area. The core area is measured by applying the concept of subregions. In each branch of the branch-and-bound tree, a partial solution leads to two children nodes, corresponding to the cases of harvesting or not a given stand in a given period. Pruning is based on constraint violations or unreachable objective values. The approach was tested with forests ranging from some dozens to more than a thousand stands. In general, branch-and-bound was able to quickly find optimal or good solutions, even for medium/large instances. [ABSTRACT FROM AUTHOR]

The best performing exact algorithms for the capacitated vehicle routing problem developed in the last 10 years are based in the combination of cut and column generation. Some authors only used cuts expressed over the variables of the original formulation, in order to keep the pricing subproblem relatively easy. Other authors could reduce the duality gaps by also using a restricted number of cuts over the master LP variables, stopping when the pricing becomes prohibitively hard. A particularly effective family of such cuts are the subset row cuts. This work introduces a technique for greatly reducing the impact on the pricing of these cuts, thus allowing much more cuts to be added. The newly proposed branch-cut-and-price algorithm also incorporates and combines for the first time (often in an improved way) several elements found in previous works, like route enumeration and strong branching. All the instances used for benchmarking exact algorithms, with up to 199 customers, were solved to optimality. Moreover, some larger instances with up to 360 customers, only considered before by heuristic methods, were solved too. [ABSTRACT FROM AUTHOR]

Branch-and-Bound (B&B) algorithms are tree-based exploratory methods for solving combinatorial optimization problems exactly to optimality. These problems are often large in size and known to be NP-hard to solve. The construction and exploration of the B&B-tree are performed using four operators: branching, bounding, selection and pruning. Such algorithms are irregular which makes their parallel design and implementation on GPU challenging. Existing GPU-accelerated B&B algorithms perform only a part of the algorithm on the GPU and rely on the transfer of pools of subproblems across the PCI Express bus to the device. To the best of our knowledge, the algorithm presented in this paper is the first GPU-based B&B algorithm that performs all four operators on the device and subsequently avoids the data transfer bottleneck between CPU and GPU. The implementation on GPU is based on the Integer–Vector–Matrix (IVM) data structure which is used instead of a conventional linked-list to store and manage the pool of subproblems. This paper revisits the IVM-based B&B algorithm on the GPU, addressing the irregularity of the algorithm in terms of workload, memory access patterns and control flow. In particular, the focus is put on reducing thread divergence by making a judicious choice for the mapping of threads onto the data. Compared to a GPU-accelerated B&B based on a linked-list, the algorithm presented in this paper solves a set of standard flowshop instances on an average 3.3 times faster. [ABSTRACT FROM AUTHOR]

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]

The maximum cardinality subset selection problem requires finding the largest possible subset from a set of objects, such that one or more conditions are satisfied. An important extension of this problem is to extract multiple subsets, where the addition of one more object to a larger subset would always be preferred to increases in the size of one or more smaller subsets. We refer to this as the multiple subset maximum cardinality selection problem ( MSMCSP). A recently published branch-and-bound algorithm solves the MSMCSP as a partitioning problem. Unfortunately, the computational requirement associated with the algorithm is often enormous, thus rendering the method infeasible from a practical standpoint. In this paper, we present an alternative approach that successively solves a series of binary integer linear programs to obtain a globally optimal solution to the MSMCSP. Computational comparisons of the methods using published similarity data for 45 food items reveal that the proposed sequential method is computationally far more efficient than the branch-and-bound approach. [ABSTRACT FROM AUTHOR]

Haplotype inference by pure parsimony ( Hipp ) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of Hipp to the problem of finding all optimal solutions, which we call Chipp . We study intrinsic haplotype features, such as backbone haplotypes and fat genotypes as well as equal columns and decomposability . We explicitly exploit these features in three computational approaches that are based on integer linear programming, depth-first branch-and-bound, and Boolean satisfiability. Further we introduce two hybrid algorithms that draw upon the diverse strengths of the approaches. Our experimental analysis shows that our optimized algorithms are significantly superior to the baseline algorithms, often with orders of magnitude faster running time. Finally, our experiments provide some useful insights into the intrinsic features of this important problem. [ABSTRACT FROM AUTHOR]

The branch-and-bound (B&B) algorithmic framework has been used successfully to find exact solutions for a wide array of optimization problems. B&B uses a tree search strategy to implicitly enumerate all possible solutions to a given problem, applying pruning rules to eliminate regions of the search space that cannot lead to a better solution. There are three algorithmic components in B&B that can be specified by the user to fine-tune the behavior of the algorithm. These components are the search strategy, the branching strategy, and the pruning rules. This survey presents a description of recent research advances in the design of B&B algorithms, particularly with regards to these three components. Moreover, three future research directions are provided in order to motivate further exploration in these areas. [ABSTRACT FROM AUTHOR]

In this paper we propose a new algorithm for finding a global solution of indefinite quadratic integer programming. We first derive Lagrangian dual bounds by D.C. decomposition and Lagrangian relaxation. And then a new branch-and-bound based on Lagrangian dual bounds and integral hyper-rectangular bisection is presented. Finally, preliminary numerical results are reported. [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]

We consider a class of two-stage stochastic integer programs and their equivalent reformulation that uses the integer programming value functions in both stages. One class of solution methods in the literature is based on the idea of pre-computing and storing exact value functions, and then exploiting this information within a global branch-and-bound framework. Such methods are known to be very sensitive to the magnitude of feasible right-hand side values. In this note we propose a simple constraint-aggregation based approach that potentially alleviates this limitation. [ABSTRACT FROM AUTHOR]