Social and Behavioral Sciences Commons^™

Tight Representation Of Logical Constraints As Cardinality Rules, John Hooker, Hong Yan

John Hooker

We address the problem of finding a "tight" representation of complex logical constraints in a mixed integer programming model by describing a convex hull representation of cardinality rules.

Approximate Compilation Of Constraints Into Multivalued Decision Diagrams, Tarik Hadzic, John Hooker, Barry O'Sullivan, Peter Tiedemann

John Hooker

We present an incremental refinement algorithm for approximate compilation of constraint satisfaction models into multivalued decision diagrams (MDDs). The algorithm uses a vertex splitting operation that relies on detection of equivalent paths in the MDD. Although the algorithm is quite general, it can be adapted to exploit constraint structure by specializing the path equivalence test to particular constraints.We show how to modify the algorithm in a principled way to obtain an approximate MDD when the exact MDD is too large for practical purposes. This is done by replacing the equivalence test with a constraint-specific measure of distance. We demonstrate the …

Testing Heuristics: We Have It All Wrong, John Hooker

John Hooker

The competitive nature of most algorithmic experimentation is a source of problems that are all too familiar to the research community. It is hard to make fair comparisons between algorithms and to assemble realistic test problems. Competitive testing tells us which algorithm is faster but not why. Because it requires polished code, it consumes time and energy that could be better spent doing more experiments. This article argues that a more scientific approach of controlled experimentation, similar to that used in other empirical sciences, avoids or alleviates these problems. We have confused research and development; competitive testing is suited only …

Optimal Design Of Truss Structures By Logic-Based Branch And Cut, S. Bollapragada, Omar Ghattas, John Hooker

John Hooker

The truss design problem is to find the optimal placement and size of structural bars that can support a given load. The problem is nonlinear and, in the version addressed here, the bars must take certain discrete sizes. It is shown that a logic-based method that dispenses with integer variables and branches directly on logical disjunctions can solve substantially larger problems than mixed integer programming, even though the nonlinearities disappear in the mixed integer model. A primary purpose of the paper is to investigate whether advantages of logic-based branching that have been demonstrated elsewhere for linear problems extend to nonlinear …

Optimal Movement Of Factory Cranes, Ionuţ Aron, Latife Genç-Kaya, Iiro Harjunkoski, Samid Hoda, John Hooker

John Hooker

We study the problem of finding optimal space-time trajectories for two factory cranes or hoists that move along a single overhead track. Each crane is a assigned a sequence of pickups and deliveries at specified locations that must be performed within given time windows. The cranes must be operated so as not to interfere with each other, although one crane may need to yield to another. The objective is generally to follow a production schedule as closely as possible. We show that only certain types of trajectories need be considered to obtain an optimal solution. This simplifies the operation of …

Mixed Logical-Linear Programming, John Hooker, M. Osorio

John Hooker

Mixed logical/linear programming (MLLP) is an extension of mixed integer/linear programming (MILP). It can represent the discrete elements of a problem with logical propositions and provides a more natural modeling framework than MILP. It can also have computational advantages, partly because it eliminates integer variables when they serve no purpose, provides alternatives to the traditional continuous relaxation, and applies logic processing algorithms. This paper surveys previous work and attempts to organize ideas associated with MLLP, some old and some new, into a coherent framework. It articulates potential advantages of MLLP's wider choice of modeling and solution options and illustrates some …

Good And Bad Futures For Constraint Programming (And Operations Research), John Hooker

John Hooker

Two futures are sketched for constraint programming and operations research. In one, they continue their present emphasis on computational methods. In the other, they are empirical sciences dedicated to prescriptive modeling of human activities, with computation playing an ancillary role. The second future is defended as one in which the two fields, which are at root one field, maintain their vitality and make a more effective contribution to solving the problems of an increasingly complex world.

A Linear Programming Framework For Logics Of Uncertainty, K. Andersen, John Hooker

John Hooker

Several logics for reasoning under uncertainty distribute “probability mass” over sets in some sense. These include probabilistic logic, Dempster-Shafer theory, other logics based on belief functions, and second-order probabilistic logic. We show that these logics are instances of a certain type of linear programming model, typically with exponentially many variables. We also show how a single linear programming package can implement these logics computationally if one “plugs in” a different column generation subroutine for each logic, although the practicality of this approach has been demonstrated so far only for probabilistic logic.

