Main News OPL MP CP JS Project Documentation Links FAQs

Frequently Asked Questions

Overview
1. What is jOpt?
2. What is OPL?
3. What can I do with jOpt?
4. How is jOpt designed?
5. How do the components of jOpt interact with each other?
6. I downloaded the source code; where do I start?

Constraint Logic Programming
7. What does the abbreviation CLP stand for?
8. What is Constraint Logic Programming?
9. What is the difference between constraint satisfaction and optimization?
10. What is a CSP solver?
11. How does jOpt's CSP solver work?
12. How does arc consistency work?
13. What types of constraints does the CSP solver support?
14. What makes this solver different than existing solutions?

Mathematical Programming
15. What does the abbreviation MP stand for?
16. What is Mathematical Programming?
17. What is Linear Programming?
18. What is Integer Programming?

Additional Information
19. What industries might benefit from jOpt?
20. Can you give an example problem that jOpt could solve?
21. Where can I find additional information about the technologies on which jOpt is based?
22. How can I get involved / get more information?




Overview

Q1. What is jOpt?
jOpt strives to be a fully functional implementation of the Optimization Programming Language (OPL) built using the Java programming language. The components within jOpt that are necessary to process OPL language statements are based largely on Operations Research (OR) and Artificial Intelligence (AI) technologies.

Q2. What is OPL?
OPL is a programming language created by Pascal Van Hentenryck . It provides a syntax allowing the definition of a problem model with the goal of assigning values to variables in the context of constraints that determine permissible values. The models consist primarily of variables, constraints to restrict values in the variables, and the ability to combine multiple AI / OR techniques to solve the problem.

OPL variables can be assigned either numeric or string values. The variables are initialized by declaring what values might be assigned to the variable such as "X can be assigned a value between 0 and 1 million".

Constraints can be defined on the variables such as "X + Y < 100" in order to restrict the values that may be assigned to the variable.

OPL also allows the developer to indicate whether all possible solutions to the problem should be determined or if a specific solution should be located. Specific solutions are requested by declaring a goal such as "maximize the value of Y".

While it is possible to create a piece of software from scratch in order to solve one (or even a small subset) of these problems, OPL provides a developer the ability to define a model without the need to write software to implement the solution. An OPL interpreter engine utilizes advanced techniques to solve the problem as defined by the developer. The developer can change and refine the model without worrying about constructing the underlying implementation.

OPL requires that the interpreting engine be capable of combining two advanced technologies known as Mathematical Programming and Constraint Logic Programming to solve the problems. The combination of these types of technologies provides developers an advanced tool for solving combinatorial optimization problems.

Q3. What can I do with jOpt?
jOpt will eventually provide an interpreter for the OPL language, but before this can be accomplished, the components that make up the foundation of the project must first be built.

The first component is the CSP solver that provides a simple, yet powerful framework (and accompanying implementation) for solving constraint satisfaction problems. The current CSP solver can be incorporated into Java applications independently (ie. without the other components of jOpt) and includes the necessary tools for modeling and solving.

The second component is the Scheduling solver, an extension of the CSP solver that specializes in Job Scheduling problems involving the assignment of resources to activities. When combined with the CSP solver, it, too, can be incorporated into Java applications independently.

Currently, the remaining components are still under development.

Q4. How is jOpt designed?
Four major components will provide the foundation for the OPL Engine:

1. OPL language parser - provides the lexical logic for parsing OPL language model requirements that will be sent to the solver components to find solutions

2. CSP solver - provides constraint logic programming functionality to solve constraint satisfaction problems. More information about this component can be found in the constraint logic programming section.

3. MP solver - provides mathematical programming functionality in order to solve linear and integer programming problems

4. Scheduling solver - a specialized extension of the CSP solver component that helps solve problems that are based on assigning resources to activities in the context of a schedule

