What ways are there to both maximize the objective function and maximize the number of integers in a LP problem solution?

asked 16 Feb '15, 15:51

klon's gravatar image

klon
214
accept rate: 0%

edited 16 Feb '15, 17:08

2

@klon: What do you mean by maximizing the number of integers? If you are solving a MIP, all of the variables, which are defined to be integers, are going to be integers in the optimal solution (provided that the model is solved correctly). So, I don't see any point in maximizing the number of integers.

(16 Feb '15, 15:59) Ehsan ♦
1

Good call, I should not call it MIP, it's that I want to maximize the number of integers in the solution but it does not really matter which variables are integers and which are continuous. Fixing it.

(16 Feb '15, 17:06) klon
1

@klon: Thanks for the clarification. Is there any practical application for this requirement? As noted by @Marco, modeling this requirement would only increase the problem complexity.

(17 Feb '15, 01:45) Ehsan ♦

There is a cost associated with every non-binary variable in the solution. So including it in the objective function is one way I guess.

(18 Feb '15, 16:31) klon

To maximize the integrality, you can replace each original continuous variable \(x\) with \(y+z\), where \(y\) is an integer variable and \(z\) is a nonnegative continuous variable. Then your objective is to minimize the sum of the \(z\) variables. You can explicitly put an upper bound of 1 on \(z\), but that will happen naturally due to the objective. Your LP now becomes a MILP with twice as many variables, but no linearization is required.

link

answered 19 Feb '15, 14:23

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

edited 19 Feb '15, 14:27

1

This method prefers x=(0.1,0.1) over x=(0, 0.3), although the latter has more integers.

(19 Feb '15, 14:33) optimizer
1

Yes, it minimizes the total fractionality. To minimize instead the number of fractional variables, you can introduce binary variable \(w\), together with big-M constraint \(z \le w\), and minimize the sum of the \(w\) variables.

(19 Feb '15, 14:53) Rob Pratt

Now, with your comment, I better understand the question.

General problem first: two objective functions, so you will typically "weigh" the two objectives and mingle them into one objective (unless you embark on multi-objective optimization and seek Pareto-optimal solutions).

The objective function could be expressed using additional integer variables z_i (one for each of your original continous variables x_i) and minimize their (absolute) difference |x_i-z_i|; you may need to linearize this using additional techniques.

Is this what you need? Will make your problem harder to solve, though.

link

answered 16 Feb '15, 18:49

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

Thanks. This sounds like a way forward, but may turn out to be to computationally expensive. I am looking at optimizing as many variables as possible to be binary. What constraints should I place on z_i? Can you clarify with an example?

(18 Feb '15, 16:33) klon

see @Rob's answer

(19 Feb '15, 14:29) Marco Luebbecke ♦

Users tend to like the idea of weighting objective measures into one model. It's (in theory) easy and from a computationally side it also sounds better. Merging objective measures may work fine in many applications, but I have also often seen models formulated into one, with the users not knowing it was in fact a multi objective model to begin with or at least didn't sit down and think it through. Often the different objective criteria is very different, impacts the model and solution in completely different ways. I often suggest to build a model to be solved in several steps, before starting to merge objectives. This gives the advantage of better control and provides insight into the model effects. If that's too slow or otherwise doesn't work out, then by all means go for the weighted approach.

link

answered 19 Feb '15, 12:47

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

Add two binary variables \(y_i\) and \(z_i\) to indicate if \(x_i\) is 0 or 1, and add the constraints \(x_i \leq 1-y_i\) and \(x_i \geq z_i\). Maximizing \(\sum_i (y_i + z_i)\) will maximize the number of number of binary \(x_i\).

link

answered 19 Feb '15, 14:51

optimizer's gravatar image

optimizer
17615
accept rate: 6%

edited 19 Feb '15, 14:54

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615

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
×190

Asked: 16 Feb '15, 15:51

Seen: 842 times

Last updated: 19 Feb '15, 14:54

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