9
$\begingroup$

The problem I solved is a flow-shop scheduling problem with parallel machines.

I solved it with the IBM ILOG CPLEX Optimization framework. There I used the constraint programming (CP).

The question is now to what kind of field of operations research CP belongs, in particular the described flow-shop problem.

With the definition of some books and websites I thought that it would be part of linear optimization, in particular integer linear optimization.

But I'm not sure because I don't know if my problem can be formulated in a mathematical way, needed for linear optimization.

So can someone help me classify this?

$\endgroup$
  • 1
    $\begingroup$ Hi Tobias, and welcome to OR.SE. It's unclear what you are asking in your question. Are you asking how to classify CP within the hierarchy of OR and optimization? Or are you asking about your particular flow shop problem? $\endgroup$ – LarrySnyder610 Sep 6 '19 at 13:59
  • 1
    $\begingroup$ In my understanding constraint programming does not belong to mathematical modeling such as linear programming/optimization. These are two different methods that can have the same output. Linear programming is faster if you want to find an optimal solution and CP is faster if you want to find a feasible solution. Still you can use an objective function and maximize/minimize it with CP or use LP to find a feasible solution without the use of an objective function. $\endgroup$ – Georgios Sep 6 '19 at 14:08
  • 1
    $\begingroup$ @LarrySnyder610 the main quesetion is "how to classify CP within the hierarchy of OR and optimization". Since I think that the flow shop problem can be assigned to multiple fields it depends on how it is resolved? Or have I here a wrong understanding? $\endgroup$ – Tobias M. Sep 6 '19 at 14:47
11
$\begingroup$

In general, I think Constraint Programming or Constraint Satisfaction Problems have their roots in Computer Science/Artificial Intelligence communities that may or may not overlap to some extent with the Operations Research communities. According to "Artificial Intelligence, A Modern Approach" by Stuart Russel and Peter Norvig, an early example within computer of a specific constraint satisfaction problem was Sketchpad. That book furthermore notes that the idea that CSP's can be generalized came from a 1974 paper by Ugo Montanari in the journal Information Sciences.

Linear programming was developed earlier, mostly by mathematicians, as pure Computer Scientists did not even exist back then. Wikipedia mentions contributions from Kantovorich in 1939, and from Dantzig and Von Neumann in 1947.

Both approaches are quite different. Linear programming basically solves systems of linear equations. With this approach, it is typically difficult to obtain integral solutions, since in general we only know how to solve continuous problems efficiently. However, it is usually quite efficient to find optimal solutions for such continuous problems, and if we are lucky, those solutions are (close to some) integral solutions.

In Constraint Programming, you can imagine your variables to be nodes in a network with a discrete set of possible values, and the constraints as links between two or more variables/nodes. It performs a "clever" brute force technique: you can pick a constraint, and see if the sets of possible values in the variables affected by the constraint are compatible. For example, if for a variable $x$ we have $\{1,2,3\}$ as possible options, and for variable $y$ we have $\{2,3,4\}$ as possible options, the constraint $x+y\leq 4$ can be used to determine that $y$ can never become $4$, so it can be safely removed from $y$'s set of possible values. It performs guessing (what happens if I assume $x$ should be $2$?), backtracking and repeatedly using constraints to update the possible values of each variable (this is called constraint propagation). It aims to search for a feasible solution that satisfies all constraints, not necessarily an optimal one. If it turns out one of the sets of potential values for a variable becomes empty, it is clear you need to backtrack. The advantage of this approach is that you do not need all your constraints to be linear. In fact, as long as a constraint can be efficiently used to prune possible values from the variables it affects, it can get as crazy as you want, and this is why Constraint Programming typically offers greater modeling flexibility compared to linear programming. The downside is, however, that it is very hard to deal with continuous variables in a basic setup.

Note that the IBM ILOG CP Solver has many advanced features that seem to combine ideas from Constraint Programming and Linear Optimization, as it does allow optimization and, I believe, continuous variables.

$\endgroup$
  • 1
    $\begingroup$ reading your answer and all the others I can summaries that CP has some roots in linear programming but is releated much more in the field of AI. But with your note you hit the point that concerns me next. For me it at the moment hard to decide if IBM mix here between both worlds and then they are mixing how much? What percentage are then AI field and how much of the LP (OR) field? $\endgroup$ – Tobias M. Sep 10 '19 at 9:31