Q5. How do the components of jOpt interact with each other?
This hasn't really been figured out yet :). The plan is for the interpreter engine to use the parser to understand the problem and then use the solver components to find solutions. The components are designed and built with their eventual need to interact in mind.

Q6. I downloaded the source code; where do I start?
Each component in the jOpt project includes an 'example' module containing, among other things, a StartHere class. Look there for a gentle introduction to the power of jOpt's components.




Constraint Logic Programming

Q7. What does the abbreviation CLP stand for?
CLP stands for Constraint Logic Programming (also commonly referred to as Constraint Programming). CLP typically deals with solving Constraint Satisfaction Problems (CSP).

Q8. What is Constraint Logic Programming?
"Constraint programming is a computer programming technique, with a name that is in the spirit of other programming techniques, such as object-oriented programming, functional programming, and structured programming" - Irvin Lusting, ILOG

The basics of constraint logic programming involve defining variables and constraints over the variables. CLP provides a way for users to create a program that will assign values to the variables in the context of constraints.

Q9. What is the difference between constraint satisfaction and optimization?
The difference between constraint satisfaction and optimization depends entirely on how the question is worded.

For example a question like "name one way you can make change for a dollar using quarters, dimes, and nickels" is an example of a constraint satisfaction problem. Similarly, "name all the ways you can make change for a dollar using quarters, dimes, and nickels" is a CSP.

On the other hand, if the problem was to "name the way you can make change for a dollar using quarters, dimes, and nickels that maximizes the number of quarters", you would have an optimization problem - the goal (maximizing or minimizing some criteria) makes a CSP a CSOP (Constraints Satisfaction Optimization Problem).

Q10. What is a CSP solver?
A CSP solver is a program that produces solutions to CLP problems. Different types of CSP solvers exist, but they all have some common features. A CSP solver provides a library that allows a user to define variables and constraints. While the specific types of variables and constraints that can be created vary from solver to solver, the intention of the solver is to produce a solution that assigns values to each variable in order to satisfy the constraints.

Q11. How does jOpt's CSP solver work?
jOpt's CSP solver is based on an artificial intelligence technique known as Arc Consistency that involves creating a graph of nodes and arcs from the user-defined variables and constraints, respectively. The node-arc graph is used to reduce the variable domains while maintaining consistency.

jOpt's solver supports different domain reduction algorithms with varying levels on consistency across a wide range of domain types (integer, float, etc.).

jOpt's solver also provides searching and local search utilities for exploring the search space in order to find valid solutions (assignments of values to variables) for CSPs.

Q12. How does arc consistency work?
Arc Consistency is based on the concept of a graph where every variable creates a node in the graph and the constraints create arcs that connect the nodes.

For example, variables X and Y would create two corresponding nodes in the graph. A constraint X + Y = 10 would create two arcs in the graph. The first arc based on the constraint is X = 10 - Y. This arc would be drawn from Y, the source, to X, the target. Similarly, a second arc, Y = X - 10, would be drawn from X to Y. The arcs indicate the dependencies between the nodes and can be traversed by an algorithm to ensure that all nodes are 'consistent' with each other.

When a variable is defined, the possible values that may be assigned to the variable are declared as well. For instance, X may be assigned a value between 1 and 10. When values are removed from a variable / node, the arcs originating from the node can be used to remove values from nodes targeted by the arcs. As other nodes are changed, they will propagate changes to other nodes. When no more changes are necessary, the variables are said to be 'consistent'.

Although consistency techniques can reduce possible values in a variable, it may not determine a specific value to assign to each variable. Therefore, the consistency technique is combined with searching algorithms in order to 'search' for the specific value to assign to each variable.

Q13. What types of constraints does the CSP solver support?
jOpt provides for the ability to define expressions and to create a wide array of constraints on those expressions.

