Search

We consider in this paper quadratic programming problems with cardinality and minimum threshold constraints that arise naturally in various real-world applications such as portfolio selection and subset selection in regression. This class of problems can be formulated as mixed-integer 0-1 quadratic programs. We propose a new semidefinite program (SDP) approach for computing the 'best' diagonal decomposition that gives the tightest continuous relaxation of the perspective reformulation of the problem. We also give an alternative way of deriving the perspective reformulation by applying a special Lagrangian decomposition scheme to the diagonal decomposition of the problem. This derivation can be viewed as a 'dual' method to the convexification method employing the perspective function on semicontinuous variables. Computational results show that the proposed SDP approach can be advantageous for improving the performance of mixed-integer quadratic programming solvers when applied to the perspective reformulations of the problem. Keywords: quadratic programming with semicontinuous variables and cardinality constraint; perspective reformulation; diagonal decomposition; semidefinite program; Lagrangian decomposition History: Accepted by Karen Aardal, Area Editor for Design and Analysis of Algorithms; received January 2012; revised November 2012, September 2013; accepted December 2013. Published online in Articles in Advance May 19, 2014., 1. Introduction 1.1. Problem and Background We consider in this paper the following cardinality constrained quadratic programs: (P) min q(x) := [x.sup.T] Qx + [c.sup.T] x s.t. Ax< ≤ b, [...]

We discuss the method recently proposed by S. Chubanov [Chubanov S (2012a) A strongly polynomial algorithm for linear systems having a binary solution. Math. Programming 134(3)533-570] for the linear feasibility problem. We present new, concise proofs and geometric interpretations of some of his results. From our ideas we derive the first strongly polynomial time algorithm based on relaxation method techniques for special classes of linear feasibility problems. Under certain conditions, these results provide new proofs of classical results obtained by Tardos for combinatorial linear programs. The paper ends with some experimental investigations. Keywords: linear programming; relaxation methods; strongly polynomial time algorithms, 1. Introduction In their now classical papers, Agmon (1954) and Motzkin and Schoenberg (1954) introduced the so called relaxation method to determine the feasibility of a system of linear inequalities [...]

In this paper, we deal with a column generation-based algorithm for the classical cutting stock problem. This algorithm is known to have convergence issues, which are addressed in this paper. [...]

This paper develops algorithms for finding Coxian generators to phase-type (PH)-majorize a PH-generator T with only real eigenvalues. In the first part of this paper, we investigate matrices S and [...]

This paper presents a parallel branch-and-bound method to address the two-dimensional rectangular guillotine strip cutting problem. Our paper focuses on a parallel branching schema. We present a series of computational [...]

1. Introduction Edge finding (Carlier and Pinson 1994) is a fundamental pruning technique for disjunctive and cumulative scheduling (this paper considers only nonpreemptive problems, where tasks cannot be interrupted) and […], The introduction of edge-finding techniques was a significant development in constraint-based scheduling. Today, edge finders are still the state of the art in the disjunctive case and a technique of interest in cumulative scheduling. This paper reconsiders edge-finding algorithms for cumulative scheduling and shows that Nuijten's edge finder, and its derivatives, are incomplete because they use an invalid dominance rule. We then present a correct cumulative edge finder running in time O([n.sup.2]k), where n is the number of tasks and k the number of different capacity requirements of the tasks. The new algorithm is organized in two phases and first uses dynamic programming to precompute the innermost maximization in the edge-finder specification. The paper also proposes the first extended edge-finding algorithms that run in time O([n.sup.2]k), improving the running time of available algorithms. Finally, the paper discusses how to speed up the algorithm in practice and how the first phase can be used to improve algorithms based on energetic reasoning. Key words: constraint based scheduling; cumulative resources; edge finding

In this paper, we consider a finite-buffer [M.sup.X]/[G.sup.Y]/1/K + B queue with setup times, which has a wide range of applications. The primary purpose of this paper is to discuss […]

A number of papers have appeared recently using eigenvalues for solving steady-state queueing problems. In this paper, we analyze Markovian systems with two state variables, the level [X.sub.1] and the […]

Abstract. In this paper, we propose the continuous variable neighborhood search method for finding all the solutions to a nonlinear system of equations (NSEs). We transform the NSE problem into [...]

