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 consider a class of generalized linear multiplicative problems (GLMP), which have a wide range of applications and are known to be NP-hard. In this paper, we first transform it into an equivalent problem (EP) by introducing p new variables and applying logarithmic transformation. Secondly, in order to calculate the lower bound, we derived the linear relaxation problem (LRP) of EP by constructing a novel relaxation strategy. Additionally, a rectangular region reduction technique is proposed to accelerate the convergence speed of the algorithm. Based on the output-space search, we propose a new branch-and-bound algorithm for tackling the GLMP or EP. The global convergence of the algorithm is proved, and its computational complexity is analyzed to estimate the maximum number of iterations. Especially on the basis of LRP, we also propose another new convex relaxation based branch-and-bound algorithm for GLMP. Some experimental examples demonstrate the feasibility and effectiveness of these two algorithms. [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]

This paper proposes a general framework for solving multiobjective nonconvex optimization problems, i.e., optimization problems in which multiple objective functions have to be optimized simultaneously. Thereby, the nonconvexity might come from the objective or constraint functions, or from integrality conditions for some of the variables. In particular, multiobjective mixed-integer convex and nonconvex optimization problems are covered and form the motivation of our studies. The presented algorithm is based on a branch-and-bound method in the pre-image space, a technique which was already successfully applied for continuous nonconvex multiobjective optimization. However, extending this method to the mixed-integer setting is not straightforward, in particular with regard to convergence results. More precisely, new branching rules and lower bounding procedures are needed to obtain an algorithm that is practically applicable and convergent for multiobjective mixed-integer optimization problems. Corresponding results are a main contribution of this paper. What is more, for improving the performance of this new branch-and-bound method we enhance it with two types of cuts in the image space which are based on ideas from multiobjective mixed-integer convex optimization. Those combine continuous convex relaxations with adaptive cuts for the convex hull of the mixed-integer image set, derived from supporting hyperplanes to the relaxed sets. Based on the above ingredients, the paper provides a new multiobjective mixed-integer solver for convex problems with a stopping criterion purely in the image space. What is more, for the first time a solver for multiobjective mixed-integer nonconvex optimization is presented. We provide the results of numerical tests for the new algorithm. Where possible, we compare it with existing procedures. [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.

The following article presents and corroborates an outcome space branch-and-bound algorithm for solving the general linear multiplicative programming problem (GLMPP). In this new algorithm, GLMPP is transformed into its equivalent problem by introducing auxiliary variables. To compute the tight upper bound for the optimal value of GLMPP, the linear relaxation programming problem is assembled by using bound and hull linear approximations. Furthermore, the global convergence and computational complexity of the algorithm are demonstrated. Finally, the soundness and advantage of the proposed algorithm are validated by solving a demonstrative linear multiplicative problem. [ABSTRACT FROM AUTHOR]

In this study, we investigate a class of linear multiplicative programs with positive exponents. By introducing p additional variables, the original problem is reformulated into an equivalent problem (EP) within the output space. Subsequently, a novel global optimization algorithm is introduced to tackle EP. The algorithm primarily leverages two key techniques. One is the outer approximation technique, which tightens the relaxed feasible region of EP and improves the upper bound by carefully examining suitable feasible points. The other is the branch and bound technique to guarantee the global optimality of the solution. Numerical results confirm the effectiveness and practicality of the proposed algorithm, thereby underscoring its potential for real-world applications. [ABSTRACT FROM AUTHOR]

This article presents a self-adjustable branch-and-bound algorithm for globally solving a class of linear multiplicative programming problems (LMP). In this algorithm, a self-adjustable branching rule is introduced and it can continuously update the upper bound for the optimal value of LMP by selecting suitable branching point under certain conditions, which differs from the standard bisection rule. The proposed algorithm further integrates the linear relaxation program and the self-adjustable branching rule. The dependability and robustness of the proposed algorithm are demonstrated by establishing the global convergence. Furthermore, the computational complexity of the proposed algorithm is estimated. Finally, numerical results validate the effectiveness of the self-adjustable branching rule and demonstrate the feasibility of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We study the Compressed Sensing (CS) problem, which is the problem of finding the most sparse vector that satisfies a set of linear measurements up to some numerical tolerance. CS is a central problem in Statistics, Operations Research and Machine Learning which arises in applications such as signal processing, data compression, image reconstruction, and multi-label learning. We introduce an ℓ 2 regularized formulation of CS which we reformulate as a mixed integer second order cone program. We derive a second order cone relaxation of this problem and show that under mild conditions on the regularization parameter, the resulting relaxation is equivalent to the well studied basis pursuit denoising problem. We present a semidefinite relaxation that strengthens the second order cone relaxation and develop a custom branch-and-bound algorithm that leverages our second order cone relaxation to solve small-scale instances of CS to certifiable optimality. When compared against solutions produced by three state of the art benchmark methods on synthetic data, our numerical results show that our approach produces solutions that are on average 6.22 % more sparse. When compared only against the experiment-wise best performing benchmark method on synthetic data, our approach produces solutions that are on average 3.10 % more sparse. On real world ECG data, for a given ℓ 2 reconstruction error our approach produces solutions that are on average 9.95 % more sparse than benchmark methods ( 3.88 % more sparse if only compared against the best performing benchmark), while for a given sparsity level our approach produces solutions that have on average 10.77 % lower reconstruction error than benchmark methods ( 1.42 % lower error if only compared against the best performing benchmark). When used as a component of a multi-label classification algorithm, our approach achieves greater classification accuracy than benchmark compressed sensing methods. This improved accuracy comes at the cost of an increase in computation time by several orders of magnitude. Thus, for applications where runtime is not of critical importance, leveraging integer optimization can yield sparser and lower error solutions to CS than existing benchmarks. [ABSTRACT FROM AUTHOR]

In this paper, we study the m-machine ( m ≥ 3 ) permutation flow shop scheduling in which the processing time of a job depends not only on the sum of actual processing times of previous jobs but also on its job-dependent truncation parameter, i.e., the general truncated learning effects. The goal is to find a sequence so as to minimize the makespan, we prove that this problem is NP-hard. Two simple heuristics are proposed and their worst-case bounds are presented. We also propose a branch-and-bound algorithm and some heuristics to solve this problem. Further, computational experiments are conducted to determine the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

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.)

