Search

This paper studies a due-window assignment scheduling problem with deterioration effects on a single-machine. Under different due-window assignment, i.e., the due-window of a job without any restriction, our goal is to make a decision on the optimal due-window and sequence of all jobs to minimize the weighted sum of earliness and tardiness, number of early and delayed, due-window starting time and size. We present properties of the optimal solutions, for some special cases, we prove that the problem can be solved in polynomial time. For the general case, we present a lower bound and an upper bound (i.e., a heuristic algorithm), then a branch-and-bound algorithm is proposed. [ABSTRACT FROM AUTHOR]

With the rapid development of Internet and the application of smart phone, the percentage of people who choose self-guide tour increased significantly. Also, with the expectation of reaching 57 billion smart connected devices by 2025, the application of Internet of Things (IoT) has spread widely. Using IoT technology to support the development of recommender system has become a widely studied topic. To elevate the quality of self-guided tours and reduce the time costs associated with arranging them, this paper proposes a system that recommends self-guided tour services according to users' personal preferences and professionals' travel recommendations in the IoT environment. This system automatically generates travel itineraries after users input some basic information. Prior to generating itineraries, this system references travel itinerary recommendations retrieved from a travel itinerary database (developed by professionals) as well as users' personal preferences and trip constraints. Next, it produces travel itinerary recommendations. Users can modify the travel itinerary recommendations of the proposed system according to their individual needs, and this system uses the branch-and-bound algorithm to assemble modified points of interest to produce optimal travel itineraries. [ABSTRACT FROM AUTHOR]

This paper studies the single-machine scheduling problem with truncated learning effect, time-dependent processing time, and past-sequence-dependent delivery time. The delivery time is the time that the job is delivered to the customer after processing is complete. The goal is to determine an optimal job schedule to minimize the total weighted completion time and maximum tardiness. In order to solve the general situation of the problem, we propose a branch-and-bound algorithm and other heuristic algorithms. Computational experiments also prove the effectiveness of the given algorithms. [ABSTRACT FROM AUTHOR]

