I'm trying to solve the following exercise from the canonical textbook on Linear Optimization. I have proposed a solution, but I'd like someone to help fortify my understanding. Here's the exercise, and my solution:
Consider the problem of the form:
$~~~~~\underset{x}{\min} ~\,\, \underset{i}{\max} \,\,\,\, (a'_i x – b_i)$
subject to no constraints, where $a_i$ and $b_i$ are given vectors and
scalars, respectively.a) Describe a cutting plane method for problems of this form.
b) Let $\textbf{x}$ be an optimal solution to a relaxed problem in which only
some of the terms $(a'_i x – b_i)$ are retained. Describe a simple
method for obtaining lower and upper bounds on the optimal cost in the
original problem.
My solution:
part a) Do the following steps to solve using cutting plane method:
- Make the following transformation:
$~~~~~\underset{x,\gamma}{\min} \,\,\, \gamma $
subject to
$~~~~~(a'_i x – b_i) \le \gamma \,\, \forall i$
- Relax the integrality constraints in the problem above, and solve using a subset $I$ of the constraints.
- Call the solution to this relaxed problem $x^*$, and its objective function value $\gamma^*$. Solve the following separation problem to determine if $x^*$ is feasible for the original problem:
$~~~~~\underset{i}{\min} \,\,\, \gamma^* – a_i^T x^* + b_i$
- If the solution to the above problem is nonnegative, then $x^*$ is optimal for the original problem. If the solution to the above problem is negative, then we introduce the corresponding additional constraint, and re-solve, repeating until the solution to this separation problem is nonnegative.
part b)
Let $\bar{x}, \bar{\gamma}$ be the solution and objective value to the original problem, respectively. Using the solution to the separation subproblem, we will always obtain a lower bound to the original problem: $\gamma \le \bar{\gamma}$, because the feasible region of the original un-relaxed problem is smaller.
EDIT: second attempt at part b
For an upper bound, there are two cases based on the solution to the separation problem:
- If the objective of the separation problem is nonnegative, then no constraints are violated, and the solution to the relaxed problem is equivalent to that of the original problem, so it is both an upper and lower bound: $\gamma \le \bar{\gamma} \le \gamma$.
- If $\exists i$ such that $\bar{\gamma} – a_i^T x^* + b_i < 0$ then it gives us an upper bound on the solution to the original problem: $\bar{\gamma} < a_i^T \textbf{x} – b_i$.
(The above exercise was taken from Chapter 6 of Bertsimas's book Linear Optimization : https://www.amazon.com/Introduction-Linear-Optimization-Scientific-Computation/dp/1886529191)
Best Answer
A lower bound arises from the optimal objective value $\gamma^*$ of the relaxed problem, not from the separation problem. To get an upper bound, you need to compute the objective value of a feasible solution to the original problem. If the separation problem objective is nonnegative, then $(x^*,\gamma^*)$ is feasible, so $\gamma^*$ is also an upper bound. If the separation problem objective is negative, consider how to compute the true objective value ($> \gamma^*$) of $x^*$ based on the solution to the separation problem.