Reverse Search for Enumeration — Applications

• Biomechanics
• Chemistry
• Coding
• Control
• Decision
• Embedded systems
• Games
• Generating sets
• Graphs
• Integer and linear programming
• Linear algebra
• Linear systems
• Metabolic pathways
• Nash equilibria
• Optimization
• Point sets
• Robotics
• Tutte polynomials
• Visibility
• Wireless

Biomechanics

Valero-Cuevas et al. used reverse search for vertex enumeration to understand the mechanisms of human forefinger neuromuscular control. Reverse search was used to find all muscular excitation patterns from a biomechanical model for specific fingertip movements. The mechanical model was compared to actual muscle excitation patterns measured from fingertip tests.

McKay et al. hypothesized that cats preferentially use muscles producing large forces for postural control. Cats were subject to postural control tests, and the hindlimb position was measured. The observation was compared the feasible force set, determined by a biomechanical model of the muscles, which could be computed by reverse search vertex enumeration.

Chemistry

Ceder et al. used reverse search vertex enumeration to predict which face centered cubic superstructures can exist in three component alloys. Nearest neighbor and next nearest neighbor interactions define inequalities for the stable states of the system. The inequalities define hyperplanes; vertices of the polytope bounded by the hyperplanes correspond to ground states of the system.

Coding

Vontobel et al. used reverse search cone edge enumeration for the generation of pseudo-codewords, in an investigation of the properties of codes. Minimal pseudo-codewords of a code described by a parity-check matrix are the edges of a cone defined from that matrix.

Control

Shimizu and Furuta used reverse search vertex enumeration as part of an algorithm for finding the positively invariant with disturbance and input constraint (PIDIC) set for a given linear time-invariant discrete-time system. The PIDIC set is so defined that for any current state, inputs can be chosen so that regardless of the disturbances, the next state will still be within the set.

Curtis describes an algorithm for finding stabilizing, high performance control for nonlinear systems with polytopic bounded input, for which a control Lyapunov function is known. The intersection of the input polytope and the stabilizing set is found, its vertices enumerated by reverse search, and its parametrization found. From the parametrization, a control can be found which is optimum by some measure.

Geyer et al. use reverse search enumeration of hyperplane arrangements for the conversion of discrete hybrid automata (DHA) into equivalent piecewise affine systems (PWA). DHA are the connection of Switched Affine Systems (SAS), Finite State Machines (FSA), mode selector (MS) and an Event Generator (EG). An EG generates a logical signal which is an input to the FSA and the MS; the MS is then an input to the SAS. The EG is defined by linear constraints which define a hyperplane arrangement. By enumerating the cells of the hyperplane arrangment, the DHA can be expressed as an equivalent PWA; and can be extended for the composition of several DHA. The algorithm and related software related to DHA can be found in HYDSEL.

For some control systems, the entire state cannot be measured; observers are built to estimate the state. Dórea and Pimenta propose an algorithm for the design of estimators for linear discrete-time systems, which relies in part on vertex enumeration.

Fakhri used reverse search as part of an algorithm for finding a convex polytope P to seperate two non-convex sets S₁ and S₂, used in controller design for nonlinear systems. An orthogonal frame is chosen with random orientation; the upper and lower bounds of S₁ are found on the frame. From these bounds, half-spaces containing S₁ are found, and reverse search is used to enumerate the vertices of the polytope P formed by the intersection of the half-spaces. The polytope is then checked for containment in S₂; if not contained, the algorithm repeats, refining P.

Ho et al. showed that solving the complex PID stabilization problem can be reduced to a vertex enumeration, given complex polynomials and if certain conditions are met. For one fixed gain value, the other two stable gain values are defined by the feasible region of a set of linear inequalities, which can be enumerated by reverse search. The approach works for linear-time invariant systems and Lur'e systems.

Decision

Decision theory usually focuses on a single decision maker and is not suited to a competitive context; game theory assumes that the information about outcomes is known to all parties. Bullock et al. develop a method to use game theory models to solve decision theory questions. Using the value focused thinking technique (VFT), where values and objectives are articulated first, a game theory strategy is made for one party and estimated for the other, then the equilibria are solved by existing methods, eg. reverse search vertex enumeration.

Dias and Clímaco used reverse search for vertex enumeration to compute minimum ELECTRE credibility inidices when parameter values are only known within some range. The paramter ranges and their dependencies define a polytope; for some types of problems, it is easiest to enumerate the vertices of the polytope to find the minimum credibility index.