For numeric expressions, jOpt's CSP solver supports all standard (+, -, /, *, ^, Σ, log, abs, etc.) and trigonometric (sin, cos, tan, arcsin, etc.) operations along with the standard relations including <, >, <=, >=, !=, and =. Also supported are 'global' constraints including allDifferent and cardinality constraints.

For boolean expressions, the CSP solver supports the And, Or, Xor, Not, Equals, and Implies relationships.

Set constraints such as Intersection (∩), Union (∪), Subset (⊆), Strict Subset (⊂), etc. are also provided.

While not created yet, jOpt has plans to allow constraints on user defined functions that can be used to convert numeric values to non-numeric values and vice versa.

Q14. What makes this solver different than existing solutions?
jOpt's CSP solver is similar to some commercial solutions such as ILOG and Koalog. However, it is built from the ground up using a design whose goal is to foster extension and stability of the product by making its technology open to everyone.




Mathematical Programming

Q15. What does the abbreviation MP stand for?
It stands for Mathematical Programming, which almost always elicits the next question ;) ...

Q16. What is Mathematical Programming?
The term programming in mathematical programming is often confusing for people who work with computers. The term traces its origins to the 1940s when the phrase "linear programming" was coined by a mathematician named George Dantzig. Danztig was describing some problems related to the US Defense Department's research into devising "programs" of activities for future conflicts. He called the problems "linear programs" and hence linear programming became associated with a particular type of mathematics problem. (see the link "Program Does Not Equal Program" on the links page for more info.)

As time went on, linear programming led to other types of "programming" including integer programming, quadratic problems, etc. Mathematical Programming covers all these problems.

Q17. What is Linear Programming?
Linear programming describes a type of mathematical problem in which all variables are part of linear polynomials.

A linear polynomial is a function that has a form similar to 1x + 15y + 3z = w. None of the variables can be raised to a power and no variables can be multiplied by other variables.

The simplex algorithm is a mathematical algorithm for solving a set of linear polynomial equations. The polynomials are defined using a set of variables and each equation represents a constraint. Another polynomial function can be used to define a goal (ie. maximize or minimize the expression).

The simplex algorithm is extremely efficient, but it has limitations. It can only solve problems where the constraints and the expression to maximize / minimize are linear. Also, it only produces real values so some additional work must be done to restrict variables to integer values (a common requirement for MP problems).

Q18. What is Integer Programming?
Integer programming is an extension of linear programming that handles finding solutions where variables must be in integer form. Techniques such as Branch-and-Bound or Cutting Plane are used to invoke a simplex algorithm over and over again until all variables in the problem are assigned to integer values.




Additional Information

Q19. What industries might benefit from jOpt technology?
Many industries including manufacturing, insurance, logistics, warehousing, retail, etc. can benefit from jOpt's technology. Many of these industries have constraint problems that could be solved by jOpt.

Q20. Can you give an example problem that jOpt could solve?
Packing problems:
Given the size of some items and restrictions on which items can be stored in the same box, jOpt could determine the best way to put the items in the boxes to minimize the number of boxes required.

Manufacturing:
Based on available raw materials and the amount of material required to produce each kind of product, jOpt could determine what products to create and how many of each product to produce to maximize income.

Airline Scheduling:
jOpt could be given input on crew abilities: medical knowledge, languages, training, etc. The input would also require knowledge of what planes were traveling to where, at what times, and restrictions on the number of hours each crew member may work. jOpt could ensure that crews would arrive near where their next flight would depart as well as ensure all required skill sets needed on a flight were provided by the crew assigned to the flight. It could also attempt minimize the staff needed while satisfying additional side constraints.

Puzzles and Games:
jOpt is also really good at solving several puzzles and games including Sudoku puzzles. An example of such is included in the CSP solver component.

Q21. Where can I find additional information about the technologies on which jOpt is based?
Our links page has many good references.

Q22. How can I get involved / get more information?
Please feel free to send an e-mail to cmj917@users.sourceforge.net or mystafer@users.sourceforge.net or post questions in our developers forum.