Abstract In deterministic global optimization, techniques for linear relaxation of a non-convex program are used in the lower bound calculation phase. To achieve this phase, most deterministic global optimization codes use reformulation-linearization techniques. However, there exist also two interval-based polyhedral relaxation techniques which produce reliable bounds without adding new auxiliary variables, and which can take into account mathematical operations and most transcendental functions: (i) the affine relaxation technique, used in the IBBA code, based on affine forms and affine arithmetic, and (ii) the extremal Taylor technique, used in the Ibex-Opt code, which is based on a specific interval-based Taylor form. In this paper, we describe how these two interval-based linear relaxation techniques can be hybridized. These two approaches appear to be complementary, and such a hybrid method performs well on a representative sample of constrained global optimization instances.

When interval branch and bound solvers are used for solving constrained global optimization, upper bounding the objective function is an important mechanism which helps to reduce globally the search space. Each time a new upper bound UB is found during the search, a constraint related to the objective function fobj (x). <; UB is added in order to prune non-optimal regions. We quantified experimentally that if we knew a close-to-optimal value in advance (without necessarily knowing the corresponding solution), then the performance of the solver could be significantly improved. Thus, in this work we propose a simple mechanism for estimating upper bounds in order to accelerate the convergence of interval branch and bound solvers. The proposal is validated through a series of experiments.

Interval branch & bound solvers are commonly used for solving numerical constraint satisfaction problems. They alternate filtering/contraction and branching steps in order to find small boxes containing all the solutions of the problem. The branching basically consists in generating two sub problems by dividing the domain of one variable into two. The selection of this variable is the topic of this work. Several heuristics have been proposed so far, most of them using local information from the current node (e.g., Domain sizes, partial derivative images over the current box, etc). We propose instead an approach based on past information. This information is provided by a preprocessing phase of the algorithm (probing) and is used during the search. In simple words, our algorithm attempts to identify the most important variables in a series of cheap test runs. As a result of probing, the variables are weighted. These weights are then considered by the selection heuristic during the search. Experiments stress the interest of using techniques based on past information in interval branch & bound solvers.

In this paper we propose a local search algorithm to tackle scheduling radiotherapy problems. Our scheduling radiotherapy problem has a set of constraints that must be satisfied and another set of soft constraints that are suitable to be satisfied. Many resources are involved in the scheduling as doctors, patients and machines. The goal is focused on improving the patient care services. Our algorithm has been tested using a real world problem as well as a set of new benchmarks that we introduce in this work.

In this work we attempt to study and discover the principles behind one of the most succesfulvariable selection heuristics in branch-and-prune interval-based solvers: the Smear-based heuristics. Why these heuristics work? Which is their objective?Can we do any better?Based on the principles of the Smear functionand the well-known first-fail principle: "To succeed, try first where you are most likely to fail" we propose several variable selection heuristics. The heuristics are tested and compared to the Smear-based oneson solving twenty nonlinear systems of equations. We report our first results and conclusions.

In this paper, we introduce a method which goal is to help the search done by a Stochastic Local Search algorithm. Given a set of initial configurations, our algorithm dynamically discriminates the ones that seems to give more promising solutions, discarding at the same time those which did not help. The concept of diversity is managed in our framework in order to both avoid stagnation and to explore the search space. To evaluate our method, we use a well-known local search algorithm. This algorithm has been specially designed for solving instances of the challenging Traveling Tournament Problem. We compare the performance obtained running different configurations of the local search algorithm to the ones using our framework. Our results are very encouraging in terms of both the quality of the solutions and the execution time required.

Researchers from interval analysis and constraint (logic) programming communities have studied intervals for their ability to manage infinite solution sets of numerical constraint systems. In particular, inner regions represent subsets of the search space in which all points are solutions. Our main contribution is the use of recent and new inner region extraction algorithms in the upper bounding phase of constrained global optimization. Convexification is a major key for efficiently lower bounding the objective function. We have adapted the convex interval taylorization proposed by Lin and Stadherr for producing a reliable outer and inner polyhedral approximation of the solution set and alinearization of the objective function. Other original ingredients are part of our optimizer, including an efficient interval constraint propagation algorithm exploiting monotonicity of functions. We end up with a new framework for reliable continuous constrained global optimization. Our interval B&B is implemented in the interval-based explorer Ibex and extends this free C++ library. Our strategy outperforms the best reliable global optimizers.

We propose in this paper a new interval constraint propagation algorithm, called MOnotonic Hull Consistency (Mohc), that exploits monotonicity of functions. The propagation is standard, but the Mohc-Revise procedure, used to filter/contract the variable domains w.r.t. an individual constraint, uses monotonic versions of the classical HC4-Revise and BoxNarrow procedures. Mohc-Revise appears to be the first adaptive revise procedure ever proposed in (interval) constraint programming. Also, when a function is monotonic w.r.t. every variable, Mohc-Revise is proven to compute the optimal/sharpest box enclosing all the solutions of the corresponding constraint (hull consistency). Very promising experimental results suggest that Mohc has the potential to become an alternative to the state-of-the-art HC4 and Box algorithms.

When handling 2D packing problems, numerous incomplete and complete algorithms maintain a so-called bottom-left (BL) property: every rectangle placed in a container is propped up bottom and left. While it is easy to make a rectangle BL when it is is added in a container, it is more expensive to maintain all the placed pieces BL when a rectangle is removed. This prevents researchers from designing incremental moves for metaheuristics or efficient complete optimization algorithms. This paper investigates the possibility of violating the BL property. Instead, we propose to maintain only the set of "maximal holes", which allows incremental additions and removals of rectangles. To validate our alternative approach, we have designed an incremental move, maintaining maximal holes, for the strip-packing problem, a variant of the famous 2D bin-packing. We have also implemented a generic metaheuristic using this move and standard greedy heuristics. Experimental results show that the approach is competitive with the best known incomplete algorithms, especially the other metaheuristics (able to escape from local minima).