A proposal for a hybrid meta-strategy for combinatorial optimization problems

In this paper, we propose an algorithm named BDS (Bound-Driven Search) that combines features of exact and approximate methods. The proposed procedure may be seen as a local search algorithm that systematically explores (in a branch-and bound sense) the most promising nodes, thus preventing solutions from being reevaluated. Additionally, it can be regarded as an exact method as it may be able to guarantee that the solution found is optimal. We present the application of this new algorithm to a specific problem domain: the permutation flow shop scheduling problem with makespan objective. The subsequent computational experiments are encouraging, as the algorithm is able to yield exact or near exact solutions to most instances of the problem. Furthermore, the algorithm outperforms one of the best state-of-the-art algorithms for the problem.     

An acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem

This contribution is focused on an acceleration of branch and bound algorithms for the uncapacitated facility location problem. Our approach is based on the well-known Erlenkotters’ procedures and Körkels’ multi-ascent and multi-adjustment algorithms, which have proved to be the efficient tools for solving the large-sized instances of the uncapacitated facility location problem. These two original approaches were examined and a thorough analysis of their performance revealed how each particular procedure contributes to the computational time of the whole algorithms. These analyses helped us to focus our effort on the most frequent procedures. The unique contribution of this paper is a new dual ascent procedure. This procedure leads to considerable acceleration of the lower bound computation process and reduces the resulting computational time. To demonstrate more efficient performance of amended algorithms we present the results of extensive numerical experiments.     

Two-stage integer programs with stochastic right-hand sides: a superadditive dual approach

We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms for finding the value functions. To solve the reformulation after obtaining the value functions, we develop a global branch-and-bound approach and a level-set approach to find an optimal tender. We show that our method can solve randomly generated instances whose extensive forms are several orders of magnitude larger than the extensive forms of those instances found in the literature. This work is supported by National Science Foundation grants DMI-0217190 and DMI-0355433.     

A novel algorithm for branch cut phase unwrapping

Branch cut method is a powerful noise-immune algorithm for correct phase unwrapping of noisy phase maps. The shortest branch cut length promises the optimal unwrapping result of the wrapped phase maps. A new algorithm is proposed to search for the shortest branch cut length by simple exchange operation. Although the algorithm is on the basis of stochastic search techniques, it has a high probability of finding the shortest branch cut length or an approximation of it. Compared with the traditional algorithms, the algorithm is fast and competitive.     

A column generation approach for solving the patient admission scheduling problem

This paper addresses the Patient Admission Scheduling (PAS) problem. The PAS problem entails assigning elective patients to beds, while satisfying a number of hard constraints and as many soft constraints as is possible, and arises at all planning levels for hospital management. There exist a few, different variants of this problem. In this paper we consider one such variant and propose an optimization-based heuristic building on branch-and-bound, column generation, and dynamic constraint aggregation to solve it. We achieve tighter lower bounds than previously reported in the literature and, in addition, we are able to produce new best known solutions for five out of twelve instances from a publicly available repository.     

Possibilistic sequential decision making

When the information about uncertainty cannot be quantified in a simple, probabilistic way, the topic of possibilistic decision theory is often a natural one to consider. The development of possibilistic decision theory has lead to the proposition a series of possibilistic criteria, namely: optimistic and pessimistic possibilistic qualitative criteria [7], possibilistic likely dominance [2], [9], binary possibilistic utility [11] and possibilistic Choquet integrals [24]. This paper focuses on sequential decision making in possibilistic decision trees. It proposes a theoretical study on the complexity of the problem of finding an optimal strategy depending on the monotonicity property of the optimization criteria – when the criterion is transitive, this property indeed allows a polytime solving of the problem by Dynamic Programming. We show that most possibilistic decision criteria, but possibilistic Choquet integrals, satisfy monotonicity and that the corresponding optimization problems can be solved in polynomial time by Dynamic Programming. Concerning the possibilistic likely dominance criteria which is quasi-transitive but not fully transitive, we propose an extended version of Dynamic Programming which remains polynomial in the size of the decision tree. We also show that for the particular case of possibilistic Choquet integrals, the problem of finding an optimal strategy is NP-hard. It can be solved by a Branch and Bound algorithm. Experiments show that even not necessarily optimal, the strategies built by Dynamic Programming are generally very good.     

A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness

This paper addresses the NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup times and no preemption where the objective is to minimize the maximum tardiness. An algorithm based on branch-and-bound permutation schemes is developed including the implementation of lower and upper bounding procedures, and three dominance rules. Computational experiments demonstrate the effectiveness of the algorithm. In the experiments, the impacts of control parameters to generate test instances on algorithm performance (CPU times) are studied by statistics methods.     

Solving maximum-entropy sampling problems using factored masks

We present a practical approach to Anstreicher and Lee’s masked spectral bound for maximum-entropy sampling, and we describe favorable results that we have obtained with a Branch-and-Bound algorithm based on our approach. By representing masks in factored form, we are able to easily satisfy a semidefiniteness constraint. Moreover, this representation allows us to restrict the rank of the mask as a means for attempting to practically incorporate second-order information. Supported in part by NSF Grant CCR-0203426.     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.     

An efficient envelope-based Branch and Bound algorithm for non-convex combined heat and power production planning

Combined heat and power (CHP) production is universally accepted as one of the most energy-efficient technologies to produce energy with lower fuel consumption and fewer emissions. In CHP technology, heat and power generation follow a joint characteristic. Traditional CHP production is usually applied in backpressure plants, where the joint characteristic can often be represented by a convex model. Advanced CHP production technologies such as backpressure plants with condensing and auxiliary cooling options, gas turbines, and combined gas and steam cycles may require non-convex models. Cost-efficient operation of a CHP system can be planned using an optimization model based on forecasts for heat load and power price. A long-term planning model decomposes into thousands of single-period models, which can be formulated in the convex case as linear programming (LP) problems, and in the non-convex case as mixed integer programming (MIP) problems.