Mixed-integer optimization

Table of Contents

• Building and solving simple models
• More advanced features
• Branch-and-bound algorithm
• Branch-and-price algorithm

Describes a collection of examples related to mixed-integer optimization.

Building and solving simple models

Example name	Description
lp-glpk	Models a simple linear problem and optimizes it with GLPK. If the is feasible, prints the primal and dual solution. If the model is infeasible, prints a Farkas certificate (dual ray). If the model is unbounded, prints a primal ray.
kp-highs	Models a simple binary knapsack problem and optimizes it with HiGHS. If the model is feasible, prints all solutions in the solution pool.
sos1-gurobi	Models a simple continuous problem and adds an SOS1 constraint. Then, uses Gurobi to optimize it and print the solution.
sudoku-cplex	Models and solves a sudoku using Cplex. Shows how to manipulate multi-dimensional variables.

More advanced features

Example name	Description
lp-dual	Models a simple LP and generates its dual. Solves the dual problem with HiGHS and prints, for each primal constraint, its associated dual variable with its value.

Branch-and-bound algorithm

Example name	Description
flp-bab	Models a capacitated facility location problem and solves it with idol's branch-and-bound algorithm. Each node is solved by GLPK. Reduced cost fixing is used.

Branch-and-price algorithm

Example name	Description
gap-bap	Solves the generalized assignment problem with idol's branch-and-price algorithm on its Dantzig-Wolfe reformulation.