I have a variable Wmn[m,n,t] and I want the AMPL to solve it as an integer without defining it as integer.

asked 27 Feb '15, 18:17

Zaid's gravatar image

Zaid
112
accept rate: 0%

2

without giving us more detail you will only get useless answers.

(27 Feb '15, 18:20) Marco Luebbecke ♦

The problem is that I am working on networks and I have the traffic between the nodes (from m to n) at time t is a float number. I want to get it as a ceiled integer without defining it as an integer. I have tried the integer definition but the complexity increased and I could not get a solution within 24 hour(super computer. So I need a constraint to force this variable to be integer. Thanks

(28 Feb '15, 04:04) Zaid
3

There is no magic constraint to force a variable to take an integer value. You have to define it as integer-valued, and turn the model into an IP. Some LPs have the "integrality property" (solutions are automatically integer when the right-hand sides are integer, while retaining the simplicity of being an LP), but apparently your model does not have that property.

(28 Feb '15, 17:04) Paul Rubin ♦♦
1

@Paul: While your comment is absolutely correct (at least: afaict), it might be worth mentioning that there are IPs whose LP relaxations don't possess that "integer property" – but can be extended in a way such that by adding some "magic" constraints solutions gain integer quality (e.g., LP version of min cost matching + Edmond's "blossom constraints").

(28 Feb '15, 17:46) fbahr ♦

Thanks for the explanations.@Paul but How about your answer: https://groups.google.com/forum/#!searchin/ampl/ceil/ampl/xrIAWvUplCQ/-Diuq_OLu9UJ Because I need the variable to be ceiled.

(01 Mar '15, 04:55) Zaid

Is it different from getting optimal integer value?

(01 Mar '15, 04:56) Zaid
1

@Zaid: The answer you linked from the AMPL forum was for a different problem. (There the poster was using ceil just to count the number of nonzero variables.) If your Wmn can be greater than 1, you would need multiple binary variables for each combination of m, n and t, which is equivalent to (but clumsier than) declaring Wmn integer.

(01 Mar '15, 06:40) Paul Rubin ♦♦

I should amend my earlier comment about "magic constraints": there's no magic constraint that forces integrality while preserving convexity. As @AndyT notes, it can be done with a nonconvex, nonlinear function.

(02 Mar '15, 11:25) Paul Rubin ♦♦
showing 5 of 8 show 3 more comments

Technically, you could do this with the constraint: \(\cos(2\pi x) = 1\), which enforces that unrestricted variable \(x\) takes only integer values.

That said, I'm guessing that moving the integrality into such a constraint won't help your model solve any faster; the introduced nonlinearity may require a different solver as well.

link

answered 02 Mar '15, 10:45

AndyT's gravatar image

AndyT
6788
accept rate: 7%

edited 02 Mar '15, 12:55

fbahr's gravatar image

fbahr ♦
4.6k716

Convex optimization solvers such as IPOPT, KNITRO or SNOPT use Newton's method for constraint satisfaction. Your constraint will be accepted and a solution will be (close to) integral, but global optimality cannot be guaranteed.

(02 Mar '15, 11:00) optimizer

A global optimization package such as BARON should be able to handle this form of constraint (though again, I'm not suggesting it would be of much help to the OP).

(02 Mar '15, 11:05) AndyT

Given the progress in global optimization, it might be worth a shot.

(02 Mar '15, 11:24) Paul Rubin ♦♦

BARON is a 'branch and reduce' solver. That may defeat the purpose of avoiding integer variables.

(02 Mar '15, 15:40) optimizer

I don't want to spoil the party, but let's face it: there is no free lunch. If integrality on variables is required, we go from easy to hard problems in theory, and that has its price also computationally.

But this is not the point to give up. If we learn more about the problem, we may (or may not) help in finding better models which enable you to solve your instances up to a certain quality at least.

link

answered 02 Mar '15, 17:27

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

Thanks a lot for you replies.The model is MILP and I do not want to make it nonlinear. Actually I have( for all{m,n,t}: sum{d in D}Y[d,m,n,t]+sum{c in C}X[c,m,n,t] =W[m,n,t]) I need the W to be the optimum minimized integer. While X and Y are float variables.

(02 Mar '15, 17:40) Zaid

and index sets are probably quite large?

(02 Mar '15, 17:52) Marco Luebbecke ♦

c:14, d:20, m & n=7, t=19.

(02 Mar '15, 17:56) Zaid
1

@Zaid: The dimensions of W suggest that the MILP formulation should not be too scary (although you never know until you try).

@Marco: I actually had a free lunch today, providing a counterexample to your assertion. :-)

(02 Mar '15, 18:49) Paul Rubin ♦♦
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:

×11
×6

Asked: 27 Feb '15, 18:17

Seen: 777 times

Last updated: 02 Mar '15, 18:49

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