We study a class of chance constrained programs (CCPs) where the underlying distribution is modeled by a Gaussian mixture model. As the original work, Hu et al. (IISE Trans 54(12):1117–1130, 2022. https://doi.org/10.1080/24725854.2021.2001608) developed a spatial branch-and-bound (B &B) algorithm to solve the problems. In this paper, we propose an enhanced procedure to speed up the computation of B &B algorithm. We design an enhanced pruning strategy that explores high-potential domains and an augmented branching strategy that prevents redundant computations. We integrate the new strategies into original framework to develop an enhanced B &B algorithm, and illustrate how the enhanced algorithm improves on the original approach. Furthermore, we extend the enhanced B &B framework to handle the CCPs with multiple chance constraints, which is not considered in the previous work. We evaluate the performance of our new algorithm through extensive numerical experiments and apply it to solve a real-world portfolio selection problem. [ABSTRACT FROM AUTHOR]

This paper incorporates the shortest passenger travel paths into the first train timetabling problem in urban rail transit networks. We first propose a path-based first train timetabling problem, which is formulated as a mixed-integer nonlinear programming model to reduce the travel time for passengers. To solve this model, we present a tailored branch-and-bound combined with the timetable-based Dijkstra algorithm. To further enhance the efficiency of the exact algorithm, we design a rolling time heuristic algorithm as a substitute for the branch-and-bound algorithm. Then, we proved that the rolling time heuristic combined with the timetable-based Dijkstra algorithm achieves 97.86% and 99.39% reductions in CPU time while sacrificing only 0.007% and 0.057% of optimality gap by two numerical experiments. Finally, the results based on two test networks with different structures demonstrate that the path-based first train timetabling model effectively improves passenger travel efficiency. Specifically, the travel times are reduced by 744 mins and 761 mins, while the transfer waiting times are reduced by 37.87% and 58.91% compared to the existing timetables. Moreover, the results also demonstrate that loop line networks will increase the difficulty of timetabling and lead to many passengers taking detours. To further enhance the efficiency of commuting for passengers who take the first train, URT operators may consider relaxing the limitations on the departure time of the depot stations. • A path-based first train timetabling model to minimize the total travel time in urban rail transit networks. • A tailored branch-and-bound combined with a timetable-based Dijkstra algorithm. • A rolling time heuristic algorithm to solve large-scale networks cases. [ABSTRACT FROM AUTHOR]

This paper deals with a single-machine scheduling problem with a general linear deterioration effect. The goal is to determine the job schedule such that the total weighted number of late jobs is minimized. We present three properties, one heuristic algorithm and a lower bound to speed up the search process of the branch-and-bound algorithm. In addition, some complex heuristics (including tabu search and simulated annealing algorithms) are proposed as solutions to this problem. The computational results show that the proposed algorithms are effective and efficient. [ABSTRACT FROM AUTHOR]

This paper studies the single machine scheduling problems with truncated logarithm processing times and exponential past-sequence-dependent delivery times. We prove that the makespan and total completion time minimizations are polynomially solvable. For the total weighted completion time minimization, we illustrate that it remains polynomially solvable under a special case; under the general case, this paper proposes heuristic, tabu search and branch-and-bound algorithms. Computational experiments indicate that the heuristic algorithm is more effective than tabu search algorithm. [ABSTRACT FROM AUTHOR]

This paper investigates a widely discussed class of charging station location problems for the en-route charging need of electric vehicles traveling in intercity highway networks. Due to the necessity for multiple charges along an intercity long-haul trip, this type of charging station location problems implies such an individual behavior that electric vehicle drivers make self-optimal route-and-charge decisions while ensuring the driving range of their vehicles to sustain trips without running out of charge. The main contribution of this paper is on analytically and computationally comparing the modeling and solution methods for the charging station location problems within uncongested and congested networks. Two distinct modeling frameworks are presented and analyzed: A metanetwork-based two-stage model for uncongested networks and a network-based bi-level model for congested networks. Both models are tackled by the classic branch-and-bound algorithm, which, however, resorts to different problem decomposition schemes, subregion bounding strategies, and network flow evaluation methods. Specifically, for uncongested networks, a two-phase procedure first employs a bi-criterion label-correcting algorithm for constructing a metanetwork and then implements the branch-and-bound algorithm on the metanetwork embedding a single-criterion label-setting algorithm for deriving network flows; on the other hand, for congested networks, the branch-and-bound algorithm is directly applied on the original network encapsulating a convex combinations method for deriving network flows. Finally, the two network scenarios and their modeling and solution methods are quantitatively evaluated with two real-world highway networks, in terms of implementation complexity, solution efficiency, and routing behavior.

To balance customer satisfaction across virtual and real-world interactions, we focus on enhancing service for dine-in customers at restaurants that typically prioritize online orders, such as those on Uber Eats. Utilizing three-agent scheduling strategies that adhere to each agent’s specific requirements—whether they are hard constraints or soft objectives—we effectively manage various types of orders, including immediate individual online orders, group reservations, and oral requests from dine-in customers. This approach significantly reduces waiting times and improves overall customer satisfaction. We propose a branch-and-bound algorithm with a tight lower bound based on preemption, which prioritizes agents A and B while reducing the total waiting time for agent C, representing dine-in customers. Computational experiments reveal that our algorithm significantly reduces total waiting times compared to existing two-agent scheduling strategies, demonstrating its effectiveness. Despite its efficiency, the algorithm incurs computational overheads, particularly with larger problem sizes. Our unique lower bound can be extended to other industries requiring multiple constraints or objectives. For example, in the film and television industry, real actors (represented by agent A) need to align their shooting times with 3D studios (represented by agent B) and stunt doubles for virtual avatars (represented by agent C) for scenes where they interact. That is, more agents are required to accommodate their constraints and objectives in such a scenario.

The issue of counting independent sets of a graph, G, represented as i (G) , is a significant challenge within combinatorial mathematics. This problem finds practical applications across various fields, including mathematics, computer science, physics, and chemistry. In chemistry, i (G) is recognized as the Merrifield–Simmons (M-S) index for molecular graphs, which is one of the most relevant topological indices related to the boiling point in chemical compounds. This article introduces an innovative algorithm designed for tallying independent sets within grid-like structures. The proposed algorithm is based on the 'branch-and-bound' technique and is applied to compute i (G m , n) for a square grid formed by m rows and n columns. The proposed approach incorporates the widely recognized vertex reduction rule as the basis for splitting the current subgraph. The methodology involves breaking down the initial grid iteratively until outerplanar graphs are achieved, serving as the 'basic cases' linked to the leaf nodes of the computation tree or when no neighborhood is incident to a minimum of five rectangular internal faces. The time complexity of the branch-and-bound algorithm speeds up the computation of i (G m , n) compared to traditional methods, like the transfer matrix method. Furthermore, the scope of the proposed algorithm is more general than the algorithms focused on grids since it could be applied to process general mesh graphs. [ABSTRACT FROM AUTHOR]

This paper studies the single-machine scheduling problem with truncated learning effect, time-dependent processing time, and past-sequence-dependent delivery time. The delivery time is the time that the job is delivered to the customer after processing is complete. The goal is to determine an optimal job schedule to minimize the total weighted completion time and maximum tardiness. In order to solve the general situation of the problem, we propose a branch-and-bound algorithm and other heuristic algorithms. Computational experiments also prove the effectiveness of the given algorithms.

Capacitated vehicle routing problem (CVRP) is a classical combinatorial optimization problem in which a network of customers with specified demands is given. The objective is to find a set of routes which originates as well as terminates at the depot node. These routes are to be traversed in such a way that the demands of all the customers in the network are satisfied and the cost associated with traversal of these routes come out to be a minimum. In real-world situations, the demand of any commodity depends upon various uncontrollable factors, such as season, delivery time, and market conditions. Due to these factors, the demand can always not be told in advance and a precise information about the demand is nearly impossible to achieve. Hence, the demands of the customers always experience impreciseness and randomness in real life. The decisions made by the customers about the demands may also have some scope of hesitation as well. In order to handle such demands of customers in the network, fuzzy random variables and intuitionistic fuzzy random variables are used in this work. The work bridges the gap between the classical version of CVRP and the real-life situation and hence makes it easier for the logistic management companies to determine the routes that should be followed for minimum operational cost and maximum profit. Mathematical models corresponding to CVRP with fuzzy stochastic demands (CVRPFSD) and CVRP with intuitionistic fuzzy stochastic demands (CVRPIFSD) have been presented. A two-stage model has been proposed to find out the solution for the same. To explain the working of the methodology defined in this work, different examples of networks with fuzzy and intuitionistic fuzzy demands have been worked out. The proposed solution approach is also tested on modified fuzzy stochastic versions of some benchmark instances. [ABSTRACT FROM AUTHOR]

We consider the scheduling problem on unrelated parallel machines in order to minimize the total late work. Since the problem is NP-hard, we propose a mathematical model and two dedicated exact approaches for solving it, based on the branching and bounding strategy and on enumerating combined with a dynamic programming algorithm. The time efficiencies of all three approaches are evaluated through computational experiments.

In this paper, we study the problem of (p , q )-biclique counting and enumeration for large sparse bipartite graphs. Given a bipartite graph G = (U , V , E) and two integer parameters p and q, we aim to efficiently count and enumerate all (p , q )-bicliques in G, where a (p , q )-biclique B(L, R) is a complete subgraph of G with L ⊆ U , R ⊆ V , | L | = p , and | R | = q . The problem of (p , q )-biclique counting and enumeration has many applications, such as graph neural network information aggregation, densest subgraph detection, and cohesive subgroup analysis. Despite the wide range of applications, to the best of our knowledge, we note that there is no efficient and scalable solution to this problem in the literature. This problem is computationally challenging, due to the worst-case exponential number of (p , q )-bicliques. In this paper, we propose a competitive branch-and-bound baseline method, namely BCList, which explores the search space in a depth-first manner, together with a variety of pruning techniques. Although BCList offers a useful computation framework to our problem, its worst-case time complexity is exponential to p + q . To alleviate this, we propose an advanced approach, called BCList++. Particularly, BCList++ applies a layer-based exploring strategy to enumerate (p , q )-bicliques by anchoring the search on either U or V only, which has a worst-case time complexity exponential to either p or q only. Consequently, a vital task is to choose a layer with the least computation cost. To this end, we develop a cost model, which is built upon an unbiased estimator for the density of 2-hop graph induced by U or V. To improve computation efficiency, BCList++ exploits pre-allocated arrays and vertex labeling techniques such that the frequent subgraph creating operations can be substituted by array element switching operations. We conduct extensive experiments on 16 real-life datasets, and the experimental results demonstrate that BCList++ significantly outperforms the baseline methods by up to 3 orders of magnitude. We show via a case study that (p , q )-bicliques optimizes the efficiency of graph neural networks. In this paper, we extend our techniques to count and enumerate (p , q )-bicliques on uncertain bipartite graphs. An efficient method IUBCList is developed on the top of BCList++, together with a couple of pruning techniques, including common neighbor refinement and search branch early termination, to discard unpromising uncertain (p , q )-bicliques early. The experimental results demonstrate that IUBCList significantly outperforms the baseline method by up to 2 orders of magnitude. [ABSTRACT FROM AUTHOR]

The indefinite separable quadratic knapsack problem (ISQKP) with box constraints is known to be NP-hard. In this paper, we propose a new branch-and-bound algorithm based on a convex envelope relaxation that can be efficiently solved by exploiting its special dual structure. Benefiting from a new branching strategy, the complexity of the proposed algorithm is quadratic in terms of the number of variables when the number of negative eigenvalues in the objective function of ISQKP is fixed. We then improve the proposed algorithm for the case that ISQKP has symmetric structures. The improvement is achieved by constructing tight convex relaxations based on the aggregate functions. Numerical experiments on large-size instances show that the proposed algorithm is much faster than Gurobi and CPLEX. It turns out that the proposed algorithm can solve the instances of size up to three million in less than twenty seconds on average and its improved version is still very efficient for problems with symmetric structures. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is a problem in computer science that has been extensively studied and has a wide variety of real-world applications. It is considered an NP-hard issue since the only way to get a precise solution to it is to wait an exponentially long amount of time unless P=NP. Both accurate and heuristic algorithms exist to tackle this problem. The Branchand-Bound algorithm (BnB) is often regarded as the most significant precise approach, despite the fact that it traverses, in the worst scenario, all potential tours in order to calculate the tour efficiently. This study proposed an efficient parallel algorithm to solve TSP by using a cluster multicore system. An exact algorithm will be used to get the optimal solution, and to expedite the search for the best path, we have employed a multi-threaded approach that capitalizes on the processing power of multiple CPU cores to concurrently process subproblems. [ABSTRACT FROM AUTHOR]

The short interval between the collecting and distribution of zakat al-fitr is a recurring issue. As a result, ‘amil does not always pay attention to the ideal route, leading in inefficient transportation expenditures. This study aims to minimize the amount of vehicle mileage that affects fuel consumption. The branch-and-bound algorithm was employed to overcome the distribution route optimization problem by proposing the shortest circuit that traverses each district exactly once and returns to its original district. The procedures involve data collecting, graph analysis, branch-and-bound analysis, MATLAB code development, and the recommendation of the best route. The results indicate that the branch-and-bound algorithm can numerically solve the distribution route optimization corresponding to traveling salesman problem. Furthermore, according to a case study of zakat al-fitr distribution conducted by Eradication of Illiteracy Al Quran (PBHA), the total optimal distance of the computational-based algorithm was 152.9 km, with inter-village routes starting from Sidorejo and then via Sumberarum, Pendoworejo, Gerbosari, Banjaroyo, Banjarasri, Sendangagung, Tuksono, Argodadi, Triwidadi, Jatimulyo, Giripurwo, and ends in Sidorejo.

This paper presents an effective algorithm for globally solving the sum of linear ratios problem (SLRP), which has broad applications in government planning, finance and investment, cluster analysis, game theory and so on. In this paper, by using a new linearization technique, the linear relaxation problem of the equivalent problem is constructed. Next, based on the linear relaxation problem and the branch-and-bound framework, an effective branch-and-bound algorithm for globally solving the problem (SLRP) is proposed. By analyzing the computational complexity of the proposed algorithm, the maximum number of iterations of the algorithm is derived. Numerical experiments are reported to verify the effectiveness and feasibility of the proposed algorithm. Finally, two practical application problems from power transportation and production planning are solved to verify the feasibility of the algorithm. [ABSTRACT FROM AUTHOR]

The Close-Enough Traveling Salesman Problem is a generalization of the Traveling Salesman Problem that requires a salesman to just get close enough to each customer instead of visiting the exact location of each customer. In this paper, we propose improvements to an existing branch-and-bound (B &B) algorithm for this problem that finds and proves optimality of solutions by examining partial sequences. The proposed improvements include a new search strategy, a simplified branching vertex selection scheme, a method to avoid unnecessary computation, a method to improve the quality of feasible solutions, and a method to reduce the space requirement of the algorithm. Numerical experiments show that the improved B &B algorithm proves optimality faster on some instances, finds good feasible solutions faster than the best known existing algorithm on instances that cannot be solved to optimality, and uses less space during the solving process. [ABSTRACT FROM AUTHOR]

This paper investigates the single-machine resource allocation scheduling problem with learning effects and group technology. The objective is to determine the optimal job and group schedules, and resource allocations such that total completion time is minimized subject to limited resource availability. For some special cases, we show that the problem remains polynomially solvable. For general case of the problem, we propose the heuristic algorithm, tabu search algorithm and branch-and-bound algorithm. Numerical experiments are tested to evaluate the performance of the heuristic and branch-and-bound algorithms. [ABSTRACT FROM AUTHOR]

The singly linearly constrained separable binary quadratic programming problem (SLSBQP) has a wide variety of applications in practice. In real-life applications, the coefficients in the objective function and constraints generally appear with symmetric structure. In this paper, we propose an extremely efficient global optimization algorithm for solving SLSBQP with symmetric structure. We first develop a reformulation of SLSBQP based on an aggregate function defined on the symmetric structure in the problem, and derive the convex envelop function for the aggregate function. A branch-and-bound algorithm is then proposed to find the global solution of the reformulation of SLSBQP. Computational experiments show that the proposed algorithm is able to solve test instances with thousands of variables in less than 0.04 seconds on average, whereas the current state-of-the-art algorithms may fail to solve the same test instances in 200 seconds. The superior performance of the proposed algorithm clearly indicates the potential of the proposed algorithm in real-life applications. [ABSTRACT FROM AUTHOR]

We consider the scheduling problem on unrelated parallel machines in order to minimize the total late work. Since the problem is NP-hard, we propose a mathematical model and two dedicated exact approaches for solving it, based on the branching and bounding strategy and on enumerating combined with a dynamic programming algorithm. The time efficiencies of all three approaches are evaluated through computational experiments. [ABSTRACT FROM AUTHOR]

The issue of counting independent sets of a graph, G, represented as i(G), is a significant challenge within combinatorial mathematics. This problem finds practical applications across various fields, including mathematics, computer science, physics, and chemistry. In chemistry, i(G) is recognized as the Merrifield–Simmons (M-S) index for molecular graphs, which is one of the most relevant topological indices related to the boiling point in chemical compounds. This article introduces an innovative algorithm designed for tallying independent sets within grid-like structures. The proposed algorithm is based on the ‘branch-and-bound’ technique and is applied to compute i(Gm,n) for a square grid formed by m rows and n columns. The proposed approach incorporates the widely recognized vertex reduction rule as the basis for splitting the current subgraph. The methodology involves breaking down the initial grid iteratively until outerplanar graphs are achieved, serving as the ’basic cases’ linked to the leaf nodes of the computation tree or when no neighborhood is incident to a minimum of five rectangular internal faces. The time complexity of the branch-and-bound algorithm speeds up the computation of i(Gm,n) compared to traditional methods, like the transfer matrix method. Furthermore, the scope of the proposed algorithm is more general than the algorithms focused on grids since it could be applied to process general mesh graphs.

The branch-and-bound method is an exact tree search method in mixed integer linear programming. Recently, learning branching policies become a popular topic, but most existing machine learning methods only consider problems with similar structures, and pay little attention to heterogeneous problems. The parameterized search tree method demonstrates promising performance on heterogeneous problems, but there is still room for improvement when it generalizes to other problems. In this paper, we propose an attention-based branching framework, which can exploit information among candidate variables. In this way, we can take full advantage of the properties exploited from the parameterized branch-and-bound search tree, resulting in a better branching policy. Our proposed model is evaluated on multiple mixed integer linear programming instances and attains remarkable performance within a given time limit. [ABSTRACT FROM AUTHOR]

Today, the development of a modern video game draws upon multiple areas of expertise. Moreover, its development cost could be as high as tens of millions of dollars. Consequently, we should carefully schedule its jobs so as not to increase the total cost. However, project leaders traditionally treat developers alike or even schedule all the jobs manually. In this study, we consider a versatile-developer scheduling problem. The objective is to minimize the makespan of a game project. We propose a branch-and-bound algorithm (B&B) to generate the optimal schedules for small problem instances. On the other hand, an imperialist competitive algorithm (ICA) is proposed to obtain approximate schedules for large problem instances. Lastly, computational experiments are conducted to show the performances of both algorithms. When the problem size is small (e.g., n ≤ 12), B&B can generate the optimal schedules within 5 s. For some large problem instances (e.g., n = 600), near-optimal schedules can be obtained by ICA within 10 min. The final results imply that both algorithms converge quickly and are of high solution quality. [ABSTRACT FROM AUTHOR]

A graph is said to be a pairwise compatibility graph (PCG) if there exists an edge-weighted tree whose leaf set is the graph's vertex set, and there exists an edge between two vertices in the graph if and only if the distance between them in the tree lies within a given interval. It is a challenging task to enumerate all non-PCGs that are minimal in the sense that each of their induced subgraphs is a PCG and deliver proof of this fact. First, it involves a large number of combinatorial decisions concerning the structure of a tree and leaf-vertex correspondence. Moreover, there exists an infinite continuous domain for the edge weights even for a fixed tree. We handle the combinatorial problem by first screening graphs that are PCGs using a heuristic PCG generator. Then, we construct "configurations" that show some graphs to be PCGs. Finally, we generate configurations without including those that cannot be used to show that a given graph is a PCG. In order to construct finite-sized evidence to a graph being a minimal non-PCG in the face of an infinite search space, we use linear programming (LP) formulations whose solutions serve as evidence. To demonstrate our approach, we enumerated all minimal non-PCGs with nine vertices, which were unknown. We prove that there are exactly 1494 minimal non-PCGs with nine vertices and provide evidence for each of them. [ABSTRACT FROM AUTHOR]

The single-period unit commitment problem has significant applications in electricity markets. An efficient global algorithm not only provides the optimal schedule that achieves the lowest cost, but also plays an important role for deriving the market-clearing price. As of today, the problem is mainly solved by using a general-purpose mixed-integer quadratic programming solver such as CPLEX or Gurobi. This paper proposes an extremely efficient global optimization algorithm for solving the problem. We propose a conjugate function based convex relaxation and design a special dual algorithm to compute a tight lower bound of the problem in O (n log n) complexity. Then, a branch-and-bound algorithm is designed for finding a global solution to the problem. Computational experiments show that the proposed algorithm solves test instances with 500 integer variables in less than 0.01 s, whereas current state-of-the-art solvers fail to solve the same test instances in one hour. This superior performance of the proposed algorithm clearly indicates its potential in day-ahead and real-time electricity markets. [ABSTRACT FROM AUTHOR]

Due to the upward trend in the aviation industry, the existing approaches for air traffic control need to be improved to achieve efficient schedules. This paper deals with the aircraft landing problem, which consists of determining a landing time for each aircraft within the radar range of an airport and allocating it to a runway. We propose an exact solution approach that involves mixed-integer linear programming. The objective is hereby to minimize the sum of weighted deviations from the target landing times under consideration of different safety, efficiency and fairness constraints. Despite of the problem’s NP-hardness, our method exhibits low execution times thanks to a modified modeling strategy and provides near-optimal results. Numerical experiments prove efficiency of the approach for different large airports.

This paper proposes a novel quadratic convex reformulation (QCR) for the nonconvex quadratic program with convex quadratic constraints. This new QCR is based on the technique of simultaneous diagonalization which has become one of the hottest tools in the area of quadratic programming. We first demonstrate that the 'best' QCR can be achieved by solving a Shor relaxation of the original problem. Then, we design a branch-and-bound algorithm based on the proposed QCR for obtaining the global optimal solution. Numerical experiments with extended Celis–Dennis–Tapia problem and optimal spectrum sharing problem are conducted to show that our proposed QCR well balances the bound quality and computing efficiency, hence it is very competitive with two state-of-the-art QCRs when they are executed by the same branch-and-bound scheme. [ABSTRACT FROM AUTHOR]

This research studies a production-recycling inventory model for postconsumer recycled content products made from a mix of virgin and recycled materials with specific proportions. The proportion is known as the postconsumer recycled content level. We study a closed-loop supply chain (CLSC) where a recycling facility and a supplier respectively ship the recycled and virgin raw materials to a manufacturer. The manufacturer mixes them based on the proportion to produce these products for a retailer. The recycling facility recycles the used products collected by a material recovery facility. The paper develops a joint economic lot-size model (JELS) to maximize the chain-wide total profit. A branch-and-bound algorithm is developed, along with the convex analysis to find the exact solution. To coordinate the CLSC, we present models called disproportionate profit-sharing (DPS) and proportional profit-sharing (PPS) operating under quantity discount. The DPS would give more powerful members, a higher proportion of the extra profits resulting from the JELS. However, the PPS guarantees equitable increases in the individual profits accruing to all members from the JELS. Whereas the DPS works properly in vertically integrated CLSCs and decentralized ones with dominant player(s), the PPS is appropriate for decentralized ones with no dominant players. Additionally, we prove the optimal level of postconsumer recycled content is often either at its maximum or minimum allowable. However, the zero-derivative points within the range can be optimum in a particular case. Consequently, we present decision trees for managers to determine the right profit-sharing method and the optimal postconsumer recycled content level. [ABSTRACT FROM AUTHOR]

Solving Multi-Objective Mixed Integer NonLinear Programming (MO-MINLP) problems is a point of interest for many researchers as they appear in several real-world applications, especially in the mechanical engineering field. Many researchers have proposed using hybrids of metaheuristics with mono-objective branch and bound. Others have suggested using heuristics with Multi-Criteria Branch and Bound (MCBB). A general hybrid approach is proposed based on MCBB and Non-dominated Sorting Genetic Algorithm 2 (NSGAII) to enhance the approximated Pareto front of MO-MINLP problems. A computational experiment based on statistical assessment is presented to compare the performance of the proposed algorithm (BnB-NSGAII) with NSGAII using well-known metrics from the literature. To evaluate the computational efficiency, a new metric, the Investment Ratio (IR), is proposed that relates the quality of solution to the consumed effort. Experimental results on five real-world mechanical engineering problems and two mathematical ones indicate that BnB-NSGAII could be a competitive alternative for solving MO-MINLP problems. [ABSTRACT FROM AUTHOR]

This paper presents an image space branch-reduction-bound algorithm for solving a class of multiplicative problems (MP). First of all, by introducing auxiliary variables and taking the logarithm of the objective function, an equivalent problem (EP) of the problem (MP) is obtained. Next, by using a new linear relaxation technique, the parametric linear relaxation programming (PLRP) of the equivalence problem (EP) can be established for acquiring the lower bound of the optimal value to the problem (EP). Based on the characteristics of the objective function of the equivalent problem and the structure of the branch-and-bound algorithm, some region reduction techniques are constructed for improving the convergence speed of the algorithm. Finally, the global convergence of the algorithm is proved and its computational complexity is estimated, and numerical experiments are reported to indicate the higher computational performance of the algorithm. [ABSTRACT FROM AUTHOR]

This paper considers a group scheduling problem with shorten (i.e., a proportional linear shortening) job processing times and ready times on a single machine. If the jobs are in the same group, they have independent and constant ready times. The setup time of a group is independent constant setup time between each group. The goal is to determine the optimal group sequence and the job sequence within the groups such that the makespan (i.e., the maximum completion time) is minimized. For the general case of the problem, an initial heuristic algorithm (an upper bound) and some lower bounds are proposed, and then a branch-and-bound algorithm can be developed to solve the problem. [ABSTRACT FROM AUTHOR]

In the game industry, tardiness is an important issue. Unlike a unifunctional machine, a developer may excel in programming but be mediocre in scene modeling. His/her processing speed varies with job type. To minimize tardiness, we need to schedule these developers carefully. Clearly, traditional scheduling algorithms for unifunctional machines are not suitable for such versatile developers. On the other hand, in an unrelated machine scheduling problem, n jobs can be processed by m machines at n × m different speeds, i.e., its solution space is too wide to be simplified. Therefore, a tardiness minimization problem considering three job types and versatile developers is presented. In this study, a branch-and-bound algorithm and a lower bound based on harmonic mean are proposed for minimizing the total tardiness. Theoretical analyses ensure the correctness of the proposed method. Computational experiments also show that the proposed method can ensure the optimality and efficiency for n ≤ 18. With the exact algorithm, we can fairly evaluate other approximate algorithms in the future. [ABSTRACT FROM AUTHOR]

We study a steel hot rolling scheduling (HRS) problem considering slab stack shuffling (SSS), which is a kind of key issues in the steel strip production. The HRS problem is to select suitable slabs for a predefined sequence of hot rolling slots, from their respective candidate slab sets so that the number of shuffling operations of slabs is minimized. Different from the most researches, we consider a situation where there are intersections among candidate slab sets and shuffled slabs will not return original stacks. Basing on a special index method of slabs, we present an integer linear programming (ILP) to compute approximation solutions of the problem. In order to improve the solutions obtained by the ILP model, we propose a very large-scale neighborhood (VLSN) search algorithm. In the VLSN search process, the solutions of HRS problems are improved by an iteration procedure that partial solutions are interactively destroyed and repaired. In each iteration, partitioned hot rolling slots correspond to a sub-problem. In the repair operations, we propose an efficient branch-and-bound algorithm for solving sub-problem. The computational results on a number of different scale simulated instances show that the VLSN search algorithm is efficient for solving this kind of HRS problems.

In this paper, we consider a class of nonconvex complex quadratic programming (CQP) problems, which find a broad spectrum of signal processing applications. By using the polar coordinate representations of the complex variables, we first derive a new enhanced semidefinite relaxation (SDR) for problem (CQP). Based on the newly derived SDR, we further propose an efficient branch-and-bound algorithm for solving problem (CQP). Key features of our proposed algorithm are: (1) it is guaranteed to find the global solution of the problem (within any given error tolerance); (2) it is computationally efficient because it carefully utilizes the special structure of the problem. We apply our proposed algorithm to solve the multi-input multi-output (MIMO) detection problem, the unimodular radar code design problem, and the virtual beamforming design problem. Simulation results show that our proposed enhanced SDR, when applied to the above problems, is generally much tighter than the conventional SDR, and our proposed global algorithm can efficiently solve these problems. In particular, our proposed algorithm significantly outperforms the state-of-the-art sphere decode algorithm for solving the MIMO detection problem in the hard cases (where the number of inputs and outputs is equal or the signal-to-noise-ratio is low), and a state-of-the-art general-purpose global optimization solver called Baron for solving the virtual beamforming design problem.

Base on the outer space search and the branch-and-bound framework, this paper presents an efficient outer space branch-and-bound algorithm for globally solving generalized linear multiplicative programming problem. First of all, we convert the problem into an equivalent problem. Then, by utilizing a direct relaxation method, we establish the linear relaxed problem to compute the lower bound of the global optimal value of the equivalent problem. By subsequently subdividing the initial outer space rectangle and solving a series of linear relaxed problems, the proposed algorithm is convergent to the global optimal solution of the primal problem. Finally, compared with some known algorithms, numerical experiments are given to demonstrate the feasibility and effectiveness of the proposed algorithm.

By reformulating the linear multiplicative programming problem (LMP) as an equivalent nonconvex programming problem (EP), we present a new accelerating outcome space branch-and-bound algorithm for globally solving the problem (LMP). Firstly, a linear relaxed programming problem is constructed, which can be used to compute the lower bound of the global optimal value of the problem (EP). Then, by subsequently subdividing the initial outcome space rectangle, and by solving a series of linear relaxed programming problems, the global optimal solution of the problem (LMP) can be obtained. It's worth mentioning that a new region reducing method and a new linear relaxed programming with a higher degree of tightness are also constructed to improve the computational efficiency in the presented algorithm. The global convergence of the presented algorithm is established, and its computational complexity is estimated. Finally, the numerical tests indicate that the presented algorithm has the higher computational efficiency than the known algorithms.