We discuss in this paper statistical inference of sample average approximations of multistage stochastic programming problems. We show that any random sampling scheme provides a valid statistical lower bound for the optimal value of the true problem. However, in order for such lower bound to be consistent one needs to employ the conditional sampling procedure. … Read more
Given a semi algebraic set S of R^n we provide a numerical approximation procedure that yields upper and lower bounds on mu(S), for measures mu that satisfy some given moment conditions. The bounds are obtained as solutions of positive semidefinite programs that can be solved via standard software packages like the LMI MATLAB toolbox. CitationAnnals … Read more
Many NP-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for many optimization … Read more
We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multi-stage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more … Read more
A new simple generalization of the Motzkin-Straus theorem for the maximum weight clique problem is formulated and directly proved. Within this framework a new trust region heuristic is developed. In contrast to usual trust region methods, it regards not only the global optimum of a quadratic objective over a sphere, but also a set of … Read more
Given two finite sets of points $X^+$ and $X^-$ in $\R^n$, the maximum box problem consists in finding an interval (“box”) $B=\{x : l \leq x \leq u\}$ such that $B\cap X^-=\emptyset$, and the cardinality of $B\cap X^+$ is maximized. A simple generalization can be obtained by instead maximizing a weighted sum of the elements … Read more
Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modeling ideas for each of the features of the problem, such as the handling of interference … Read more
In this paper we present a primal-dual inexact infeasible interior-point algorithm for semidefinite programming problems (SDP). This algorithm allows the use of search directions that are calculated from the defining linear system with only moderate accuracy, and our analysis does not require feasibility to be maintained even if the initial iterate happened to be a … Read more
The Fortran subroutine NLPQLP solves smooth nonlinear programming problems and is an extension of the code NLPQL. The new version is specifically tuned to run under distributed systems. A new input parameter l is introduced for the number of parallel machines, that is the number of function calls to be executed simultaneously. In case of … Read more
In multicriteria optimization, several objective functions have to be minimized simultaneously. For this kind of problem, no single solution can adequately represent the whole set of optimal points. We propose a new efficient method for approximating the solution set of a convex quadratic multiobjective programming problem. The method is based on a warm-start interior point … Read more