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]

We propose a new upper bounding procedure for global minimization problems with continuous variables and possibly nonconvex inequality and equality constraints. Upper bounds are crucial for standard termination criteria of spatial branch-and-bound (SBB) algorithms to ensure that they can enclose globally minimal values sufficiently well. However, whereas for most lower bounding procedures from the literature, convergence on smaller boxes is established, this does not hold for several methods to compute upper bounds even though they often perform well in practice. In contrast, our emphasis is on the convergence. We present a new approach to verify the existence of feasible points on boxes, on which upper bounds can then be determined. To this end, we resort to existing convergent feasibility verification approaches for purely equality and box constrained problems. By considering carefully designed modifications of subproblems based on the approximation of active index sets, we enhance such methods to problems with additional inequality constraints. We prove that our new upper bounding procedure finds sufficiently good upper bounds so that termination of SBB algorithms is guaranteed after a finite number of iterations. Our theoretical findings are illustrated by computational results on a large number of standard test problems. These results show that compared with interval Newton methods from the literature, our proposed method is more successful in feasibility verification for both, a full SBB implementation (42 instead of 26 test problems) and exhaustive sequences of boxes around known feasible points (120 instead of 29 test problems). History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0162) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0162). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

The branch-and-bound algorithm based on decision diagrams is a framework for solving discrete optimization problems with a dynamic programming formulation. It works by compiling a series of bounded-width decision diagrams that can provide lower and upper bounds for any given subproblem. Eventually, every part of the search space will be either explored or pruned by the algorithm, thus proving optimality. This paper presents new ingredients to speed up the search by exploiting the structure of dynamic programming models. The key idea is to prevent the repeated expansion of nodes corresponding to the same dynamic programming states by querying expansion thresholds cached throughout the search. These thresholds are based on dominance relations between partial solutions previously found and on pruning inequalities given by rough upper bounds and local bounds — two additional filtering techniques recently introduced. Computational experiments show that the pruning brought by this caching mechanism allows for significantly reducing the number of nodes expanded by the algorithm. This results in more benchmark instances of difficult optimization problems being solved in less time while using narrower decision diagrams. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0340), as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0340). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Abstract In many applications, there is a need for algorithms that can align partially overlapping point clouds while remaining invariant to corresponding transformations. This research presents a method that achieves these goals by minimizing a binary linear assignment-least squares (BLALS) energy function. First, we reformulate the BLALS problem as the minimization of a quadratic function with quadratic and linear constraints through variable substitution. By utilizing semidefinite relaxation and the convex envelope of bilinear monomials, we relax the problem to create a lower bound that can be solved using linear assignment and low-dimensional semidefinite programming. Additionally, we develop a branch-and-bound (BnB) algorithm that only branches over the transformation variable, which enhances convergence. Experimental results show that, compared to state-of-the-art approaches, the proposed method is robust against non-rigid deformation and outliers when the outliers are separate from the inliers. However, its robustness decreases when outliers are mixed with inliers. The run time of our method is relatively high due to the need to solve a semidefinite program in each iteration of the BnB algorithm.

The lot-streaming flowshop scheduling problem with stochastic due time is addressed in this paper, with the objective of minimizing the sum of expected job delays. Closed-form expressions for the expected delays of jobs are derived under three classical distribution conditions. A mathematical model is then formulated, considering set-up times and stochastic due time. To address the highly nonlinear nature of the model, a linearization is performed. Furthermore, an optimization algorithm is designed using a Logic-based Benders decomposition (LBBD) approach combined with branch-and-bound. Two effective acceleration strategies are introduced to improve the efficiency of the algorithm. The numerical experiments demonstrate the effectiveness of the proposed algorithm, and the necessity of considering stochastic lead times is verified by comparing the results with those obtained from deterministic due time.

Copyright of Journal of Shanghai Jiao Tong University (1006-2467) is the property of Journal of Shanghai Jiao Tong University Editorial Office and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The Discretizable Molecular Distance Geometry Problem (DMDGP) plays a key role in the construction of three-dimensional molecular structures from interatomic distances acquired through nuclear magnetic resonance (NMR) spectroscopy, with the primary objective of validating a sequence of distance constraints related to NMR data. This article addresses the escalating complexity of the DMDGP encountered with larger and more flexible molecules by introducing a novel strategy via the Molecular Ordered Covering Problem, which optimizes the ordering of distance constraints to improve computational efficiency in DMDGP resolution. This approach utilizes a specialized Branch-and-Bound (BB) algorithm, tested on both synthetic and actual protein structures from the protein data bank. Our analysis demonstrates the efficacy of the previously proposed greedy heuristic in managing complex molecular scenarios, highlighting the BB algorithm's utility as a validation mechanism. This research contributes to ongoing efforts in molecular structure analysis, with possible implications for areas such as protein folding, drug design, and molecular modeling. [ABSTRACT FROM AUTHOR]

