GCG#

GCG is a generic decomposition solver for mixed-integer programs (MIPs). It automatically performs a Dantzig-Wolfe reformulation and runs a full-fledged branch-price-and-cut algorithm to solve it to optimality. Alternatively, GCG is able to automatically apply a Benders decomposition. No user interaction is necessary, thus GCG provides decomposition-based MIP solving technology to everyone.

Learn More | GCG modeling guide | Features | Options | Changes

Download GCG

How to use it#

How to install using amplpy:

# Install Python API for AMPL:
$ python -m pip install amplpy --upgrade

# Install AMPL & solver modules:
$ python -m amplpy.modules install gcg # install GCG

# Activate your license (e.g., free ampl.com/ce or ampl.com/academia licenses):
$ python -m amplpy.modules activate <your-license-uuid>

How to use:

from amplpy import AMPL
ampl = AMPL()
...
ampl.solve(solver="gcg", gcg_options="option1=value1 option2=value2")

Learn more about what we have to offer to implement and deploy Optimization in Python.

AMPL APIs give access to AMPL from a programming language:

ampl: option solver gcg; # change the solver
ampl: option gcg_options 'option1=value1 option2=value2'; # specify options
ampl: solve; # solve the problem

Resources#

Features#

Problem types and algorithms#

Problem types

  • LP

  • MILP

Received natively: linear constraints and ranges. GCG does not accept quadratic objectives: quadratic and nonlinear terms are approximated piecewise-linearly; logical constraints become big-M rows. Decomposition applies to MIP models.

All constructs: native constraints and expressions by driver.

Dantzig-Wolfe and Benders decomposition

gcg:mode: 0 Dantzig-Wolfe with branch-price-and-cut (default), 1 Benders, 2 no decomposition. Detection of the structure: det:... options; see the GCG modeling guide.

Instrumentation#

For a generic summary of the options and features used most often, see Important features in the MP documentation.

For all models

Model export

Option tech:writemodel. Details

Solution export

Option tech:writesolution. Details

Multiple solutions

Option sol:stub. Details

Multiple objectives

Emulated by MP. Option obj:multi. Details

For MIP models

MIP gap

Option mip:return_gap. Details

Best dual bound

Option mip:bestbound. Details

GCG modeling guide#

GCG can apply Dantzig-Wolfe or Benders decomposition, either automatically or user-controlled, see types of structures GCG can detect and AMPL/GCG Colab examples.

Moreover, AMPL logical and some nonlinear expressions can be automatically linearized by the driver, see MP modeling guide.

Solver options#

Full list of solver options:

More details on solver options: MP solver options.

Retrieving solutions#

The outcome of the last optimization is stored in the AMPL parameter solve_result_num and the relative message in solve_result.

display solve_result_num, solve_result;

GCG solve result codes can be obtained by running gcg -! or ampl: shell "gcg -!";:

Solve result table for GCG 4.0.2
          0- 99 solved: optimal for an optimization problem,
                feasible for a satisfaction problem 
        100-199 solved? solution candidate returned but error likely 
            150 solved? MP solution check failed (option sol:chk:fail) 
        200-299 infeasible 
        300-349 unbounded, feasible solution returned 
        350-399 unbounded, no feasible solution returned 
        400-449 limit, feasible: stopped, e.g., on iterations or Ctrl-C 
        450-469 limit, problem is either infeasible or unbounded.
                Disable dual reductions or run IIS finder for definitive answer.
        470-499 limit, no solution returned 
        500-999 failure, no solution returned 
            550 failure: numeric issue, no feasible solution
Solve result codes of the gcg-cpx driver
Solve result table for GCG 4.0.0
          0- 99 solved: optimal for an optimization problem, feasible for a satisfaction problem 
        100-199 solved? solution candidate returned but error likely 
            150 solved? MP solution check failed (option sol:chk:fail) 
        200-299 infeasible 
        300-349 unbounded, feasible solution returned 
        350-399 unbounded, no feasible solution returned 
        400-449 limit, feasible: stopped, e.g., on iterations or Ctrl-C 
        450-469 limit, problem is either infeasible or unbounded 
        470-499 limit, no solution returned 
        500-999 failure, no solution returned 
            550 failure: numeric issue, no feasible solution

For general information, see MP result codes guide.

Changelog#