Simpl: A System For Integrating Optimization Techniques, Ionuţ Aron, John Hooker, Tallys Yunes

John Hooker

In recent years, the Constraint Programming (CP) and Operations Research (OR) communities have explored the advantages of combining CP and OR techniques to formulate and solve combinatorial optimization problems. These advantages include a more versatile modeling framework and the ability to combine complementary strengths of the two solution technologies. This research has reached a stage at which further development would benefit from a general-purpose modeling and solution system. We introduce here a system for integrated modeling and solution called SIMPL. Our approach is to view CP and OR techniques as special cases of a single method rather than as separate …

A Framework For Integrating Solution Methods, John Hooker

John Hooker

We describe a modeling framework that integrates mathematical programming (MP), constraint programming (CP) and heuristic methods.

Corruption From A Cross-Cultural Perspective, John Hooker

John Hooker

This paper views corruption as activity that tends to undermine a cultural system. Because cultures operate in very different ways, different activities are corrupting in different parts of the world. The paper analyzes real-life situations in Japan, Taiwan, India, China, North America, sub-Saharan Africa, the Middle East, and Korea to distinguish actions that structurally undermine a cultural system from those that are merely inefficient or are actually supportive. Activities such as nepotism or cronyism that are corrupting in the rule-based cultures of the West may be functional in relationship-based cultures. Behavior that is normal in the West, such as bringing …

Solving The Incremental Satisfiability Problem, John Hooker

John Hooker

Given a set of clauses in propositional logic that have been found satisfiable, we wish to check whether satisfiability is preserved when the clause set is incremented with a new clause. We describe an efficient implementation of the Davis-Putnam-Loveland algorithm for checking the satisfiability of the original set. We then show how to modify the algorithm for efficient solution of the incremental problem, which is NP-complete. We also report computational results.

Resolution And The Integrality Of Satisfiability Problems, John Hooker

John Hooker

No abstract provided.

Logic-Based Benders Decomposition, John Hooker, G. Ottosson

John Hooker

Benders decomposition uses a strategy of “learning from one’s mistakes.” The aim of this paper is to extend this strategy to a much larger class of problems. The key is to generalize the linear programming dual used in the classical method to an “inference dual.” Solution of the inference dual takes the form of a logical deduction that yields Benders cuts. The dual is therefore very different from other generalized duals that have been proposed. The approach is illustrated by working out the details for propositional satisfiability and 0-1 programming problems. Computational tests are carried out for the latter, but …

Some Business-Related Ethical Issues In Engineering, John Hooker

John Hooker

Engineering has always been related to business, but now more than ever. Engineers are increasingly involved in startup companies in which they make business decisions as well as engineering decisions. Even in large firms, highly integrated product development cycles bring engineers into closer contact with marketing and other business people than in years past. Engineers must now think about ethical issues that were once the province of business managers. In addition, the rapid growth of biotechnology and e-commerce has created a new ethical landscape in which engineers must operate.

The aim here is to examine a few of the issues …

Mixed Global Constraints And Inference In Hybrid Clp-Ip Solvers, Greger Ottosson, Erlendur Thorsteinsson, John Hooker

John Hooker

The complementing strengths of Constraint (Logic) Programming (CLP) and Mixed Integer Programming (IP) have recently received significant attention. Although various optimization and constraint programming packages at a first glance seem to support mixed models, the modeling and solution techniques encapsulated are still rudimentary. Apart from exchanging bounds for variables and objective, little is known of what constitutes a good hybrid model and how a hybrid solver can utilize the complementary strengths of inference and relaxations. This paper adds to the field by identifying constraints as the essential link between CLP and IP and introduces an algorithm for bidirectional inference through …

Business Ethics As Rational Choice, John Hooker

John Hooker

No abstract provided.

Working Across Cultures, John Hooker

John Hooker

No abstract provided.

Logic-Based Methods For Optimization: Combining Optimization And Constraint Satisfaction, John Hooker

John Hooker

No abstract provided.

Optimization Methods For Logical Inference, Vijay Chandru, John Hooker

John Hooker

No abstract provided.