We discuss a tightly feasible mixed-integer linear programs arising in the energy industry, for which branch-and-bound appears to be ineffective. We consider its hardness, measure the probability that randomly generated instances are feasible or almost feasible, and introduce heuristic solution methods based on relaxing different constraints of the problem. We show the computational efficiency of … Read more
We propose an algorithm based on infeasible irreducible subsystems (IIS) to solve general binary chance-constrained problems. By leverag- ing on the problem structure we are able to generate good quality upper bounds to the optimal value early in the algorithm, and the discrete do- main is used to guide us eciently in the search of … Read more
We exactly solve the NP-hard combinatorial optimization problem of finding a minimum cardinality vertex separator with k (or arbitrarily many) capacitated shores in a hypergraph. We present an exponential size integer programming formulation which we solve by branch-and-price. The pricing problem, an interesting optimization problem on its own, has a decomposable structure that we exploit … Read more
A probabilistic framework for large classes of binary integer programming problems is constructed. The approach is given by a mean field annealing scheme where the annealing phase is substituted by the solution of a dual problem that gives a lower (upper) bound for the original minimization (maximization) integer task. This bound has an information theoretic … Read more
It is common knowledge that symmetries arising in integer programs could impair the solution process, in particular when symmetric solutions lead to an excessively large branch and bound (B&B) search tree. Techniques like isomorphic pruning [11], orbital branching [16] and orbitopal fixing [8] have been shown to be essential to solve very symmetric instances from … Read more
It is often useful in practice to explore near-optimal solutions of an integer programming problem. We show how all solutions within a given tolerance of the optimal value can be efficiently and compactly represented in a weighted decision diagram, once the optimal value is known. The structure of a decision diagram facilitates rapid processing of … Read more
We consider a novel method entitled constraints reduction programming which aims to reduce the constraints in an optimization model. This method is derived from various applications of management or decision making, and has potential ability to handle a wider range of applications. Due to the high combinatorial complexity of underlying model, it is difficult to … Read more
The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a prohibitive number of valid inequalities and integer variables. In this … Read more
In this paper we investigate non-linear matroid optimization problems with polynomial objective functions where the monomials satisfy certain monotonicity properties. Indeed, we study problems where the set of non-linear monomials consists of all non-linear monomials that can be built from a given subset of the variables. Linearizing all non-linear monomials we study the respective polytope. … Read more
We consider integer optimization problems where variables can potentially take fractional values, but this occurrence is penalized in the objective function. This general situation has relevant examples in scheduling (preemption), routing (split delivery), cutting and telecommunications, just to mention a few. However, the general case in which variables integrality can be relaxed at cost of … Read more