0
$\begingroup$

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)

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ I see. I don't have enough reputation to upvote this, but thank you. So, does the rest of my reasoning seem correct? $\endgroup$ Aug 22, 2023 at 18:46
  • $\begingroup$ Yes, your part (a) is correct. Glad to help. Please mark my answer as accepted. $\endgroup$
    – RobPratt
    Aug 22, 2023 at 18:54
  • $\begingroup$ On second thought, I guess I don't understand how to obtain an upper bound if the solution to the separation problem objective is negative (i.e. a constraint is violated). What do you mean by "based on the solution to the separation problem"? We would need to introduce the violated constraint and re-solve, right? Thanks again for your help. $\endgroup$ Aug 22, 2023 at 21:43
  • $\begingroup$ You can get a feasible solution without solving again. Keep $x^*$ the same and increase $\gamma$ by the amount that the maximum constraint violation indicates. $\endgroup$
    – RobPratt
    Aug 22, 2023 at 22:04
  • $\begingroup$ Thanks (sorry for a delayed response). I've editted my question with what I think is the correct answer to part b. Please confirm or let me know what's wrong. $\endgroup$ Sep 15, 2023 at 8:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .