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 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
We study the multiple-sets split feasibility problem that requires to find a point closest to a family of closed convex sets in one space such that its image under a linear transformation will be closest to another family of closed convex sets in the image space. By casting the problem into an equivalent problem in … Read more
We present a target-following framework for semidefinite programming, which generalizes the target-following framework for linear programming. We use this framework to build weighted path-following interior-point algorithms of three distinct flavors: short-step, predictor-corrector, and large-update. These algorithms have worse-case iteration bounds that parallel their counterparts in linear programming. We further consider the problem of finding analytic … Read more
Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem’s functions can be improved by performing a nonsingular linear transformation in the space corresponding … Read more
Traditional models of decision-making under uncertainty assume perfect information, i.e., accurate values for the system parameters and specific probability distributions for the random variables. However, such precise knowledge is rarely available in practice, and a strategy based on erroneous inputs might be infeasible or exhibit poor performance when implemented. The purpose of this tutorial is … Read more
Support Vector Machine has shown to have good performance in many practical classification settings. In this paper we propose, for multi-group classification, a biobjective optimization model in which we consider not only the generalization ability (modelled through the margin maximization), but also costs associated with the features. This cost is not limited to an economical … Read more
We propose a novel solution approach for polynomial programming problems with equality constraints. By means of a generic transformation, we show that solution schemes for the (typically simpler) problem without equalities can be used to address the problem with equalities. In particular, we propose new solution schemes for mixed binary programs, pure 0-1 quadratic programs, … Read more
We implement several warm-start strategies in interior-point methods for linear programming (LP). We study the situation in which both the original LP instance and the perturbed one have exactly the same dimensions. We consider different types of perturbations of data components of the original instance and different sizes of each type of perturbation. We modify … Read more