In this paper, we consider two single-machine scheduling problems with deteriorating jobs and controllable processing time. The job processing time is a function of its starting time and resource allocation. For the convex resource function, a bicriteria analysis is provided, where the first (respectively, second) criteria is to minimize total weighted completion time (respectively, total resource consumption cost). The first problem is to minimize the weighted sum of the total weighted completion time and the total resource consumption cost. The second problem is to minimize the total weighted completion time subject to the total resource consumption cost is bound. These both problems are NP-hard, we propose some heuristic algorithms and a branch-and-bound algorithm to solve the problems. [ABSTRACT FROM AUTHOR]

The presence of symmetries in binary programs typically degrades the performance of branch-and-bound solvers. In this article, we derive efficient variable fixing algorithms to discard symmetric solutions from the search space based on propagation techniques for cyclic groups. Our algorithms come with the guarantee to find all possible variable fixings that can be derived from symmetry arguments; that is, one cannot find more variable fixings than those found by our algorithms. Because every permutation symmetry group of a binary program has cyclic subgroups, the derived algorithms can be used to handle symmetries in any symmetric binary program. In experiments, we also provide numerical evidence that our algorithms handle symmetries more efficiently than other variable fixing algorithms for cyclic symmetries. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms—Discrete. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0060. [ABSTRACT FROM AUTHOR]

To increase the efficiency of last-mile delivery, online retailers can adopt pickup points in their operations. The retailer may then incentivize customers to steer them from home to pickup point delivery to reduce costs. However, it is usually uncertain whether the customer accepts this incentive to switch to pickup delivery. This setup gives rise to a new last-mile delivery problem with integrated incentive and routing decisions under uncertainty. We model this problem as a two-stage stochastic program with decision-dependent uncertainty. In the first stage, a retailer decides which customers to incentivize. However, customers' reaction to the incentive is stochastic: they may accept the offer and switch to pickup point delivery, or they may decline the offer and stick with home delivery. In the second stage, after customers' final delivery choices are revealed, a vehicle route is planned to serve customers via the delivery option of their choice. We develop an exact branch-and-bound algorithm and propose several heuristics to improve the algorithm's scalability. Our algorithm solves instances with up to 50 customers, realizing on average 4%–8% lower last-mile delivery costs compared with the commonly applied approaches in the industry that do not use incentives or offer incentives to all customers. We also develop a benchmark policy that gives very fast solutions with a 2% average optimality gap for small instances and up to 2% average cost increase compared with the heuristic solutions. Funding: This project received funding from the European Union's Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement [Grant 765395]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0287. [ABSTRACT FROM AUTHOR]

The multiple traveling salesman problems (MTSP), which arise from real world problems, are essential in urban logistics. Variations such as MinMax-MTSP and Bounded-MTSP aim to distribute workload evenly among salesmen and impose constraints on visited cities, respectively. Branch-and-bound (B&B) provides an exact algorithm solution for these problems. The Learn to Branch (L2B) approach guides branch node selection through deep learning. In this study, we utilize mathematical modeling of Bipartite Graph Neural Network (BiGNN) and an attention mechanism to support B&B in exploring solution spaces through imitation learning. The problems are framed to formulate mixed integer linear programming, which is different from conventional algorithms. It is proposed that a bipartite graph network approach makes a feature representation by setting a structure of constraints and variables. Experimental results showed that our model can generate more accurate solutions than three benchmark models. The BiGNN model can effectively learn the strong branch strategy, which reduces solution time by replacing complex calculations with fast approximations. Additionally, the small-scale instances model can be applied to larger-scale ones.

