References of "Discrete Optimization"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailA combinatorial branch-and-bound algorithm for box search
Mathieu, Sébastien ULg; Louveaux, Quentin ULg

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: 38 (17 ULg)
Full Text
Peer Reviewed
See detailIntermediate integer programming representations using value disjunctions
Köppe, Matthias ULg; Louveaux, Quentin ULg; Weismantel, Robert

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: 56 (9 ULg)
Full Text
Peer Reviewed
See detailExtended formulations for Gomory Corner polyhedra
Köppe, Matthias ULg; Louveaux, Quentin ULg; Weismantel, Robert 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: 64 (4 ULg)