如何在使用松弛变量的情况下获得目标函数的结果？

Question

我有一个使用 Gurobi 的简单 Python 代码。我添加了一个松弛变量来强制模型的可行性。我需要知道如何获得目标函数中真正的最小值。

import gurobipy as gp
from gurobipy import GRB

# Create the model
model = gp.Model("quadratic_optimization_with_slack")

# Variables
x = model.addVar(name="x", lb=0)  # x >= 0
y = model.addVar(name="y", lb=0)  # y >= 0
slack = model.addVar(name="slack", lb=0)  # Slack variable for relaxation. If slack = 0 --> Model is infeasible

# Objective: Minimize 2x^2 + y
model.setObjective(2 * x**2 + y, GRB.MINIMIZE)

# Constraints
model.addConstr(x - 5 + slack == 0, name="constraint_1")  # (slack allows relaxation) <-- Condition to be relaxed
model.addConstr(x + y == 4, name="constraint_2")

# Add slack penalty in the objective to ensure the slack value is minimum.
# The problem is that the result is not anymore the model.ObjVal, but the penalty*slack
penalty_weight = 0.00010  # Penalty for slack usage
model.setObjective(model.getObjective() + (penalty_weight * slack))

# Optimize the model
model.optimize()

根据数值：

x = 4
y = 0
slack = 1
model.ObjVal = 0.0001  # (penalty_weight * slack)

显然，0.0001并不是我的目标函数2x^2 + y所能得到的最小值。有了这个松弛，它应该是 2 * 4^2 + 0 = 32。

如何获得目标函数的真正最小值？

Answer 1

您的期望是错误的。您不需要松弛变量。

如果 x+y=4 那么你的函数可以通过完成平方来重写，如

2x²+4-x = 2(x-1/4)²+31/4

当 x=1/4（因此 y=15/4）时，该值被最小化，值为 31/4。这也符合您的隐含约束 x<=5.

gurobipy 的有限、免费、pip 安装版本提供 3.875（即 31/4）。

import gurobipy as gp
from gurobipy import GRB

model = gp.Model("quadratic_optimization_with_slack")
x = model.addVar(name="x", lb=0)  # x >= 0
y = model.addVar(name="y", lb=0)  # y >= 0

model.setObjective(2 * x**2 + y, GRB.MINIMIZE)
model.addConstr(x <= 5, name="constraint_1")
model.addConstr(x + y == 4, name="constraint_2")

model.optimize()

输出：

Restricted license - for non-production use only - expires 2026-11-23
Gurobi Optimizer version 12.0.0 build v12.0.0rc1 (win64 - Windows 10.0 (19045.2))

CPU model: Intel(R) Xeon(R) W-2123 CPU @ 3.60GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 2 rows, 2 columns and 3 nonzeros
Model fingerprint: 0x2bcf8c93
Model has 1 quadratic objective term
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  QObjective range [4e+00, 4e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [4e+00, 5e+00]
Presolve removed 2 rows and 2 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Barrier solved model in 0 iterations and 0.00 seconds (0.00 work units)
Optimal objective 3.87500000e+00