Column Generation

Our core technology for producing real-world scheduling solutions is column generation. GENCOL (GÉNération de COLonnes) embodies the principles of the column generation method developed to solve large-scale complex problems. Column generation is an optimization strategy that allows one to implicitly consider a huge number of variables by using a mathematical component called the generator.

The column generator (or sub problem) shares information with what is usually referred to as the master problem, and together these components drive optimization to optimality. Together with other robust optimization algorithms, the GENCOL optimizer provides significant advantages in both economic and human terms.

Award-winning technology

The brainchild of researchers Jacques Desrosiers and François Soumis, GENCOL and its researchers have received many prestigious honors — namely, the Canadian Operational Research Society (1994 and 1996), the Operational Research Society of America (1986) and the European Association of Operations Research (1983).

Dynamic programming

Our column generator is built around a shortest path with resource constraints algorithm. This type of mathematical tool is very powerful yet difficult to master. Harnessing the power of such a tool is definitely one of the strengths in Altitude solutions.

Cplex, ACCPM

Our master problem component is generic and allows Altitude to easily use different engines to produce the dual information needed by the generator. In many cases, Cplex engines are used but we also use heuristics and are currently working in collaboration with GERAD on a solver designed especially for column generation.

Branch and cut/bound

Because column generation does not produce integer solutions, our column generation scheme is embedded in a branch and cut/bound framework. The framework defines an interface to branching "methods" that compete to make fractional solutions more integral. Each method evaluates what it can do on a given relaxed problem and the best one gets to modify the problem. Several search strategies are available and we have proven to be very innovative in this area of research.

Business logic unified engine

One of the newest operations research developments is the business logic unified engine (BLUE). Based on an efficient in-house programmed interpreter of the LISP family of languages, the BLUE rule engine is already playing an important role in the evaluation of bids and schedules and even schedule construction within Altitude PBS.

More than a rule engine, Altitude BLUE allows us to go one step further in the evolution of our optimization products, from a parameterized environment to a functional programming environment. Learn more about Altitude BLUE.