We describe improvements to Smith’s branch-and-bound (B&B) algorithm for the Euclidean Steiner problem in R^d. Nodes in the B&B tree correspond to full Steiner topologies associated with a subset of the terminal nodes, and branching is accomplished by “merging” a new terminal node with each edge in the current Steiner tree. For a given topology … Read more
While dealing with uncertainty in linear programs, the robust optimization framework proposed by Bertsimas and Sim appears as relevant. In particular, it can readily be extended for integer linear programming. This paper outlines the polyhedral impacts of this robust model for the 0-1 knapsack problem. It shows especially how the classical cover cuts can be … Read more
In this paper we derive new properties of extreme inequalities for infinite group problems. We develop tools to prove that given valid inequalities for the infinite group problem are extreme. These results show that integer infinite group problems have discontinuous extreme inequalities. These inequalities are strong when compared to related classes of continuous extreme inequalities. … Read more
We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal sub ject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain … Read more
One of perspective ways to exploit sparsity in the dependency graph of an optimization problem as J.N. Hooker stressed is nonserial dynamic programming (NSDP) which allows to compute solution in stages, each of them uses results from previous stages. The class of discrete optimization problems with the block-tree-structure matrix of constraints is considered. Nonserial dynamic … Read more
In this paper we present a centralized model for managing, at the same time, the dayahead energy market and the reserve market in order to price through the market, beside energy, the overall cost of reliability and to assure that the power grid survives the failure of any single components, so to avoid extended blackouts. … Read more
Chance-constrained programming is a relevant model for many concrete problems. However, it is known to be very hard to tackle directly. In this paper, the chance-constrained knapsack problem (CKP) is addressed. Relying on the recent advances in robust optimization, a tractable combinatorial algorithm is proposed to solve CKP. It always provides feasible solutions for CKP. … Read more
We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called Feasibility Pump, alternates between solving nonlinear programs and mixed integer linear programs. We also discuss how the algorithm can be iterated so as to improve the first solution it finds, as well as its integration within … Read more
We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in management and machine scheduling, and also appears as a subproblem in decomposition techniques for network design and other related problems. We present a new approach for determining facets of … Read more
The polyhedral homotopy method, which has been known as a powerful numerical method for computing all isolated zeros of a polynomial system, requires all mixed cells of the support of the system to construct a family of homotopy functions. Finding the mixed cells is formulated in terms of a linear inequality system with an additional … Read more