3D object alignment is essential in multiple fields. For instance, to allow precise measurements in metrology, to perform surface/volumetric checks or quality control in industrial inspection, to align partial captures of a 3D object during object scanning, to simplify object recognition or classification in pattern recognition, accuracy and speed, being opposed, are desirable features of those algorithms. Nevertheless, they can be more or less critical depending on the application area. In the present work, we propose a methodology to improve the alignment of 3D objects reconstructed using shape-from-silhouette techniques. This reconstruction technique produces objects with small synthetic bulges, making them more difficult to align accurately. On the one hand, prealignment and branch-and-bound techniques are used to improve the convergence and speed of the alignment algorithms. On the other hand, a method to obtain a precise alignment even in the presence of bulges is presented. Finally, a refinement of the shape-from-silhouettes technique is shown. This technique uses multiple captures to refine object reconstruction and reduce or eliminate, among other improvements, synthetic bulges.

The computational efficiency of unit commitment (UC) is important for power system operations. Traditionally the unit commitment problem is solved per hour in a day, but with the scale of the power system and the electricity market continuing to expand, the large-scale UC problem will be hard to be solved within 1 h which will affect the power system operation and market clearing. To reduce the solving time of the large-scale UC problem, an ultra-fast optimization algorithm of neural branching for unit commitment (NBUC) is proposed. NBUC learns the branch and bound (B&B) decision made by full strong branching (FSB), which can generate the perfect B&B order to minimize the iterative process but take a lot of time to decide the perfect order by using graph convolutional neural network according to the historical data, and then makes the perfect order prediction with a certain precision without spending a lot of time to make B&B decision which minimizes the solving time including the iteration time and decision time in order to solve the large-scale UC problem quickly. A modified RTS-96 bus system is used to validate the effectiveness of the proposed NBUC. The results show 9.3% and 23.2% reductions in computational time compared with commercial software CPLEX and SCIP.

The manufacturing sector faces unprecedented challenges, including intense competition, a surge in product varieties, heightened customization demands, and shorter product life cycles. These challenges underscore the critical need to optimize manufacturing systems. Among the most enduring and complex challenges within this domain is production scheduling. In practical scenarios, setup time is whenever a machine transitions from processing one product to another. Job scheduling with setup times or associated costs has garnered significant attention in both manufacturing and service environments, prompting extensive research efforts. While previous studies on customer order scheduling primarily focused on orders or jobs to be processed across multiple machines, they often overlooked the crucial factor of setup time. This study addresses a sequence-dependent bi-criterion scheduling problem, incorporating order delivery considerations. The primary objective is to minimize the linear combination of the makespan and the sum of weighted completion times of each order. To tackle this intricate challenge, we propose pertinent dominance rules and a lower bound, which are integral components of a branch-and-bound methodology employed to obtain an exact solution. Additionally, we introduce a heuristic approach tailored to the problem's unique characteristics, along with three refined variants designed to yield high-quality approximate solutions. Subsequently, these three refined approaches serve as seeds to generate three distinct populations or chromosomes, each independently employed in a genetic algorithm to yield a robust approximate solution. Ultimately, we meticulously assess the efficacy of each proposed algorithm through comprehensive simulation trials. [ABSTRACT FROM AUTHOR]

