We study the solution of a multiobjective nonlinear sum of fractional optimization problems. A dualitybased branch and bound cut method is developed for the efficient solution of this problems. The proposed methodolog...
详细信息
We study the solution of a multiobjective nonlinear sum of fractional optimization problems. A dualitybased branch and bound cut method is developed for the efficient solution of this problems. The proposed methodology is validated by proving the required theoretical assertions for the solution. The present method is an extension of the work P. P. Shen, Y. P. Duan, and Y. G. Pei [J. Comput. Appl. Math., 223, 145-158 (2009)] developed for a single-objective sum of ratios of nonlinear optimization problems. The proposed method is realized in MatLab (version 2014b). Two numerical problems are considered and solved by using the proposed method and the global optimal solution is obtained.
Many real-world planning problems require searching for an optimal solution in the face of uncertain input. One approach to is to express them as a two-stage stochastic optimization problem where the search for an opt...
详细信息
ISBN:
(纸本)9781479907298
Many real-world planning problems require searching for an optimal solution in the face of uncertain input. One approach to is to express them as a two-stage stochastic optimization problem where the search for an optimum in one stage is informed by the evaluation of multiple possible scenarios in the other stage. If integer solutions are required, then branch-and-bound techniques are the accepted norm. However, there has been little prior work in parallelizing and scaling branch-and-boundalgorithms for stochastic optimization problems. In this paper, we explore the parallelization of a two-stage stochastic integer program solved using branch-and-bound. We present a range of factors that influence the parallel design for such problems. Unlike typical, iterative scientific applications, we encounter several interesting characteristics that make it challenging to realize a scalable design. We present two design variations that navigate some of these challenges. Our designs seek to increase the exposed parallelism while delegating sequential linear program solves to existing libraries. We evaluate the scalability of our designs using sample aircraft allocation problems for the US airfleet. It is important that these problems be solved quickly while evaluating large number of scenarios. Our attempts result in strong scaling to hundreds of cores for these datasets. We believe similar results are not common in literature, and that our experiences will feed usefully into further research on this topic.
The U-curve branch-and-bound algorithm for optimization was introduced recently by Ris and collaborators. In this paper we introduce an improved algorithm for finding the optimal set of features based on the U-curve a...
详细信息
ISBN:
(纸本)9781479934621
The U-curve branch-and-bound algorithm for optimization was introduced recently by Ris and collaborators. In this paper we introduce an improved algorithm for finding the optimal set of features based on the U-curve assumption. Synthetic experiments are used to asses the performance of the proposed algorithm, and compare it to exhaustive search and the original algorithm. The results show that the modified U-curve BB algorithm makes fewer evaluations and is more robust than the original algorithm.
The branch-and-bound (B& B) method is a wellknown optimization algorithm for solving integer linear programming (ILP) models in the field of operations research. It is part of software often employed by businesses...
详细信息
ISBN:
(纸本)9781479907298
The branch-and-bound (B& B) method is a wellknown optimization algorithm for solving integer linear programming (ILP) models in the field of operations research. It is part of software often employed by businesses for finding solutions to problems such as airline scheduling problems. It operates according to a divide-and-conquer principle by building a treelike structure with nodes that represent linear programming (LP) problems. A LP solver commonly used to process the nodes is the simplex method. Nowadays its sequential implementation can be found in almost all commercial ILP solvers. In this paper, we present a hybrid CPU-GPU implementation of the B&B algorithm. The B&B tree is managed by the CPU, while the revised simplex method is mainly a GPU implementation, relying on the CUDA technology of NVIDIA. The CPU manages concurrently multiple instances of the LP solver. The principal difference with a sequential implementation of the B&B algorithm pertains to the LP solver, provided that the B&B tree is managed with the same strategy. We thus compared our GPU-based implementation of the revised simplex to a wellknown open-source sequential solver, named CLP, of the COINOR project. For given problem densities, we measured a size threshhold beyond which our GPU implementation outperformed its sequential counterpart.
Considerable attention had previously been given to the single-vendor single-customer integrated inventory problem, but there had been very little work on the integrated single-vendor multi-customer and multi-product ...
详细信息
ISBN:
(纸本)9781479967735
Considerable attention had previously been given to the single-vendor single-customer integrated inventory problem, but there had been very little work on the integrated single-vendor multi-customer and multi-product consideration. Here, we develop a generalized single-vendor multi-customer with multi-product consideration supply chain model with one transporter available to deliver the products from the supplier to the customers. The objective is to solve the proposed model and to find the minimized total cost, while guaranteeing a certain customer service level. A mathematical formulation of the problem is given in a general way. Then, we propose a branch and bound algorithm as an exact method and an efficient heuristic greedy algorithm. Both procedures are then compared through computational experiments which show that the heuristic algorithm is capable of generating near-optimal solutions within a short amount of CPU time.
The bilevel programming problem (BLPP) is a model of a leader-follower game in which play is sequential and cooperation is not permitted. In the first part of the paper, some basic properties of the general model are ...
详细信息
The bilevel programming problem (BLPP) is a model of a leader-follower game in which play is sequential and cooperation is not permitted. In the first part of the paper, some basic properties of the general model are developed and a conjecture relevant to solution procedures is presented. Next, two algorithms are presented for solving various versions of the game when certain convexity conditions hold. One algorithm relies upon a hybrid branch and bound scheme, and it does not guarantee global optimality. Another is based upon objective function cuts and, barring numerical stability problems with the optimize, is guaranteed to converge to an epsilon-optimal solution. Finally, performance of the two algorithms is examined using randomly generated test problems. The computational performance of the branch and bound algorithm is explored, and the cutting plane algorithm is used to determine whether or not the branch and bound algorithm is uncovering global optima.
Attack graph is a popular tool for modelling multi-staged, correlated attacks on computer networks. Attack graphs have been widely used for measuring network security risks. Majority of the works on attack graph use h...
详细信息
Attack graph is a popular tool for modelling multi-staged, correlated attacks on computer networks. Attack graphs have been widely used for measuring network security risks. Majority of the works on attack graph use host-based or state-based approaches. These attack graph models are either too restrictive or too resource consuming. Also, a significant portion of these works have used 'probability of successfully exploiting a network' as the metric. This approach requires that the 'probability of successfully exploiting individual vulnerabilities' be known a priori. Finding such probabilities is inherently difficult. This present study uses exploit dependency graph, which is a space efficient and expressive attack graph model. It also associates an additive cost with executing individual exploits, and defines a security metric in terms of the 'minimum cost required to successfully exploit the network'. The problem of calculating the said metric is proved to be NP-complete. A modified depth first branch and bound algorithm has been described for calculating it. This study also formulates, a linear-time computable, security metric in terms of the 'expected cost required to successfully exploit the network' assuming a random attacker model and an uncorrelated attack graph.
This paper addresses a new class of linearly constrained fractional programming problems where the objective function is defined as the ratio of two functions which are the sums of the absolute values of affine functi...
详细信息
This paper addresses a new class of linearly constrained fractional programming problems where the objective function is defined as the ratio of two functions which are the sums of the absolute values of affine functions. This problem has an important application in financial optimization. This problem is a convex-convex type of fractional program which cannot be solved by standard algorithms. We propose a branch-and-bound algorithm and an integer programming algorithm. We demonstrate that a fairly large scale problem can be solved within a practical amount of time.
This paper considers a job sequencing problem for a single numerical controlled machining center. It is assumed that all the considered jobs must be processed on a single machine provided with a tool magazine with C p...
详细信息
This paper considers a job sequencing problem for a single numerical controlled machining center. It is assumed that all the considered jobs must be processed on a single machine provided with a tool magazine with C positions, that no job requires more than C tools to be completely machined and that the tools may be loaded and unloaded from the tool magazine only when the machining operations for each job are completed. The decisional problem is referred to as the tool loading problem (TLP) and it determines the jobs machining sequence as well as the tools to load in the machine tool magazine before the machining operations on each job may start. In industrial cases where the tool switching time is both significant relative to job processing time and proportional to the number of tool switches, the performance criterion is the minimization of the number of tool switches. This paper demonstrates that the TLP is a symmetric sequencing problem. The authors enrich a branch-and-bound algorithm proposed in literature for the TLP with the new symmetric formulation. Computational experiments show the significant improvement obtained by the novel symmetric formulation of the TLP. (c) 2007 Elsevier Ltd. All rights reserved.
In branch and bound algorithms in constrained global optimization, a sharp upper bound on the global optimum is important for the overall efficiency of the branch and bound process. Software to find local optimizers, ...
详细信息
In branch and bound algorithms in constrained global optimization, a sharp upper bound on the global optimum is important for the overall efficiency of the branch and bound process. Software to find local optimizers, using floating point arithmetic, often computes an approximately feasible point close to an actual global optimizer. Not mathematically rigorous algorithms can simply evaluate the objective at such points to obtain approximate upper bounds. However, such points may actually be slightly infeasible, and the corresponding objective values may be slightly smaller than the global optimum. A consequence is that actual optimizers are occasionally missed, while the algorithm returns an approximate optimum and corresponding approximate optimizer that is occasionally far away from an actual global optimizer. In mathematically rigorous algorithms, objective values are accepted as upper bounds only if the point of evaluation is proven to be feasible. Such computational proofs of feasibility have been weak points in mathematically rigorous algorithms. This paper first reviews previously proposed automatic proofs of feasibility, then proposes an alternative technique. The alternative technique is tried on a test set that caused trouble for previous techniques, and is also employed in a mathematically rigorous branch and bound algorithm on that test set.
暂无评论