Liu presents three algorithms for psi-learning, determining a rule for classifying unseen events based on the classification of previous events. Psi-learning is most accurate as a minimization of a nonconvex cost function, and three algorithms are presented for the minimization. One builds nondecreasing outer approximations for cost function, until the error is bounded. Successive approximations are built by adding a constraint and enumerating vertices.

Mannino and Koushik used reverse search vertex enumeration for the construction of Vornoi diagrams, in finding an exact solution to the minimum-cost inverse classification problem. Rather than trying to classify a case, minimum-cost inverse classification finds the cost-minimizing change to the case so it falls into a preferred class. The exact solution is compared to a genetic algorithm derived.

Zhang and Gu used reverse search for vertex enumeration to detect network anomolies. Based on the support vector machine, they compute the convex hull of the training vectors for an SVM model, and compute the optimal hyperplane using the closest points on the convex hulls.

Embedded systems

Greenstreet and Mitchell present methods for verifying circuits modelled by systems of ODEs. Circuits verification is often a problem of reachability analysis, finding the state space of a circuit at discrete times, and all times between. For models which define non-convex polyhedra for state spaces, projections of the space are taken. An approximation of the space is taken by enumerating extremal vertices of the projection, eg by reverse search.

Balasa et al. used reverse search for vertex enumeration in finding the exact memory requirements for signal processing applications. From the high-level programming language description of the algorithm, index reference space is constructed. The size of the space is determined using reverse search.

Paul et al. used reverse search vertex enumeration as part of an algorithm to implement reconfiguration in FGPAs. FPGA are programmed by a bitstream, which can be intercepted, making the FPGA more vulnerable to attack. One method of protecting FPGAs is reconfiguration, changing the circuit without changing the functionality of the circuit. Retiming - a set of linear constraints on the configuration of the circuit with respect to the timing of the components - provides a set of transformations for parts of the circuit, and can be enumerated by reverse search.

Zhu et al. use reverse search vertex and ray enumeration in an algorithm to compute exactly the size requirements of multimedia processing algorithms. Loops in the algorithm are analyzed for their memory requirements, finding the iterator and index space for each signal. The iterator space is decomposed, by reverse search, into vertices and rays, as the first step in counting the number of lattice points within the space.

Zhao et al. use reverse search vertex enumeration for the creation of static resource models. Embedded systems use programmable processor, which can have irregular instruction sets, making code optimization difficult. The instruction set of the processor and the dataflow in the algorithm both define linear constraints. Optimization of the instruction set is reduced to a problem of vertex enumeration, while generation of virtual resources (sets of operations that can be done in parallel) is reduced to the convex hull.

Games

In the peg solitaire game, there exists a set of legal moves from a given start state to a given final state, if the difference of the final and start states (as vectors) are in the solitaire cone, defined by the legal moves on the board. Avis and Deza used lrs to enumerate the facets of the solitaire cone, for small board sizes. Later work enumerated the facets of the binary solitaire cone, the cone generated by the {0,1}-valued facets of the solitaire cone.

Generating sets

Hemmecke and Malkin present an algorithm for computing generating sets of lattice ideals, by computing in a projected subspace and lifting to a higher dimension. The generating set is built incrementally, until the intersection of the lattice generated by the set and the space of natural numbers is the null set, which can be checked by computing extreme rays by reverse search, among other methods.

Graphs

Lee and Margot present work on an ILP formulation for determining if a graph has an edge coloring. An edge coloring polytope of a graph is defined as a polytope where each vertex corresponds to an edge in the graph, and the coordinates of the vertex determine the coloring. For star graphs, each edge must have a different color, so each vertex must have unique coordinates. Algorithms for constructing linear inequality constraints are presented. One, for general block inequalities, uses reverse search to enumerate partitions of the polytope, which are then iterated over to determine inequalities.

Integer and linear programming

Halikas et al. used reverse search vertex enumeration planes to solve the reduced rank quadratic integer programming (RRQIP) problem. The solutions are used to derive upper bounds on the general quadratic integer programming problem.

Li and Ierapetritou presented a methodology for solving multiparametric mixed-integer linear programming problems. The algorithm solves multiparametric linear programming subproblems, finding the feasible region of the uncertain parameters, eg. by reverse search vertex enumeration.