Copyright of Journal of Cryptologic Research (2097-4116) is the property of Editorial Board of Journal of Cryptologic Research 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]

This paper discusses the single-machine scheduling problems with deteriorating jobs and past-sequence-dependent delivery times. Under the general deterioration function, the objective is to determine an optimal schedule for the job that minimizes the makespan, and the total weighted completion time. We demonstrate that the makespan minimization is polynomially solvable. For the total weighted completion time, this problem is NP-hard, to solve this problem, we provide the branch-and-bound algorithm and some heuristic algorithms. [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]

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]

Smoothing the workloads among the stations of an already installed assembly line is one of the major objectives in assembly line (re-)balancing. In order to find a feasible task-station assignment that distributes the total workload as equal as possible, two exact task-oriented branch-and-bound algorithms have recently been proposed. In this paper, we systematically analyse their effectiveness in solving the workload smoothing problem on simple assembly lines. In our experiments, we also examine the performance of a state-of-the-art mathematical programming solver and a 'combined' exact branch-and-bound procedure that integrates components of the two algorithms from the literature. In terms of theory, we show the equivalence of two recently developed local lower bounding arguments and suggest a slight improvement of the bound. We also propose an enhanced feasibility test. [ABSTRACT FROM AUTHOR]

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.

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]

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]

Sparse optimization–fitting data with a low-cardinality linear model–is addressed through the minimization of a cardinality-penalized least-squares function, for which dedicated branch-and-bound algorithms clearly outperform generic mixed-integer-programming solvers. Three acceleration techniques are proposed for such algorithms. Convex relaxation problems at each node are addressed with dual approaches, which can early prune suboptimal nodes. Screening methods are implemented, which fix variables to their optimal value during the node evaluation, reducing the subproblem size. Numerical experiments show that the efficiency of such techniques depends on the node cardinality and on the structure of the problem matrix. Last, different exploration strategies are proposed to schedule the nodes. Best-first search is shown to outperform the standard depth-first search used in the related literature. A new strategy is proposed which first explores the nodes with the lowest least-squares value, which is shown to be the best at finding the optimal solution–without proving its optimality. A C++ solver with compiling and usage instructions is made available. [ABSTRACT FROM AUTHOR]

