Mixed integer linear programming

[VladimirG.]

Hello,

I need to solve mixed-integer linear programming problem.

My problem is like common minimization problem but with integer constrain on one of variables ( not real ).

Mathcad 15 Help page said, that solving that Mathcad Solve Block can not contain Range variables.

For example, how could I solve problem like next:

Given:

x = 0 or 1 -???

y > 100 and y < 500

f(x,y) = (y + x)*( y - x )

Minimize (f,x,y)

My quastion is if it is possible to set restrictions on "x" as I wrote above?

[MikeArmstrong]

Like below.

Mike

[VladimirG.]

Thank you for fast response.

But indeed, my problem is a little different.

Suppose x and y are vectors.

There are limitations for each member of vector and also for sum of members.

Please check sample attached and advice how to be in such case.

[ptc-2128955]

Vladimir,

Unfortunately, the base Mathcad package does not have the algorithms to support integer programming. For that, you need an add-on package... I think it's the Data Analysis Extension Pack, but I'm not sure -- try to find descriptions of the extension packages on the PTC site.

Aaron

[ptc-2128955]

Vladimir,

I've taken a look at your file. Your problem statement doesn't really make much sense. First, as written in the base MC with x real and in [0,1], there are an infinite number of solutions. MC is just displaying one of them. With x restricted to 0 or 1, you would still have a number of different solutions, all having an objective function value of 400. With the criteria given, each solution would have 7 x values equal to 1 and 4 that equal 0. For each x that equals 0, the corresponding y value would equal 100 for your objective to be minimized. Actually, all the other y's could be anything, so technically you could have an infinite number of y vectors.

Perhaps you could describe the problem you're trying to solve -- are you sure you've formulated it correctly?

Regards,

Aaron

[VladimirG.]

That was just a sample to illustrate my problem. My real problem has big set of constraints that lead to one solution, not a set of them.

The main idea was to show that real X gives better(more optimal) solution than integer, and I want to restrict such real solutions.

So, what about extension with integer programming implementation. Can somebody provide me link or exact name of such.

[ptc-2128955]

Click on a few of the "more like this" links on the right side of the screen.... you'll find that it's called the

Solving & Optimization Extension Pack. Probably info somewhere on PTC site about it. Good luck with your problem.

Aaron

[ptc-2128955]

Vladimir: This is from the M14 FAQ on PTC site. You might be set if you're using M14 or 15. I'm still on M11, so hadn't really been keeping up with the M14+ stuff. Sorry for passing bad info. -Aaron

Do the earlier versions of Mathcad extension packs and libraries work with Mathcad 14.0?

Customers migrating to Mathcad 14.0 need to update their extension packs and libraries. Enterprise customers will automatically receive the compatible extension packs and libraries. Single user customers who are upgrading from Mathcad 12 or Mathcad 13 to Mathcad 14.0 will also automatically receive the compatible extension packs and libraries if they had version 12 or 13 of the Mathcad extension packs and libraries. Single users with extension packs and libraries from Mathcad 11 and older must purchase new extension packs and libraries for Mathcad 14.0. Single users can purchase Mathcad 14.0 extension packs and libraries at the end of March 2007. *

Are any add-on products being retired at the time of the release?

As of Mathcad 14.0 the Mathcad Solving and Optimization Extension Pack will be retired. The calculation functionality formerly offered in the SOEP is included in Mathcad. A new, free e-book (collection of Mathcad worksheets) which contains solving and optimization techniques will be available from the Mathcad Resources page at: http://www.mathcad.com/resources/ by the end of April 2007.*

[VladimirG.]

Aaron, am I understand it correctly. If use mathcad 14 or 15 I will have a possibility to solve integer programming problems without any extensions?

Than I still have same open question: how to set "integer constraint" in mathcad 15?

[ptc-2128955]

Please see the last post in this topic link:

http://communities.ptc.com/message/128658#128658

Seems to explain how to do it.

[rag]

Hmm - that way there is no guarantee the x is assigned an intreger value only (0 or 1) and thats which was asked for by the poster.

Unfortunately using the logical OR from the boolean palette from the boolean palette does not work (unless the initial value for X is set to 0). Why?? It seems to be a valid logical constraint.

Furthermore your pic shows, that Mathcad is ignoring the constraint Y>100 as opposed to Y>=100! A bug or a natural limitiation of the numerical method used?

Rag

[MikeArmstrong]

Strangely when I changed the guess value of X to zero. The minimize function produce a value.

Mike

[RichardJ]

Unfortunately using the logical OR from the boolean palette from the boolean palette does not work (unless the initial value for X is set to 0). Why?? It seems to be a valid logical constraint.

To you, but not to Mathcad. The help says:

A set of equations and/or inequalities representing the constraints. Use the following operators to create these constraints:

• Boolean equals,
• greater than,
• greater than or equal to,
• less than, or
• less than or equal to.

Furthermore your pic shows, that Mathcad is ignoring the constraint Y>100 as opposed to Y>=100! A bug or a natural limitiation of the numerical method used?

Perhaps if it is displayed to full precision you will see 100.00000000000001?

[MikeArmstrong]

Perhaps if it is displayed to full precision you will see 100.00000000000001?

Nope.

The value still comes out at 100 even when displayed to 17 decimal places.

Mike

[RichardJ]

Oh well. Another (rather minor) bug.

[ValeryOchkov]

Vladimir G. wrote:

Hello,

I need to solve mixed-integer linear programming problem.

My problem is like common minimization problem but with integer constrain on one of variables ( not real ).

The SOEP (Solving Optimization Ext. Puck. for Mathcad 6-11?) has an option "I" for this task.

Not Minimize (f, x) but Minimize (f, x, "I") - I - Integer.

One example (sorry, in Russian):

[VladimirG.]

Thank you for sample.

I saw your topics and tried such conditions, but as far as I understand it is not work in mathcad 15.

Also in the case when count of variables is more than 100 it is really hard to write such maximize function.

[ValeryOchkov]

Vladimir (and all) - read please one Russian article:

http://twt.mpei.ac.ru/ochkov/paint.htm

[VladimirG.]

Thank you for link. Cognitive article. It was interesting to read, but it does not solv my problem.

I still do not get how to solv mixed-integer problems in mathcad 15.

Is anybody in this community can help me to setup integer restriction for my problem?

[RichardJ]

I still do not get how to solv mixed-integer problems in mathcad 15.

You can't. The SOEP is no longer available, and the statement by PTC "The calculation functionality formerly offered in the SOEP is included in Mathcad" is not true. Specifically, there is no way to restrict solutions to integers. Sorry.

[VladimirG.]

Ok, thank's. It's a pitty.

I like mathcad, but now I need to migrate to other product:(.