Thoai uses reverse search vertex enumeration in an algorithm to compute a lower bound for general quadratic integer programming (QIP) problems. Vertices of a simplex containing all optimal solutions to a concave minimization are enumerated and checked for optimality. The simplex is reduced as suboptimal vertices are found. The lower bound computation is part of a branch-and-bound algorithm for solving a QIP problem.

Linear algebra

Corral presents a technique for finding a structured inverse of a matrix, using vertex enumeration. A structured inverse will result in some error. The structure of the inverse and bound on the error creates a set of halfspaces which define a polytope; the center of mass of the polytope corresponds to the inverse with minimum error. Center of mass is calculated by finding the sum of the equal weighting of the extreme points of the polytope, which are found by reverse search.

Linear systems

Dixon et al. use reverse search in their algorithm for finding the reachable set of an irreversible positive linear discrete dynamical system. In the algorithm, lrs is used to enumerate the edges of a cone constructed from the transition and control matrices.

Metabolic pathways

Larhlimi and Bockmayr used lrs, among other programs, to characterize metamobolic pathways according to their number of elementary flux modes, extreme pathways, and minimal metabolic behaviors. The stoichiometric matrix of a metabolic network defines the steady state flux cone; the flux cone is analyzed to characterize the metabolic behavior.

Nash equilibria

von Stengel used reverse search to enumerate Nash equilibria for bimatrix games, according to an algorithm for equilibria from Mangasarian. The payoff matrices and expected payoff vectors define two polyhedra; vertices are enumerated on each, and checked for being a completely labelled vertex, and thus an equilibrium.

Optimization

Arsham et al. present an algorithm for solving linearly constrained global optimization problems, in part based on reverse search. In the first step, critical points of the objective function are found; those in the feasible region are checked for maximality. In the next step, the vertext points of the feasible region are enumerated, by reverse search. In the last step, the critical points are found on the open domain of the feasible region. The function is evaluated at all these points, and the global solution is chosen.

Carraresi et al. present an algorithm for testing optimality of quadratic 0-1 programs, which in part relies on reverse search for vertex enumeration. At each iteration, the algorithm selects vertices of a parametric polytope and checks the solution for optimality; once all vertices are exhausted, a hyperplane is added to the polytope and the algorithm repeats.

Lewis and Torczon develop pattern search methods for linearly constrained minimization. Pattern search finds a minimum by calculating the objective function at a given distance from the starting point, in directions determined by the pattern; then recursing at the new point. If a lessor value cannot be found, the search distance is reduced. The pattern (set of directions for the search) is derived in part by reverse search veretex enumeration.

Point sets

Ambühl et al. used reverse search for finding the largest common point set between two point sets. Given two point sets and a group of transformations, the largest common point set is the set of points which can be matched with a set of transformations. A set of transformations corresponds to a hyperplane; by traversing all cells of the hyperplane arrangement, the graphs can be matched. The largest common point set is returned.

Robotics

Mosemann et al. implemented reverse search for vertex enumeration to determine stable orientations of assemblies. A linear program is written representing the contact points between parts of the assembly, and the gravity vector acting on the assembly is changed to consider all the stable directions. The range of stable orientations is integrated into the high level assembly planning system ^HighLAP.

Teichmann and Mishra present several algorithms for efficient grasping and fixturing. For one grasping problem (called MinCover-B) an object is represented by a set of points on the unit ball centered on the origin, and the algorithm returns the most efficient set of points to be used for grasping the object. In part of the algorithm, the facets of a random sample are enumerated by reverse search.

Zhu et al. used reverse search vertex enumeration as part of an algorithm for synthesizing robotic hand grasps on polygonal objects. They introduce a new quantitative measure of a grasp, and all grasps synthesized by the algorithm are constrained by the measure.

Tutte polynomials

Imai et al. used reverse search for enumeration of bases of linear matroids in an algorithm for finding the Tutte polynomial of a linear matroid. Internal and external activities of each base is found, from which the polynomial is computed.

Visibility

Bittner et al. used reverse search as part of an algorithm to determine visibility in urban scenes. To test for visibility of an object, a stabbing line is computed: a ray from the view cell, through virtual portal of the occluders between the view cell and the obect, to the object is computed. The computation itself is done in 5D, as the intersection point of 5D halfspaces, found by reverse search.

Wireless

Khan and Slock used zonotope enumeration for exact maximum likelihood decoding of MIMO (multiple input, multiple output) channels. The maximum likelihood function is shown to be maximal on the vertices of a zonotope; the vertices are enumerate by reverse search and each is checked for optimality.