1435 research outputs found
Sort by
On Linearising Mixed-Integer Quadratic Programs via Bit Representation
Full text linkIt is well known that, under certain conditions, one can use bit representation to transform both integer
quadratic programs
and mixed-integer bilinear programs into mixed-integer linear programs (MILPs), and thereby render them
easier to solve using standard software packages. We show how to convert a more general family of
mixed-integer quadratic programs to MILPs, and present several families of strong valid linear inequalities
that can be used to strengthen the continuous relaxations of the resulting MILPs
Gap functions for quasi-equilibria
No full textAn approach for solving quasi-equilibrium problems (QEPs) is proposed relying on gap functions, which allow reformulating QEPs as global optimization problems. The (generalized) smoothness properties of a gap function are analysed and an upper estimates of its Clarke directional derivative is given.
Monotonicity assumptions on both the equilibrium and constraining bifunctions are a key tool to guarantee that all the stationary points of a gap function actually solve QEP. A few classes of constraints satisfying such assumptions are identified covering a wide range of situations. Relying on these results, a descent method for solving QEP is devised and its convergence proved. Finally, error bounds are given in order to guarantee the boundedness of the sequence generated by the algorithm
The MPA Graph Problem
Full text linkGiven an undirected graph G whose vertices are associated to different subsets of colors, the MPA problem asks for partitioning G into a minimal set of monochromatic connected subgraphs. We prove that MPA is NP-hard as well as its extensions BDMPA where the vertices of G have a bounded maximum degree, PMPA where G is planar, BDPMPA where the maximum vertex degree is bounded and G is planar, and GMPA
where G consists of a p by q grid
Bloch oscillations and mean-field effects of Bose-Einstein condensates in 1-D optical lattices
No full textWe have loaded Bose-Einstein condensates into one-dimensional, off-resonant
optical lattices and accelerated them by chirping the frequency difference
between the two lattice beams. For small values of the lattice well-depth,
Bloch oscillations were observed. Reducing the potential depth further,
Landau-Zener tunneling out of the lowest lattice band, leading to a breakdown
of the oscillations, was also studied and used as a probe for the effective
potential resulting from mean-field interactions as predicted by Choi and Niu
[Phys. Rev. Lett. {\bf 82}, 2022 (1999)]. The effective potential was measured
for various condensate densities and trap geometries, yielding good qualitative
agreement with theoretical calculations
Assigning and sequencing storage locations under a two level storage policy: optimization model and matheuristic approach
Full text linkWe deal with a storage location problem in a warehouse where items of different product types are released by the production area and need to be stored.
Capacitated storage locations have to be assigned to each product type to store the corresponding items. Items of different product types cannot share the same storage location, i.e., each storage location can be assigned to at most one product type. In addition, a suitable sequencing of the assigned storage locations must be devised for each product type. Each sequence will provide both the order with which the storage locations will be filled up during the storing operations, and also the order of visit of the storage locations during the successive order picking phase. A motivation is that, separately per product type, an order picking based on the time of permanence of the items in the warehouse has to be pursued. Moreover, the chosen sequencing influences the availability of additional storage on the top of the assigned storage locations. In fact, for each product type, an additional extra storage can be made available on top of pairs of consecutive storage locations in the sequence, which depends on the two storage locations at the ground level. The goal is to maximize the storage capacity still available after the assignment of the storage locations.
After proving the NP-Hardness of the considered problem, we model it in terms of a multicommodity flow problem with additional constraints on an auxiliary graph, and we propose a Mixed-Integer Linear Programming model for its mathematical formulation. A matheuristic approach, based on the sequential resolution of multicommodity flow subproblems, is then presented. The proposed methodology is applied to a case study related to a large warehouse with a high stock rotation index in tissue logistics, which motivated our study. Computational results on a wide test bed related to such a real application context show the efficiency and efficacy of the proposed approach