Building separating concentric balls to solve a multi-instance classification problem

In this work, we consider a classification problem where the objects to be classified are bags of instances which are vectors measuring d different attributes. The classification rule is defined in terms of a ball, whose center and radius are the parameters to be computed. Given a bag, it is assigned to the positive class … Read more

Kernel Support Vector Regression with imprecise output

We consider a regression problem where uncertainty affects to the dependent variable of the elements of the database. A model based on the standard epsilon-Support Vector Regression approach is given, where two hyperplanes need to be constructed to predict the interval-valued dependent variable. By using the Hausdorff distance to measure the error between predicted and … Read more

Fast Local Search for the Maximum Independent Set Problem

Given a graph G = (V,E), the independent set problem is that of finding a maximum-cardinality subset S of V such that no two vertices in S are adjacent. We introduce two fast local search routines for this problem. The first can determine in linear time whether a maximal solution can be improved by replacing … Read more

Efficient implementations of heuristics for routing and wavelength assignment

The problem of Routing and Wavelength Assignment in Wavelength Division Multiplexing (WDM) optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned to different wavelengths. When the objective is to minimize the total number of wavelengths used, … Read more

Hilbert’s Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm … Read more

Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes

This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with … Read more

Numerical Study of Affine Supply Function Equilibrium in AC Network-Constrained Markets

An affine supply function equilibrium (SFE) approach is used to discuss voltage constraints and reactive power issues in the modeling of strategic behavior. Generation companies (GenCos) can choose their bid parameters with no restrictions for both energy and spinning reserves. The strategic behavior of generators is formulated as a multi-leader single-follower game. Each GenCo is … Read more

Formulation of Oligopolistic Competition in AC Power Networks: An NLP Approach

In this paper, oligopolistic competition in a centralized power market is characterized by a multi-leader single-follower game, and formulated as a nonlinear programming (NLP) problem. An AC network is used to represent the transmission system and is modeled using rectangular coordinates. The follower is composed of a set of competitive suppliers, demands, and the system … Read more

Probing the Pareto frontier for basis pursuit solutions

The basis pursuit problem seeks a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise (BPDN) fits the least-squares problem only approximately, and a single parameter determines a curve that traces the optimal trade-off between the least-squares fit and the one-norm of the solution. We prove that this curve is convex and continuously … Read more

MOST – Multiple Objective Spanning Trees Repository Project

This article presents the Multiple Objective Spanning Trees repository – MOST – Project. As the name suggests, the MOST Project intends to maintain a repository of tests for the MOST related problems, mainly addressing real-life situations. MOST is motivated by the scarcity of repositories for the problems in the referred field. This entails difficulty in … Read more