Abstract. In this paper, we present a method for comparing and evaluating different collections of machine learning algorithms on the basis of a given performance measure (e.g., accuracy, area under [...]

Abstract. Preferences provide a means for specifying the desires of a decision maker (DM) in a declarative way. In this paper, based on a DM's pairwise preferences, we infer the [...]

Abstract. In this paper, we study a revenue management model over a single flight leg, where the customers are allowed to lock an available fare. Each customer arrives into the [...]

Abstract. In this paper, I view and present the multiobjective discrete optimisation problem as a particular case of disjunctive programming where one seeks to identify efficient solutions from within a [...]

Abstract. This paper presents a new local search approach, called randomized decomposition (RD), for solving nonlinear, nonconvex mathematical programs. Starting from a feasible solution, RD partitions the problem's decision variables [...]

Abstract. Stochastic kriging (SK) and stochastic kriging with gradient estimators (SKG) are useful methods for effectively approximating the response surface of a simulation model. In this paper, we show that [...]

Abstract. This paper proposes a simulated annealing variant for optimization problems in which the solution quality can only be estimated by sampling from a random distribution. The aim is to [...]

Abstract. In this paper, we extend a recently proposed scenario decomposition algorithm for risk-neutral 0-1 stochastic programs to the risk-averse setting. Specifically, we consider two-stage risk-averse 0-1 stochastic programs with [...]

Abstract. In this paper, we present examples of a class of Markov chains that occur frequently, but whose associated matrices are a challenge to construct efficiently. These are Markov chains [...]

Abstract. This paper studies multilevel uncapacitated p-location problems, a general class of facility location problems. We use a combinatorial representation of the general problem where the objective function satisfies the [...]

Abstract. In this paper, we propose a new methodology for the speed-scaling problem based on its link to scheduling with controllable processing times and submodular optimization. It results in faster [...]

Abstract. In this paper, a heuristic procedure is proposed for the facility location problem with general Bernoulli demands. This is a discrete facility location problem with stochastic demands that can [...]

Abstract. This paper presents a novel and computationally efficient methodology for approximating the queue length (the number of customers in the system) distributions of time-varying non-Markovian many-server queues (e.g., [G.sub.t]/[G.sub.t]/ [...]

Abstract. This paper presents a new model for online decision making. Motivated by the healthcare delivery application of dynamically allocating patients to procedure rooms in outpatient procedure centers, the online [...]

The INFORMS Journal on Computing (JOC) is a quarterly journal that publishes papers the intersection of operations research (OR) and computer science (CS). Most papers contain original research, but we […]

Abstract. In this paper, we use a branch decomposition technique to improve approximations to the p-median problem. Starting from a support graph produced either by a combination of heuristics or [...]

Abstract. In this paper we demonstrate how a key adjustment to known numerically exact methods for evaluating time-dependent moments of the number of entities in the [Ph.sub.t]/[Ph.sub.t]/[infinity] queueing system and [...]

Abstract. This paper presents an algorithmic strategy to nonstationary policy search for finite-horizon, discrete-time Markovian decision problems with large state spaces, constrained action sets, and a risk-sensitive optimality criterion. The [...]

Abstract. In this paper, we study a multisourcing supply network design problem, in which each retailer faces uncertain demand and can source products from more than one distribution center (DC). [...]

This paper examines a class of three-stage sequential defender-attacker-defender problems. In these problems the defender first selects a subset of assets to protect, the attacker next damages a subset of [...]

We present in this paper a new generic approach to variable branching in branch and bound for mixedinteger linear problems. Our approach consists in imitating the decisions taken by a [...]

This paper presents a new methodology for university exam timetabling problems, which draws upon earlier work on the Great Deluge metaheuristic. The new method introduces a 'flexible' acceptance condition. Even [...]

This paper addresses the close-enough traveling salesman problem. In this problem, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve [...]

In this paper, stochastic kriging (SK) is considered as a metamodeling tool to capture risk-related properties of complex stochastic system outputs. To better assess the tail behavior of the underlying [...]

In this paper, we propose and analyze a distributed negotiation strategy for a multi-agent, multi-attribute negotiation in which the agents have no information about the utility functions of other agents. [...]

This paper introduces a novel class of generalized assignment problems with location/allocation considerations that arises in several applications including retail shelf space allocation. We consider a set of items where [...]

In this paper we propose a methodology for constructing decision rules for integer and continuous decision variables in multiperiod robust linear optimization problems. This type of problem finds application in, [...]

In this paper we derive and exploit duality in general two-stage adaptive linear optimization models. The equivalent dualized formulation we derive is again a two-stage adaptive linear optimization model. Therefore, [...]

This paper presents an efficient algorithm for an integrated operating room planning and scheduling problem. It combines the assignment of surgeries to operating rooms and scheduling over a short-term planning [...]

This paper presents a branch-and-price approach to solve personalized tour-scheduling problems in a multiactivity context. Two formulations are considered. In the first, columns correspond to daily shifts that are modeled [...]

The consistency between review summaries and review ranking lists is important for consumers so they can utilize online reviews effectively and efficiently in their purchase decisions. This paper examines this [...]

In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective [...]

This paper considers the minimum k-connected d-dominating set problem, which is a fault-tolerant generalization of the minimum connected dominating set (MCDS) problem. Three integer programming formulations based on vertex cuts [...]

This paper explores techniques for solving the maximum clique and vertex coloring problems on very large-scale real-life networks. Because of the size of such networks and the intractability of the [...]

This paper presents a solution scheme for a class of multistage stochastic programs (possibly mixed-integer at all stages) in which a hierarchy of decisions emerges. A special structure, common to [...]

In this paper, a cutting-plane neighborhood structure is proposed for the fixed-charge capacitated multicommodity network design (CMND) problem. In the proposed structure, different strategies are used to select an open [...]

In this paper, we extend our former investigation on conceiving reliable fixed point-to-point wireless networks under outage probability constraints. We consider the problem of determining the minimum cost bandwidth assignment [...]

Estimating the sensitivities of portfolio credit risk with respect to the underlying model parameters is an important problem for credit risk management. In this paper, we consider performance measures that [...]

This paper proposes a heuristic for districting problems arising in an arc routing context. The aim is to design districts by amalgamating edges of a graph as opposed to cells. [...]

In this paper, we study whether cuts obtained from two simplex tableau rows at a time can strengthen the bounds obtained by Gomory mixed-integer (GMI) cuts based on single tableau [...]

Determination of a protein's structure can facilitate an understanding of how the structure changes when that protein combines with other proteins or smaller molecules. In this paper we study a [...]