We propose a global optimization method based on simplex subdivision and Lagrange dual bound to solve a specific type of problem known as linear multiplicative problem (LMP). The method utilizes the Lagrangian duality theory to solve the equivalent problem (ELMP) and obtain a lower bound by solving a linear programming problem (LP). To improve the convergence speed of the algorithm, we introduce two deleting rules that efficiently prune the feasible region without an optimal solution. These rules help accelerate the algorithm’s convergence by reducing unnecessary computations. The convergence of the proposed algorithm is theoretically proven, ensuring its reliability and effectiveness. To validate its feasibility and performance, we conduct numerical experiments. [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 consider the factor-risk-constrained mean-variance portfolio-selection (MVPS) problem that allows managers to construct portfolios with desired factor-risk characteristics. Its optimization model is a non-convex quadratically constrained quadratic program that is known to be NP-hard. In this paper, we investigate the new global algorithm for factor-risk-constrained MVPS problem based on the successive convex optimization (SCO) method and the semi-definite relaxation (SDR) with a second-order cone (SOC) constraint. We first develop an SCO algorithm and show that it converges to a KKT point of the problem. We then develop a new global algorithm for factor-risk-constrained MVPS, which integrates the SCO method, the SDR with an SOC constraint, the branch-and-bound framework and the adaptive branch-and-cut rule for factor-related variables, to find a globally optimal solution to the underlying problem within a pre-specified ϵ -tolerance. We establish the global convergence of the proposed algorithm and its complexity. Preliminary numerical results demonstrate the effectiveness of the proposed algorithm in finding a globally optimal solution to medium- and large-scale instances of factor-risk-constrained MVPS. [ABSTRACT FROM AUTHOR]

In this paper, we study a single-machine green scheduling problem with learning effects and past-sequence-dependent delivery times. The problem can be properly applied to tackle green manufacturing where production and delivery time are variable and highly subject to process-reengineering. Our goal is to determine the optimal sequence such that total weighted completion time and maximum tardiness are minimized. For the general case, we provide the analysis procedure of lower bound, and also propose the heuristic and branch-and-bound algorithms. Furthermore, computational experiments are conducted to demonstrate the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we investigate effective algorithms for the worst-case linear optimization (WCLO) under polyhedral uncertainty on the right-hand-side of the constraints that arises from a broad range of applications and is known to be strongly NP-hard. We first develop a successive convex optimization (SCO) algorithm for WCLO and show that it converges to a local solution of the transformed problem of WCLO. Second, we develop a global algorithm (called SCOBB) for WCLO that finds a globally optimal solution to the underlying WCLO within a pre-specified ϵ -tolerance by integrating the SCO method, LO relaxation, branch-and-bound framework and initialization. We establish the global convergence of the SCOBB algorithm and estimate its complexity. Finally, we integrate the SCOBB algorithm for WCLO to develop a global algorithm for the two-stage adaptive robust optimization with a polyhedral uncertainty set. Preliminary numerical results illustrate that the SCOBB algorithm can effectively find a global optimal solution to medium and large-scale WCLO instances. [ABSTRACT FROM AUTHOR]

The performance of branch-and-bound algorithms for solving non-convex optimization problems greatly depends on convex relaxation techniques. They generate convex regions which are used for improving the bounds of variable domains. In particular, convex polyhedral regions can be represented by a linear system A. x = b . Then, bounds of variable domains can be improved by minimizing and maximizing variables in the linear system. Reducing or contracting optimally variable domains in linear systems, however, is an expensive task. It requires solving up to two linear programs for each variable (one for each variable bound). Suboptimal strategies, such as preconditioning, may offer satisfactory approximations of the optimal reduction at a lower cost. In non-square linear systems, a preconditioner P can be chosen such that P. A is close to a diagonal matrix. Thus, the projection of the equivalent system P. A. x = P. b over x, by using an iterative method such as Gauss–Seidel, can significantly improve the contraction. In this paper, we show how to generate an optimal preconditioner, i.e., a preconditioner that helps the Gauss–Seidel method to optimally reduce the variable domains. Despite the cost of generating the preconditioner, it can be re-used in sub-regions of the search space without losing too much effectiveness. Experimental results show that, when used for reducing domains in non-square linear systems, the approach is significantly more effective than Gauss-based elimination techniques. Finally, the approach also shows promising results when used as a component of a solver for non-convex optimization problems. [ABSTRACT FROM AUTHOR]

In classical schedule problems, the actual processing time of a job is a fixed constant, but in the actual production process, the processing time of a job is affected by a variety of factors, two of which are the learning effect and resource allocation. In this paper, single-machine scheduling problems with resource allocation and a time-dependent learning effect are investigated. The actual processing time of a job depends on the sum of normal processing times of previous jobs and the allocation of non-renewable resources. With the convex resource consumption function, the goal is to determine the optimal schedule and optimal resource allocation. Three problems arising from two criteria (i.e., the total resource consumption cost and the scheduling cost) are studied. For some special cases of the problems, we prove that they can be solved in polynomial time. More generally, we propose some accurate and intelligent algorithms to solve these problems. [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]

We consider in this paper a class of linear multiplicative programming problems that arise from numerous applications such as network flows and financial optimization. The problem is first transformed into an equivalent nonlinear optimization problem to provide a novel convex quadratic relaxation. A simplicial branch-and-bound algorithm is then designed to globally solve the problem, based on the proposed relaxation and simplicial branching process. The convergence and computational complexity of the algorithm are also analyzed. The results of numerical experiments confirm the efficiency of the proposed algorithm for tested instances. [ABSTRACT FROM AUTHOR]

Focusing on the dynamic improvement of the underlying service network configuration, this paper aims to address a specific challenge of redesigning a multi-echelon city logistics distribution network. By considering the intra-echelon connection of facilities within the same layer of echelon, we propose a new distribution network design model by reformulating the classical quadratic assignment problem (QAP). To minimize the overall transportation costs, the proposed model jointly optimizes two types of decisions to enable agile distribution with dynamic "shortcuts": (i) the allocation of warehouses to supply the corresponding distribution centers (DCs), and (ii) the demand coverage decision from distribution centers to delivery stations. Furthermore, a customized branch-and-bound algorithm is developed, where the lower bound is obtained by adopting Gilmore and Lawler lower Bound (GLB) for QAP. We conduct extensive computational experiments, highlighting the significant contribution of GLB-oriented lower bound, to obtain practical solutions; this type of efficient mathematical lower bounds offers a powerful tool for balancing theoretical research ideas with practical and industrial applicability. [ABSTRACT FROM AUTHOR]

The quadratically constrained quadratic programming problem often appears in various fields such as engineering practice, management science and network communication. This paper mainly considers a non-convex quadratic programming problem with convex quadratic constraints. Firstly, the objective function of the problem is reconstructed into a form composed of only one convex function and several linear functions by using the eigenvalue decomposition technique of matrix. Then the reconstructed problem is converted to the equivalent problem with simple concave quadratic objective function in the outcome space by introducing appropriate auxiliary variables, and its feasible domain is convex. Based on the branch-and-bound framework which can guarantee the global optimality of the solution, a global optimization algorithm for solving the equivalent problem is proposed, which integrates the effective relaxation process and the branching process related to the outer approximation technique. Finally, the effectiveness and feasibility of the algorithm are illustrated by numerical experiments. [ABSTRACT FROM AUTHOR]

The single facility location problem in multiple regions with different norms (SMDN) generalizes the well-known Weber Problem. The SMDN consists of finding the optimum location of a single facility in the plane which is partitioned into multiple regions where the distance to travel in each region is measured or approximated with different norms. In this study, we specifically focus on the SMDN considering three regions with either rectilinear or Euclidean norms. We first introduce some analytical properties of this problem. Then, we devise a specially tailored branch-and-bound algorithm, i.e. a Big Square Small Square algorithm (BSSS), and two heuristics, named as Discrete Approximation algorithm (DA) and Modified Weiszfeld procedure (MW). The performance of the proposed approaches are tested using both standard test instances from the literature and randomly generated instances. According to our extensive computational experiments, the BSSS stands out to be a suitable exact solution approach in terms of both accuracy and efficiency when commercial mixed integer nonlinear solvers are not applicable. Besides, we also observe that the DA yields quite accurate solutions at the expense of high computation times while the MW arises to be the most efficient method with the least accuracy. [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.

The aim of this study was to explore the information disclosure (ID) problem, which involves selecting pairs of two sides before matching toward user-oriented optimization. This problem is known to be useful for mobility-on-demand (MoD) platforms because drivers' choice behaviors are appropriately modeled, but solving the problem is still under development, although heuristic solvers have been proposed. We develop new branch-and-bound-based (BnB) solvers and a new heuristic solver based on a quadratic unconstrained binary optimization (QUBO) formulation. Our numerical experiments show that the QUBO-based solver indeed works within the limit of available bits, and the BnB solver performs slightly better than existing heuristic ones.

We study the Sparse Plus Low-Rank decomposition problem (SLR), which is the problem of decomposing a corrupted data matrix into a sparse matrix of perturbations plus a low-rank matrix containing the ground truth. SLR is a fundamental problem in Operations Research and Machine Learning which arises in various applications, including data compression, latent semantic indexing, collaborative filtering, and medical imaging. We introduce a novel formulation for SLR that directly models its underlying discreteness. For this formulation, we develop an alternating minimization heuristic that computes high-quality solutions and a novel semidefinite relaxation that provides meaningful bounds for the solutions returned by our heuristic. We also develop a custom branch-and-bound algorithm that leverages our heuristic and convex relaxations to solve small instances of SLR to certifiable (near) optimality. Given an input n-by-n matrix, our heuristic scales to solve instances where n = 10000 in minutes, our relaxation scales to instances where n = 200 in hours, and our branch-and-bound algorithm scales to instances where n = 25 in minutes. Our numerical results demonstrate that our approach outperforms existing state-of-the-art approaches in terms of rank, sparsity, and mean-square error while maintaining a comparable runtime. [ABSTRACT FROM AUTHOR]

In this paper, linear multiplicative programs are approached with a branch-and-bound scheme and a detailed computational study is provided. Several underestimation functions are analyzed and various partitioning criteria are presented. A particular class of linear multiplicative programs, useful to solve some applicative bilevel problems, is considered from a theoretical point of view to emphasize an efficient solution method. Detailed results of the computational study are provided to point out the performances provided by using various underestimation functions and partitioning criteria, thus improving some of the results of the current literature. [ABSTRACT FROM AUTHOR]

A discrete network design problem (DNDP) is conventionally formulated as an analytical bi-level programming problem to acquire an optimal network design strategy for an existing traffic network. In recent years, multimodal network design problems have benefited from simulation-based models. The nonconvexity and implicity of bi-level DNDPs make it challenging to obtain an optimal solution, especially for simulation-related models. Bayesian optimization (BO) has been proven to be an effective method for optimizing the costly black-box functions of simulation-based continuous network design problems. However, there are only discrete inputs in DNDPs, which cannot be processed using standard BO algorithms. To address this issue, we develop a hybrid method (BO-B&B) that combines Bayesian optimization and a branch-and-bound algorithm to deal with discrete variables. The proposed algorithm exploits the advantages of the cutting-edge machine-learning parameter-tuning technique and the exact mathematical optimization method, thereby balancing efficiency and accuracy. Our experimental results show that the proposed method outperforms benchmarking discrete optimization heuristics for simulation-based DNDPs in terms of total computational time. Thus, BO-B&B can potentially aid decision makers in mapping practical network design schemes for large-scale networks. [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. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of scheduling chain-like structures of tasks on a single multiprocessor resource. In fact, sub-tasks of unit-time length and predefined size are aggregated to composite tasks that have to be scheduled without preemption, but subject to flexibility concerning resource allocation. This setting most closely resembles the problem of malleable task scheduling, with sub-tasks being the smallest atomic unit of allocation. The specific type of malleability is realized using precedence constraints with minimum and maximum time lags. A bin packing model is established for this scheduling problem and a corresponding, dedicated branch-and-bound algorithm is devised, alongside problem-specific bound tightening, symmetry breaking and dominance concepts. The efficacy of the solution approach is demonstrated based on extensive computational experiments, including randomized instances, adapted benchmark instances from the literature, and a small real-world data set. In comparison to mixed-integer and constraint programming formulations, the new method is able to achieve a considerably higher percentage of optimal solutions at computation times that are up to orders of magnitude smaller. [ABSTRACT FROM AUTHOR]

In this paper, we study a general class of two-level capacitated discrete location problems with concave costs. The concavity arises from the economies of scale in production, inventory, or handling at the facilities and from the consolidation of flows for transportation and transshipment on the links connecting the facilities. Given the discrete nature of the problem, it is naturally formulated as a mixed-integer nonlinear program that uses binary variables for locational decisions and continuous variables for routing flows. We present an alternative formulation that only uses continuous variables and discontinuous functions, resulting in a nonlinear program with a concave objective function. Our main goal is to computationally compare these two modeling approaches under the same solution framework. In particular, we present an exact branch-and-bound algorithm that uses (integer) linear relaxations of the proposed formulations to optimally solve large-scale instances. The algorithm is enhanced with a cost-dependent spatial branching strategy and preprocessing step to improve its convergence. Extensive computational experiments are performed to assess the performance of the exact algorithm. Based on real location data from 3,109 counties in the contiguous United States, we also present a sensitivity analysis to showcase the impact of considering concave costs in location and assignment decisions. [ABSTRACT FROM AUTHOR]

In this paper, we study resource allocation algorithm design for multi-user orthogonal frequency division multiple access (OFDMA) ultra-reliable low latency communication (URLLC) in mobile edge computing (MEC) systems. To meet the stringent end-to-end delay and reliability requirements of URLLC MEC systems, we employ joint uplink-downlink resource allocation and finite blocklength transmission. Furthermore, we propose a partial time overlap between the uplink and downlink frames to minimize the end-to-end delay, which introduces a new time causality constraint. The proposed resource allocation algorithm is formulated as an optimization problem for minimization of the total weighted power consumption of the network under a constraint on the number of URLLC user bits computed within the maximum allowable computation time, i.e., the end-to-end delay of a computation task of each user. Despite the non-convexity and the complicated structure of the formulated optimization problem, we develop a globally optimal solution using a branch-and-bound approach based on discrete monotonic optimization theory. The branch-and-bound algorithm minimizes an upper bound on the total power consumption until convergence to the globally optimal value. Furthermore, to strike a balance between computational complexity and performance, we propose two efficient suboptimal algorithms. For the first suboptimal scheme, the optimization problem is reformulated in the canonical form of difference of convex programming. Then, successive convex approximation (SCA) is used to determine a locally optimal solution. For the second suboptimal scheme, we use a high signal-to-noise ratio approximation for the channel dispersion. Then, via novel transformations, we convert the non-convex quality-of-service constraints of the original problem into equivalent second-order-cone constraints. Our simulation results reveal that the proposed resource allocation algorithm design facilitates URLLC in MEC systems, and yields significant power savings compared to three baseline schemes. Moreover, our simulation results show that the proposed suboptimal algorithms offer different trade-offs between performance and complexity and attain an excellent performance at comparatively low complexity.

This paper introduces an optimal algorithm for solving the discrete grid-based coverage path planning (CPP) problem. This problem consists in finding a path that covers a given region completely. First, we propose a CPP-solving baseline algorithm based on the iterative deepening depth-first search (ID-DFS) approach. Then, we introduce two branch-and-bound strategies (Loop detection and an Admissible heuristic function) to improve the results of our baseline algorithm. We evaluate the performance of our planner using six types of benchmark grids considered in this study: Coast-like, Random links, Random walk, Simple-shapes, Labyrinth and Wide-Labyrinth grids. We are first to consider these types of grids in the context of CPP. All of them find their practical applications in real-world CPP problems from a variety of fields. The obtained results suggest that the proposed branch-and-bound algorithm solves the problem optimally (i.e., the exact solution is found in each case) orders of magnitude faster than an exhaustive search CPP planner. To the best of our knowledge, no general CPP-solving exact algorithms, apart from an exhaustive search planner, have been proposed in the literature.

Community detection in complex networks has emerged as a fundamental research area during the last decade. Traditional community detection is primarily based on static techniques, which are neither practicable regarding limited resources nor appropriate for the evolving complex networks. Dynamically updating the community structures, getting accurate and real-time results are vital constraints for analyzing evolving networks, hence in our research, we take these possibilities into consideration. Our work proposes a novel community detection approach BBmst inspired by the original branch-and-bound (BB) concept for label propagation and a Minimum Spanning Tree (MST) to measure the dissimilarity between nodes in graphs. These proposed methods consist of four phases: finding of the local intrinsic density called core or granule of the community, label propagation with BB, an MST is employed to segregate the detected communities and finally a modularity-based community merging is performed. The performance of our proposed method is assessed against a few well-known community detectors on real-world social networks concerning various validity measures. Results demonstrated our proposed method superiority over current community detectors and showed a considerable trade-off between cluster accuracy and quality.

In this paper, we study a single-machine green scheduling problem with learning effects and past-sequence-dependent delivery times. The problem can be properly applied to tackle green manufacturing where production and delivery time are variable and highly subject to process-reengineering. Our goal is to determine the optimal sequence such that total weighted completion time and maximum tardiness are minimized. For the general case, we provide the analysis procedure of lower bound, and also propose the heuristic and branch-and-bound algorithms. Furthermore, computational experiments are conducted to demonstrate the effectiveness of our algorithms.

The performance of branch-and-bound algorithms for solving non-convex optimization problems greatly depends on convex relaxation techniques. They generate convex regions which are used for improving the bounds of variable domains. In particular, convex polyhedral regions can be represented by a linear system A.x=b. Then, bounds of variable domains can be improved by minimizing and maximizing variables in the linear system. Reducing or contracting optimally variable domains in linear systems, however, is an expensive task. It requires solving up to two linear programs for each variable (one for each variable bound). Suboptimal strategies, such as preconditioning, may offer satisfactory approximations of the optimal reduction at a lower cost. In non-square linear systems, a preconditioner P can be chosen such that P.A is close to a diagonal matrix. Thus, the projection of the equivalent system P.A.x=P.b over x, by using an iterative method such as Gauss–Seidel, can significantly improve the contraction. In this paper, we show how to generate an optimal preconditioner, i.e., a preconditioner that helps the Gauss–Seidel method to optimally reduce the variable domains. Despite the cost of generating the preconditioner, it can be re-used in sub-regions of the search space without losing too much effectiveness. Experimental results show that, when used for reducing domains in non-square linear systems, the approach is significantly more effective than Gauss-based elimination techniques. Finally, the approach also shows promising results when used as a component of a solver for non-convex optimization problems.

Estimating the pose of a calibrated camera relative to a 3D point set from one image is an important task in computer vision. Perspective-n-Point algorithms are often used if perfect 2D-3D correspondences are known. However, it is difficult to determine 2D-3D correspondences perfectly, and then the simultaneous pose and correspondence determination problem is needed to be solved. Early methods aimed to solve this problem by local optimization. Recently, several new methods are proposed to globally solve this problem by using branch-and-bound (BnB) method, but they tend to be slow because the time complexity of the BnB-based methods is exponential to the dimensionality of the parameter space, and they directly search the 6D parameter space. In this paper, we propose to decompose the joint searching into two separate searching processes by introducing a rotation invariant feature (RIF). Specifically, we construct RIFs from the original 3D and 2D point sets and search for the globally optimal translation to match these two RIFs first. Then, the original 3D point set is translated and matched with the 2D point set to find a globally optimal rotation. Experiments on challenging data show that the proposed method outperforms state-of-the-art methods in terms of both speed and accuracy. [ABSTRACT FROM AUTHOR]

Makespan minimization in permutation flow-shop scheduling is a well-known hard combinatorial optimization problem. Among the 120 standard benchmark instances proposed by E. Taillard in 1993, 23 have remained unsolved for almost three decades. In this paper, we present our attempts to solve these instances to optimality using parallel Branch-and-Bound (BB) on the GPU-accelerated Jean Zay supercomputer. We report the exact solution of 11 previously unsolved problem instances and improved upper bounds for eight instances. The solution of these problems requires both algorithmic improvements and leveraging the computing power of peta-scale high-performance computing platforms. The challenge consists in efficiently performing parallel depth-first traversal of a highly irregular and fine-grained search tree on distributed systems composed of hundreds of massively parallel accelerator devices and multicore processors. We present and discuss the design and implementation of our permutation-based BB and experimentally evaluate its parallel performance on up to 384 V100 GPUs (2 million CUDA cores) and 3840 CPU cores. The optimality proof for the largest solved instance requires about 64 CPU-years of computation—using 256 GPUs and over 4 million parallel search agents, the traversal of the search tree is completed in 13 hours, exploring 339 × 10 12 nodes. [ABSTRACT FROM AUTHOR]

Taking selfies has become one of the major photographic trends of our time. In this study, we focus on the selfie stick, on which a camera is mounted to take selfies. We observe that a camera on a selfie stick typically travels through a particular type of trajectory around a sphere. Based on this finding, we propose a robust, efficient, and optimal estimation method for relative camera pose between two images captured by a camera mounted on a selfie stick. We exploit the special geometric structure of camera motion constrained by a selfie stick and define this motion as spherical joint motion. Utilizing a novel parametrization and calibration scheme, we demonstrate that the pose estimation problem can be reduced to a 3-degrees of freedom (DoF) search problem, instead of a generic 6-DoF problem. This facilitates the derivation of an efficient branch-and-bound optimization method that guarantees a global optimal solution, even in the presence of outliers. Furthermore, as a simplified case of spherical joint motion, we introduce selfie motion, which has a fewer number of DoF than spherical joint motion. We validate the performance and guaranteed optimality of our method on both synthetic and real-world data. Additionally, we demonstrate the applicability of the proposed method for two applications: refocusing and stylization. [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]

To maximize the maintenance willingness of the owner of transmission lines, this study presents a transmission maintenance scheduling model that considers the energy constraints of the power system and the security constraints of on- site maintenance operations. Considering the computational complexity of the mixed integer programming (MIP) problem, a machine learning (ML) approach is presented to solve the transmission maintenance scheduling model efficiently. The value of the branching score factor value is optimized by Bayesian optimization (BO) in the proposed algorithm, which plays an important role in the size of the branch-and-bound search tree in the solution process. The test case in a modified version of the IEEE 30-bus system shows that the proposed algorithm can not only reach the optimal solution but also improve the computational efficiency.

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.

In classical schedule problems, the actual processing time of a job is a fixed constant, but in the actual production process, the processing time of a job is affected by a variety of factors, two of which are the learning effect and resource allocation. In this paper, single-machine scheduling problems with resource allocation and a time-dependent learning effect are investigated. The actual processing time of a job depends on the sum of normal processing times of previous jobs and the allocation of non-renewable resources. With the convex resource consumption function, the goal is to determine the optimal schedule and optimal resource allocation. Three problems arising from two criteria (i.e., the total resource consumption cost and the scheduling cost) are studied. For some special cases of the problems, we prove that they can be solved in polynomial time. More generally, we propose some accurate and intelligent algorithms to solve these problems.