4
1

I have a series of difficult 0/1 IPs that I'm solving. The objective function, which I want to minimize, has the property that its value at any feasible integer point is of the form x.y where 1 <= y <= x < 10. In watching the output of Cplex I see a lot of instances where the dual bound is of the form z.w... where w > z, and it stays that way for a long time. If, in fact, the optimum objective is >= z.w..., then it is certainly going to be >= (z+1).1. So how can I persuade Cplex to make this inference?

[added later] I should say something about how I encode the problem: I have a bunch of subsets (each of cardinality <= 10) of the variables. If S is such a subset, denote by [S] the sum of the 0/1 variables in that set. I want to find a solution that minimizes the maximal [S] over all of my subsets. I'm also interested in finding the minimum of [S] + 0.1*[T] where S and T range over all pairs of sets so that [S] >= [T] (i.e. I want to find a setting of my 0/1 variables that minimizes the maximal [S], and then, over all of those minimizes the second largest). I encode it by having two continuous variables, w and z and adding the inequalities

[S] <= w and [S] + [T] <= z, where S and T range over all distinct subsets. I then make my objective

\[0.9 \ast w + 0.1 \ast z\]

asked 23 Dec '13, 13:04

VictorSMiller's gravatar image

VictorSMiller
343215
accept rate: 0%

edited 23 Dec '13, 18:00

fbahr's gravatar image

fbahr ♦
4.6k716

4

CPLEX is smart enough to know that if an objective function is composed of integer variables with integer coefficients, then any bound that is less than 1 away from the current best known integer solution is good enough. It might help to simply multiply your objective function by 10 (\(9w+1z\)) so that CPLEX could recognize this.

(23 Dec '13, 16:53) Brian Borchers

@Brian, Thanks for the suggestion. However, I changed w and z to integer variables and changed the objective to 9*w + z. Cplex still spent a few minutes where the dual bound was 19.5455 (the incumbent at that point had value 88). Is there some setting of cplex that I need to make? All of my variables are integer now. My version of cplex is 12.5.0.0.

(24 Dec '13, 11:10) VictorSMiller

@Brian. I think that I understand what you're saying -- if cplex has an incumbent whose objective value (with integer coefficients) is x, and it has a dual bound of y where x-y< 1, then it knows that it's solved to optimality. However, in the middle of the computation it doesn't "promote" the dual bound to ceil(y).

(24 Dec '13, 12:08) VictorSMiller

Unless you think there will be a large number of solutions optimal with respect to the first criterion, you might want to investigate using the solution pool. Minimize a single continuous variable w that is at least as large as the sum of the binary variables in each set. Set the absolute pool gap to something less than 0.5, so that solutions strictly inferior to the current incumbent are dropped. Set the replacement strategy to 1, which gets rid of inferior solutions. I think you can get by with setting the pool capacity to something small (but at least two). Solve the model, and then screen the solutions in the pool to find the one that has matches the optimal objective value and also has the best result on the secondary criterion.

link

answered 23 Dec '13, 18:54

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

If your goal is really " I want to find a setting of my 0/1 variables that minimizes the maximal [S], and then, over all of those minimizes the second largest", then I would use goal programming, i.e. solve two problems.

  • Step 1. Minimize the largest set size. Assume that in the optimal solution you find the minimum largest set size equals s, that it is attained by set S0, and that all other sets have a size smaller than s.
  • Step 2. Add the constraint [S0] = s, and minimize the largest size among all sets except S0.

If after first step you have several sets of size s, then run step 2 independently for each such set. The algorithms becomes.

  • Step 1. Minimize the largest set size. Assume that in the optimal solution you find that the minimum largest set size equals s, that it is attained by the sets S0,S1,...,Sn, and that all other sets have a size smaller than s.
  • Step 2. For each set Si add the constraint [Si] = s to the original problem, and minimize the largest size among all sets except Si. Let ti be the objective value, and Ti one of the sets having a size ti.
  • Step 3. Select i such that ti is minimal (i may not be unique). Si and Ti are the answer to your problem.
link

answered 24 Dec '13, 05:47

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

3

You can modify this to avoid having to run the second stage problem multiple times. After step 1, add a new binary variable \(z_j\) for each set \(S_j\) (whether or not \([S_j] = s\) in step 1, add the constraint \([S_j] \le s - 1 + z_j\) for all \(j\), and make the \(z\) variables SOS1 (or add the constraint \(\sum_j z_j \le 1\)). If the second stage problem is infeasible, then \([S_j]=s\) has to hold for at least two values of \(j\).

(24 Dec '13, 13:52) Paul Rubin ♦♦

Paul, good catch, your solution is probably more efficient if you can't run the second stage problems in parallel.

(26 Dec '13, 09:31) jfpuget
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:

×191
×71
×2

Asked: 23 Dec '13, 13:04

Seen: 1,003 times

Last updated: 26 Dec '13, 09:31

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