Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Valid inequalities for the single arc design problem with set-ups ; ; Louveaux, Quentin in Discrete Optimization (2015), 16 We consider a mixed integer set which generalizes two well-known sets: the single node fixed- charge network set and the single arc design set. Such set arises as a relaxation of feasible sets of general ... [more ▼] We consider a mixed integer set which generalizes two well-known sets: the single node fixed- charge network set and the single arc design set. Such set arises as a relaxation of feasible sets of general mixed integer problems such as lot-sizing and network design problems. We derive several families of valid inequalities that, in particular, generalize the arc resid- ual capacity inequalities and the flow cover inequalities. For the constant capacitated case we provide an extended compact formulation and give a partial description of the convex hull in the original space which is exact under a certain condition. By lifting some basic inequalities we provide some insight on the difficulty of obtaining such a full polyhedral description for the constant capacitated case. Preliminary computational results are presented. [less ▲] Detailed reference viewed: 48 (11 ULg)Multi-Dimensional Vector Assignment Problems ; Crama, Yves ; in Discrete Optimization (2014), 14 We consider a special class of axial multi-dimensional assignment problems called multi- dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by m disjoint sets, each of ... [more ▼] We consider a special class of axial multi-dimensional assignment problems called multi- dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by m disjoint sets, each of which contains the same number n of p-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an m-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the m sets of vectors into n m-tuples so that no two vectors from the same set are in the same m-tuple and so that the sum of the costs of the m-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed m. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case m = 3 and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension p. [less ▲] Detailed reference viewed: 38 (9 ULg)A combinatorial branch-and-bound algorithm for box search Mathieu, Sébastien ; Louveaux, Quentin in Discrete Optimization (2014), 13 Considering a set of points in a multi-dimensional space with an associated real value for each point, we want to find the box with the maximum sum of the values of the included points. This problem has ... [more ▼] Considering a set of points in a multi-dimensional space with an associated real value for each point, we want to find the box with the maximum sum of the values of the included points. This problem has applications in data mining and can be formulated as a mixed-integer linear program. We propose a branch-and-bound algorithm where the bounding is obtained by combinatorial arguments instead of the traditional linear relaxation. Computational experiments show that this approach competes with current state of the art mixed-integer solvers. The algorithm proposed in this paper may be seen as a simple and dependence-free method to solve the box search problem. [less ▲] Detailed reference viewed: 81 (26 ULg)Intermediate integer programming representations using value disjunctions Köppe, Matthias ; Louveaux, Quentin ; in Discrete Optimization (2008), 5(2), 293-313 We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The ... [more ▼] We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formu- lation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet descrip- tion decomposes into one “linking polyhedron” per block and the “aggre- gated polyhedron”. Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coeffi- cients, this theorem provides a complete description in an extended space with a polynomial number of variables. Based on this theory, we propose a new branching scheme that analyzes the problem structure. It is designed to be applied in those subproblems of hard integer programs where LP-based techniques do not provide good branching decisions. Preliminary computational experiments show that it is successful for some benchmark problems of multi-knapsack type. [less ▲] Detailed reference viewed: 64 (11 ULg)Extended formulations for Gomory Corner polyhedra Köppe, Matthias ; Louveaux, Quentin ; et al in Discrete Optimization (2004), 1(2), 141-165 We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory’s group relaxations. We present algorithmic schemes based on an iterative ... [more ▼] We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory’s group relaxations. We present algorithmic schemes based on an iterative reformulation technique using these extended formulations. We give computational results for benchmark problems, which illustrate the primal and dual effect of the reformulation. [less ▲] Detailed reference viewed: 72 (4 ULg) |
||