In this paper, which is an extension of [4],we first show the existence of solutions to a class of Min Sup problems with linked constraints, which satisfy a certain property. Then, we apply our result to a class of weak nonlinear bilevelproblems. Furthermore, for such a class of bilevel problems, wegive a relationship with appropriate d.c. problems concerning theexistence of solutions.

Many combinatorial optimization problems can be formulated asthe minimization of a 0–1 quadratic function subject to linear constraints. Inthis paper, we are interested in the exact solution of this problem through atwo-phase general scheme. The first phase consists in reformulating theinitial problem either into a compact mixed integer linear program or into a0–1 quadratic convex program. The second phase simply consists insubmitting the reformulated problem to a standard solver. The efficiency ofthis scheme strongly depends on the quality of the reformulation obtained inphase 1. We show that a good compact linear reformulation can be obtained bysolving a continuous linear relaxation of the initial problem. We also showthat a good quadratic convex reformulation can be obtained by solving asemidefinite relaxation. In both cases, the obtained reformulation profitsfrom the quality of the underlying relaxation. Hence, the proposed scheme getsaround, in a sense, the difficulty to incorporate these costly relaxations ina branch-and-bound algorithm.

This paper presents a logarithmic barrier method for solving a semi-definite linear program. The descent direction is the classical Newton direction. We propose alternative ways to determine the step-size along the direction which are more efficient than classical line-searches.

In this work, we present an introduction to automatic differentiation,its use in optimization software, and some new potential usages. Wefocus on the potential of this technique inoptimization. We do not dive deeply in the intricacies of automaticdifferentiation, but put forward its key ideas. We sketch a survey, asof today, of automatic differentiation software, but warn the readerthat the situation with respect to software evolves rapidly. In thelast part of the paper, we present some potential future usage ofautomatic differentiation, assuming an ideal tool is available, whichwill become true in some unspecified future.

In this paper, we study the differentiability of the trajectories of the logarithmic barrier algorithm for a nonlinearprogram when the set Λ* of the Karush-Kuhn-Tucker multiplier vectors is emptyowing to the fact that the constraint qualifications are not satisfied.


In this paper we present a generic primal-dualinterior point methods (IPMs) for linear optimization in which the search direction depends on a univariate kernel function which is also used as proximity measure in the analysis of the algorithm. The proposed kernel function does not satisfy all the conditions proposed in [2].We show that the corresponding large-update algorithm improves the iteration complexity with a factor $n^{\frac16}$ when compared with the method based on the use of the classical logarithmic barrier function. For small-update interior point methods the iteration bound is $O(\sqrt{n}\log\frac{n}{\epsilon}),$ which is currently the best-known bound for primal-dual IPMs.

This paper describes a new representation for the solutions of the resource-constrained project scheduling problem (RCPSP) denoted Activity Set List. The most efficient heuristics for the problem use the activity list representation and the serial SGS method to construct the corresponding solution (schedule). The activity list may induce a search space of representations much larger then the space of schedules because the same schedule can correspond to many different activity list representations. We indicate how the activity set list representation can significantly reduce the search space, and how to move more efficiently through it. Furthermore, this new representation never excludes the optimal solution and it has many interesting properties. An evaluation of the search space reduction induced by this representation is made for the most used library of instances in the literature. The activity set list representation may be used to construct a new category of more efficient solution procedures for the problem.

This paper considers large shift scheduling problems with different shiftstart times and lengths, fractionable breaks and work stretch durationrestrictions. Two solution approaches are proposed to solve the problemsover a multiple-day planning horizon. The first approach is based on alocal branching strategy and the second one is based on a temporaldecomposition of the problem. Local branching is veryefficient in finding good feasible solutions when compared to a classicalbranch-and-bound procedure. However, the decomposition approach has theadvantage of yielding feasible solutions in short computing times, even for difficult instances.