Linear Programming - Constraints

Question

I am trying to encode this (a small part of a project) to linear programming:

For each package p we know its length (xDimp) and width (yDimp). Also, we have the length (xTruck) and width (yTruck) of the Truck. All the numbers are integers.

Due to the design of the packages, they cannot be rotated when placed in a truck.

The Truck is represented as a matrix of 2 dimensions, only with x and y coordinates. We ignore the height.

Decision variables:

– pxy[p,x,y] = package p is in the cell with upper-right coordinates (x, y)

– pbl[p,x,y] = the bottom left cell of p has upper-right coordinates (x, y)

Example

How do I write such constraints to set pbl and pxy variables? I supouse that I should set the variable pbl to assure that the package fits in the truck and the value of pxy variable depends of the value of pbl.

Thank you,

Is not homework, but is a small part of a project that I'm doing (self learning) to learn linear-programming and CPLEX. — Cristian Morales
– Cristian Morales, Commented May 22, 2016 at 10:48
The no-overlap constraints for this packing problem can not be stated in a (continuous) linear programming formulation. You'll need binary variables for that. — Erwin Kalvelagen
– Erwin Kalvelagen, Commented May 22, 2016 at 16:24
I think, that it should can be done with linear programming. — Cristian Morales
– Cristian Morales, Commented May 23, 2016 at 18:08
This looks like a packing-problem (which are most of the time NP-complete; may be seen as generalizations of bin-packing). So under the assumption, that this problem is NP-complete (what i think) and P=/NP, there is no linear program (except for models with an exponential size) that can solve this (proof by contradiction). As Erwin mentioned, you could resolve to binary variables, but in this case you have an integer/mixed-integer problem which are in general NP-hard too (but may work in practice)! — sascha
– sascha, Commented May 29, 2016 at 23:04

Lars Hadidi · Accepted Answer · 2022-12-24 21:05:05Z

This is a variant of the bin packing problem, a two dimensional packing of multiple rectangles of varying widths and heights in an enclosing rectangle (2BP). If they are only allowed to be rotated by 90°, we got the orthogonal orientations rectangular packing problem, and in your case we have a non-rotatable rectangular packing problem. Its computational complexity is NP-hard, but it's not unfeasible. From your description, the problem is already discretised, restricting the possible placements to the grid, which means that the optimum of the continuous version may not be available anymore.

One approch is to calculate certain conflict graph in advance, which represents your search space and holds information about the overlap of the rectangles:

where

Every edge represents a conflict and every node represents a possible placement within your truck. Two packages p and q intersect iff

and pairwise.

Now, the packing problem on the grid is a maximum independent set problem on the conflict graph (MIS), assuming you want to maximize the number of packages on the truck. The MIS, in turn, has the following ILP formulation:

This is an integer relaxation of the MIS but still not good for the branch and bound solving method. If C is clique in G then any independent set can pick at most one node from C, therefore use the following constraint:

The resulting linear program's number of variables grows exponentially.

In order to go further, you can try a meta constraint satisfaction approach. Firstly, use the following contraints to make sure your packages are within the truck:

Secondly, use a set of disjunctive constraints to prevent overlap:

From that point on, you can start to formulate a meta program, as descriped here

I think this should be be enough for a start :-) You can find more information in the literature about combinatorial optimization.

Sources:

http://www.staff.uni-mainz.de/schoemer/publications/ESA03.pdf

https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2046

Collectives™ on Stack Overflow

Linear Programming - Constraints

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related