LP relaxation versus integer optimum: an integer programming example, solved and checked
The LP relaxation versus integer optimum is a classic integer programming problem. Here it is solved by a real solver (HIGHS) and checked: every constraint, the dual, and the optimality certificate. Change the numbers below and solve your own.
Solve your own version free, no account needed
The problem
maximize x + y
subject to
2x + 2y <= 3
x, y >= 0
integer: x, y
How the model was built
The objective as written from the problem, before the numbers are multiplied out:
- Without the integer rule the best value would be 1.5 (any point on the line x + y = 1.5). Whole numbers can only reach 1, so here the integer optimum is 0.5 below the LP relaxation's bound.
The model
Each line has a plain-language note on the right.
| make as large as possible: sum of x and y (units) | |
| limit 1: left side cannot exceed 3 | |
| first decision variable (units) cannot be negative | |
| second decision variable (units) cannot be negative | |
| whole numbers only |
In matrix form
With its numbers:
What is being decided
There are 2 decision variables.
| Variable | Type | Meaning |
|---|---|---|
| x | integer | first decision variable (units) |
| y | integer | second decision variable (units) |
Goal and limits
Maximize sum of x and y (units) subject to 3 constraints, of which 2 are simple bounds on a single variable.
Problem type
ILP, complexity level 5: integer variables with linear objective and constraints. Solved with HIGHS at the Medium solver tier.
Picture
Shaded: every point that satisfies all the constraints. Dot: the optimum. Dashed: the objective's level line through it.
The answer at a glance
The optimal value of each decision, as the solver returned it.
Which constraints hold the answer in place
Binding (no slack left): (3) y >= 0. Changing a binding constraint changes the answer; a slack one can move a little without effect.
| # | Constraint | Value | Limit | Slack | Binding |
|---|---|---|---|---|---|
| 1 | 2*x + 2*y <= 3 | 2 | 3 | 1 | |
| 2 | x >= 0 | 1 | 0 | 1 | |
| 3 | y >= 0 | 0 | 0 | 0 | yes |
Algebraic model (low level)
Decision variables, objective and every constraint written out; this is exactly what the solver receives.
Standard form
As a linear program: minimize cᵀx subject to A x ≤ b (the inequality rows) and A_eq x = b_eq (the equations); a maximization is written as minimizing the negative.
Model code (cvxpy)
The same model in cvxpy, ready to run.
import cvxpy as cp
x = cp.Variable(name='x', integer=True) # first decision variable (units)
y = cp.Variable(name='y', integer=True) # second decision variable (units)
objective = cp.Maximize(x + y)
constraints = [
2*x + 2*y <= 3,
x >= 0,
y >= 0,
]
problem = cp.Problem(objective, constraints)
problem.solve(solver='HIGHS')
print(problem.status, problem.value)
print('x =', x.value)
print('y =', y.value)The dual problem
Every constraint of the original (primal) problem gets a price, and every primal variable becomes a constraint on those prices. Integer variables are relaxed: this is the dual of the continuous (LP) relaxation, which gives a bound on the integer optimum, not its exact value. Only weak duality: the dual of the continuous relaxation gives an upper bound of 1.5 on the integer optimum 1, a duality gap of 0.5. Integer problems generally have a gap.
| Dual variable | Prices | Value |
|---|---|---|
| y1 | price of constraint '2*x + 2*y <= 3' (objective change per extra unit of its right-hand side) | 0.5 |
Solve your own
This is the model as the app reads it. Change any number and solve it in the free box on the front page (no account needed).
maximize x + y
subject to
2*x + 2*y <= 3
x, y >= 0
integer: x, y
# x = first decision variable (units)
# y = second decision variable (units)
# objective = sum of x and y (units)Checked: the app's answer matches the reference answer in our test set, which two solvers (HIGHS, SCIP) agree on. Built 2026-11-10.
Related examples
Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.