I'm currently trying to implement Bender's Decomposition in MATLAB using the CPLEX API, though I'm having issues since I do not want to restrict my inputs to Standard Form LPs.

The input model that I want to use essentially looks like:

minimize c*t  
s.t. b_lhs < Ax < b_rhs 

Where A is a m x n constraint matrix and lhs and rhs are m x 1 vectors associated with each constraint. I have to stick to this formulation partially since it speeds up a lot of my other code and since it can easily capture equality constraints, inequality constraints, upperbounds and lowerbounds.

My issue stems from the fact that I need both the dual values and the corresponding rhs or lhs constants to generate the correct cuts in Bender's Decomposition. Right now, Cplex can provide me with the dual values for each constraint, but cannot tell me whether these values are related to the right inequality or the left inequality (i.e. the b_lhs or the b_rhs vector)...

Is there a way to have Cplex provide me with the dual values for each constraint and also reveal which side of the constraint each value is associated with?

asked 20 Jan '11, 06:42

Berk%20Ustun's gravatar image

Berk Ustun
3071311
accept rate: 0%


The simplex algorithm and interior point (after cross-over) returns basic solutions. Underneath this lies the optimality condition for constraints :

-y[i]+sl[i]-su[i] = 0 and sl[i]*(l[i]-xc[i])=0 su[i]*(u[i]-xc[i])=0

where sl and su are the lower and upper constraint lagrange multipliers derived from the general KTT optimality conditions. sl[i]-su[i] now becomes your well known reduced cost. For a optimal primal and dual feasible basic solution the following apply :

  1. Slack is on lower => su[i] = 0, sl[i] = y[i]
  2. Slack is on upper => sl[i] = 0, su[i] = -y[i]
  3. Slack is basic => sl[i]=su[i]=0

I am sure Paul has something to add regarding implementing Benders, he's the expert in that area :-)

link

answered 20 Jan '11, 07:51

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

edited 20 Jan '11, 07:57

Thanks for this. Worst case scenario I'm going to use this and just check which constraints have slack/are tight...

(20 Jan '11, 11:04) Berk Ustun

Retrieving sl and su boils down to looking at the sign of y, I just wanted to give a peak at the theory behind. You have to be careful when solutions become either primal or dual infeasible i.e use farkas rays if needed.

(20 Jan '11, 11:47) Bo Jensen ♦

ROTFL at the "expert" crack.

(21 Jan '11, 16:52) Paul Rubin ♦♦

Why not post your question to CPLEX forum?

http://www.ibm.com/developerworks/forums/forum.jspa?forumID=2059

link

answered 21 Jan '11, 10:24

John%20Cui's gravatar image

John Cui
15917
accept rate: 0%

I can see no reason to down-vote such a answer, CPLEX related questions is better answered there.

(21 Jan '11, 14:40) Bo Jensen ♦

Take a look at IloCplex.getBasisStatuses. Feed it the array of constraints, and it will return an array of status indicators for the slack variables in the constraints. Bear in mind that (if I've had enough coffee this morning) a slack at its upper bound means the constraint hit its lower bound and vice versa.

link

answered 21 Jan '11, 16:58

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Exactly, you can often be tricked by the slack sign i.e if it's -1 or +1 in the constraint matrix.

(21 Jan '11, 17:23) Bo Jensen ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×191

Asked: 20 Jan '11, 06:42

Seen: 5,348 times

Last updated: 21 Jan '11, 16:58

OR-Exchange! Your site for questions, answers, and announcements about operations research.