In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to … Read more
In this paper, we extend a class of globally convergent evolution strategies to handle general constrained optimization problems. The proposed framework handles relaxable constraints using a merit function approach combined with a specific restoration procedure. The unrelaxable constraints in our framework, when present, are treated either by using the extreme barrier function or through a … Read more
Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that … Read more
We consider a general class of infinite horizon dynamic programmes where state and control sets are convex and compact subsets of Euclidean spaces and (convex) costs are discounted geometrically. The aim of this work is to provide a convergence result for these problems under as few restrictions as possible. Under certain assumptions on the cost … Read more
In Food Industry, the combined treatments based on high-pressure and temperature (HPT) are frequently used to increment the durability of the products without damaging their good properties. However, achieving a reasonable compromise between conservation and quality is usually a challenging task. In a previous work, we proposed a decision tool which solves a multi-objective optimization … Read more
We consider generalizations of parity polytopes whose variables, in addition to a parity constraint, satisfy certain ordering constraints. More precisely, the variable domain is partitioned into k contiguous groups, and within each group, we require the variables to be sorted nonincreasingly. Such constraints are used to break symmetry after replacing an integer variable by a … Read more
We consider the maximum $k$-cut problem that involves partitioning the vertex set of a graph into $k$ subsets such that the sum of the weights of the edges joining vertices in different subsets is maximized. The associated semidefinite programming (SDP) relaxation is known to provide strong bounds, but it has a high computational cost. We … Read more
We address combinatorial optimization problems with uncertain coefficients varying over ellipsoidal uncertainty sets. The robust counterpart of such a problem can be rewritten as a second-oder cone program (SOCP) with integrality constraints. We propose a branch-and-bound algorithm where dual bounds are computed by means of an active set algorithm. The latter is applied to the … Read more
This paper presents rigorous filtering methods for constraint satisfaction problems based on the interval union arithmetic. Interval unions are finite sets of closed and disjoint intervals that generalize the interval arithmetic. They allow a natural representation of the solution set of interval powers, trigonometric functions and the division by intervals containing zero. We show that … Read more
We introduce a new variant of Chubanov’s method for solving linear homogeneous systems with positive variables. In the \BP\ we use a recently introduced cut in combination with Nemirovski’s Mirror-Prox method. We show that the cut requires at most $O(n^3)$ time, just as Chabonov’s cut. In an earlier paper it was shown that the new … Read more