Stochastic programming with step decision rules, SPSDR, is an attempt to overcome the curse of computational complexity of multistage stochastic programming problems. SPSDR combines several techniques. The first idea is to work with independent experts. Each expert is confronted with a sample of scenarios drawn at random from the original stochastic process. The second idea … Read more
The traffic assignment problem with elastic demands can be formulated as an optimization problem, whose objective is sum of a congestion function and a disutility function. We propose to use a variant of the Analytic Center Cutting Plane Method to solve this problem. We test the method on instances with different congestion functions (linear with … Read more
We show that the problem of computing sharp upper and lower static-arbitrage bounds on the price of a European basket option, given the prices of other similar options, can be cast as a linear program (LP). The LP formulations readily yield super-replicating (sub-replicating) strategies for the upper (lower) bound problem. The dual counterparts of the … Read more
Wavelet decomposition problems have been modeled as linear programs – but only as extremely dense problems. Both revised simplex and interior point methods have difficulty with dense linear programs. The question then is how to get around that issue. In our experiments the standard method outperforms a revised implementation for these problems. Moreover, the standard … Read more
An explicit description of the convex hull of solutions to the uncapacitated lot-sizing problem with backlogging, in its natural space of production, setup, inventory and backlogging variables, has been an open question for many years. In this paper, we identify facet-defining inequalities that subsume all previously known valid inequalities for this problem. We show that … Read more
We consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution … Read more
We derive a robust primal-dual interior-point algorithm for a semidefinite programming, SDP, relaxation for sensor localization with anchors and with noisy distance information. The relaxation is based on finding a Euclidean Distance Matrix, EDM, that is nearest in the Frobenius norm for the known noisy distances and that satisfies given upper and lower bounds on … Read more
In this paper we extend in a simple way the transformation of Charnes and Cooper to the case where the functional ratio to be considered are of similar polynomial CitationUniversidad de San Luis Ejercito de Los Andes 950 San Luis(5700) ArgentinaArticleDownload View PDF
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