7
$\begingroup$

From a comment:

... the main question is "how to classify CP within the hierarchy of OR and optimization".

There's a useful graphic on IBM's webpage: "IT Best Kept Secret Is Optimization - Constraint Programming History" (Jan 21 2014), by Jean Francois Puget:

Paul Shaw and I were invited by John Poppelaars to give talks at the Back to School seminar of Dutch ORMS society. Part of our presentation was a brief history of constraint programming. We drafted this slide to summarize it:

Constraint Programming History Chart

... Its abstract is reproduced below, and the slides are available here (requires IBMid) [alternative source "Constraint Programming Background and History - LNMB" (.PDF) 35 pages].

Background and Theory of Constraint Programming
Jean-François Puget and Paul Shaw

This talk will review the principles and the historical roots of constraint programming (CP). Indeed, understanding the history behind this field helps understand the basic principles it is built on. CP can be traced back to a combination of Artificial Intelligence, Combinatorics (graph algorithms), and programming language design. It took two decades to unify these in a comprehensive and versatile framework shared by all modern CP tools and solvers. We'll review this framework and how it is implemented in recent tools. Last we will relate it and contrast it with mathematical programming.

The webpage link contains some additional unrelated (to the question) but interesting information. The blog: "Optimization Engines Make The Industry Efficient" (Aug 28 2018), by Diego explains the earliest history of CP:

In 1997 the Parrot project started with ILOG, Carmen Systems, Lufthansa and Olympic Airways.

The objective of the PARROT project is to provide efficient means to address the highly complex and costly problem of airline crew scheduling […] developing on promising results in the combination of Operations Research (OR) techniques and Constraint Programming (CP).

...

"I like to describe early Constraint Programming toolkits as “systems that help you write backtracking heuristics”

  • Prolog (Colmerauer, 1972) was a programming language that included an backtracking mechanism in its core
  • Alice (Laurière) 1976 was a “modern” constraint programming engine where you described your problem with equations and it would find the optimal solution for you
  • CHIP (Dincbas 1988) was an early commercial system based on Prolog
  • ILOG Solver (Puget 1994) was the first successful commercial system in C++ but was harder to use than a MIP engine".

Parrot Project: "Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search", in Annals of Operations Research 115(1):207-225, September 2002:

"We developed two different algorithms to tackle the large scale optimization problem;of Airline Crew Assignment. The first is an application of the Constraint Programming (CP) based Column Generation Framework. The second approach performs a CP based heuristic tree search. We present how both algorithms can be coupled to overcome their inherent weaknesses by integrating methods from Constraint Programming and Operations Research.".

$\endgroup$
6
$\begingroup$

Regarding your question “The question is now to what kind of field of operations research CP belongs”, I will say that CP is not a subfield of operations research, but it is another field, closely related to OR, but it is another field.

If you really like to understand the fundamental of Constraint (Logic) Programming, you should read the paper In Pursuit of the Holy Grail by Eugene C. Freuder, where in the abstract he writes:

Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it.

The main focus of CP is not on a specific single problem or a single class of problems, but it is the design of a very general declarative computer language that would permit to solve any problem that can be stated using that computer language, regardless of the techniques used inside the solver. For instances, the plot reported by @Rob presents several different computer languages for different CP solvers.

This is quite different from a mathematical programming approach, were the focus is on the problem you must (efficiently) solve. A mathematician would study the mathematical properties of the problem of interest, and then, she would try to exploit as much as possible the mathematical structure of the given problem to design an efficient solution algorithm (e.g., Linear Programming relies on the strong duality theorem).

Once say that, indeed, if you look at the programming techniques used internally by CP and/or MP solvers, there is a growing intersection of methods, and several researchers are trying to unify the two worlds. Just to mention two seminal references, you can look at:

  1. Looking at OR from CP: Logic-based Methods for Optimization, by John Hooker.
  2. Looking at CP from OR: Constraint Integer Programming, by Tobias Achterberg.

Finally, for looking deeper at the interplay between CP and OR, I would suggest to explore the proceeding of the CPAIOR Conference Series, where you can find several papers related to scheduling problems close to yours.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.