NobleBlocks

Research indexJournal article

A Dual-based Combinatorial Algorithm for Solving Cyclic Optimization Problems

Alfares

Recent Patents on Computer Science9 Dec 2012

NobleIDark:/48914/w1/20260515/EC0711C1DOI10.2174/2213275911205030188

Paywalled

The full text is at the publisher

You can read the abstract here, or open it at the publisher.

Read at the publisher

Abstract

This paper describes Patent Number U.S. 8,046,316 B2, titled “Cyclic Combinatorial Method and System”, issued by the US Patents and Trademarks Office on October 25, 2011. The patent is based on a combinatorial algorithm to solve cyclic optimization problems. First, the algorithm identifies cyclically distinct solutions of such problems by enumerating cyclically distinct combinations of the basic dual variables. In combinatorial terminology, this stage of the algorithm addresses the following question: given n cyclic objects, how many cyclically distinct combinations of m (m ≤ n) objects can be selected? Integrating the operations of partition and cyclic permutation, a procedure is developed for generating cyclically distinct selections (dual solutions). Subsequently, rules are described for recognizing the set of dominant solutions. Finally, primal-dual complementary slackness relationships are used to find the primal optimum solution. This patent has many potential applications in optimization problems with cyclic 0-1 matrices, such as network problems and cyclic workforce scheduling. The patent’s applicability has been illustrated by efficiently solving several cyclic labor scheduling problems. Keywords: Binary matrices, combinatorial algorithms, cyclic selection, cyclic scheduling, integer programming, optimization, BINARY OPTIMIZATION, CYCLIC OPTIMIZATION ALGORITHM, cyclic selection procedure, Cyclic Combinatorial Method

Discussion

Citations

Topics

More

Suggest a correction or report