Inspired by the recently introduced branch-and-bound method for continuous multiobjective optimization problems from G. Eichfelder, P. Kirst, L. Meng, O. Stein [A general branch-and-bound framework for continuous global multiobjective optimization. J Glob Optim. 2021;80:195–227], we study for a general class of branch-and-bound methods in which sense the generated terminal enclosure and the terminal provisional nondominated set approximate the nondominated set when the termination accuracy is driven to zero. Our convergence analysis of the enclosures relies on constructions from the above paper, but is self-contained and also covers the mixed-integer case. The analysis for the provisional nondominated set is based on general convergence properties of the epsilon-nondominated set, and hence it is also applicable to other algorithms which generate such points. Furthermore, we discuss post-processing steps for the terminal enclosure and provide numerical illustrations for the cases of two and three objective functions. [ABSTRACT FROM AUTHOR]

For a single matrix (operator) it is well-known that the spectral gap is an important quantity, as well as its estimate and computation. Here we consider, for the first time in the literature, the computation of its extension to a finite family of matrices, in other words the difference between the joint spectral radius (in short JSR, which we call here the first Lyapunov exponent) and the second Lyapunov exponent (denoted as SLE). The knowledge of joint spectral characteristics and of the spectral gap of a family of matrices is important in several applications, as in the analysis of the regularity of wavelets, multiplicative matrix semigroups and the convergence speed in consensus algorithms. As far as we know the methods we propose are the first able to compute this quantity to any given accuracy. For computation of the spectral gap one needs first to compute the JSR. A popular tool that is used to this purpose is the invariant polytope algorithm, which relies on the finiteness property of the family of matrices, when this holds true. In this paper we show that the SLE may not possess the finiteness property, although it can be efficiently approximated with an arbitrary precision. The corresponding algorithm and two effective estimates are presented. Moreover, we prove that the SLE possesses a weak finiteness property, whenever the leading eigenvalue of the dominant product is real. This allows us to find in certain situations the precise value of the SLE. Numerical results are demonstrated along with applications in the theory of multiplicative matrix semigroups and in the wavelets theory. [ABSTRACT FROM AUTHOR]

We investigate the optimal portfolio deleveraging (OPD) problem with permanent and temporary price impacts, where the objective is to maximize equity while meeting a prescribed debt/equity requirement. We take the real situation with cross impact among different assets into consideration. The resulting problem is, however, a nonconvex quadratic program with a quadratic constraint and a box constraint, which is known to be NP‐hard. In this paper, we first develop a successive convex optimization (SCO) approach for solving the OPD problem and show that the SCO algorithm converges to a KKT point of its transformed problem. Second, we propose an effective global algorithm for the OPD problem, which integrates the SCO method, simple convex relaxation, and a branch‐and‐bound framework, to identify a global optimal solution to the OPD problem within a prespecified ε‐tolerance. We establish the global convergence of our algorithm and estimate its complexity. We also conduct numerical experiments to demonstrate the effectiveness of our proposed algorithms with both real data and randomly generated medium‐ and large‐scale OPD instances. [ABSTRACT FROM AUTHOR]

Delimited control is a powerful mechanism for programming language extension which has been recently proposed for Prolog (and implemented in SWI-Prolog). By manipulating the control flow of a program from inside the language, it enables the implementation of powerful features, such as tabling, without modifying the internals of the Prolog engine. However, its current formulation is inadequate: it does not capture Prolog's unique non-deterministic nature which allows multiple ways to satisfy a goal. This paper fully embraces Prolog's non-determinism with a novel interface for disjunctive delimited control, which gives the programmer not only control over the sequential (conjunctive) control flow, but also over the non-deterministic control flow. We provide a meta-interpreter that conservatively extends Prolog with delimited control and show that it enables a range of typical Prolog features and extensions, now at the library level: findall, cut, branch-and-bound optimisation, probabilistic programming. [ABSTRACT FROM AUTHOR]

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]

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.