In this paper, we derive new families of piecewise linear facet-defining inequalities for the finite group problem and extreme inequalities for the infinite group problem using approximate lifting. The new valid inequalities for the finite group problem are two- and three-slope facet-defining inequalities as well as the first family of four-slope facet-defining inequalities. The new … Read more
This paper introduces the single item lot sizing problem with inventory gains. This problem is a generalization of the classical single item capacitated lot sizing problem to one in which stock is not conserved. That is, the stock in inventory undergoes a transformation in each period that is independent of the period in which the … Read more
The task of scheduling communications between satellites and ground control stations is getting more and more critical since an increasing number of satellites must be controlled by a small set of stations. In such a congested scenario, the current practice, in which experts build hand-made schedules, often leaves a large number of communication requests unserved. … Read more
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