Bin Packing

Capture

For many years I have maintained open source code to optimize the arrangement of small items in larger bins in two and three dimensions.

My interest in this problem has been maintained by requests from several clients to provide front and back ends that adapt the bin packing engine for their particular needs.

  • Cutting panels from plywood sheets with minimum waste.  2D problem. Client in the Philippines .
  • Packing ECCO shoe boxes into cartons to minimize shipping costs.  3D problem. Client in the USA.
  • Packing Canon camera boxes into cartons to minimize shipping costs. 3D problem.  Client in Italy.
  • Cutting panels from plywood sheets with minimum waste. 2D problem. Client in India.

The Indian client was kind enough to share test results comparing my results with those from a commercially available system ( Cut Rite ).  The test involved 32 unique packing problems requiring in total  926 panels to be cut from 124 sheets. On 26 of the 32 packs the results were identical, requiring the same number of sheets to cut the panels. For 4 packs the Cut Rite arrangement needed fewer sheets, and for 2 my packing engine gave a better result.

As always with optimization problems, my focus is on providing answers that are good enough in an extremely short time.  The Cut Rite bin packer required several seconds to generate a solution, my engine delivered in 300 milliseconds or about 10 times faster.

Bin Packing Engine code.

 

Posted in Projects | Leave a comment

A little intelligence, artificially.

KMeans is a windows console application to find clusters in data with any number of columns ( attributes ) using the KMeans algorithm ( https://en.wikipedia.org/wiki/K-means_clustering )

Usage: KMeans <data dimension> <data file path> <number of clusters>

The iris data set ( http://archive.ics.uci.edu/ml/datasets/Iris ) has 4 attributes

1. sepal length in cm 
2. sepal width in cm 
3. petal length in cm 
4. petal width in cm

The application outputs

KMeans.exe 4 ..\data\bezdekIris.data 3

Total distance 103.982
Total distance 97.249
Total distance 97.2046

Cluster 0 means 5.006 3.428 1.462 0.246
mins: 4.3, 2.3, 1, 0.1,
maxs: 5.8, 4.4, 1.9, 0.6,
sds: 0.348947, 0.375255, 0.171919, 0.104326,

Cluster 1 means 5.90161 2.74839 4.39355 1.43387
mins: 4.9, 2, 3, 1,
maxs: 7, 3.4, 5.1, 2.4,
sds: 0.462633, 0.293885, 0.504774, 0.295091,

Cluster 2 means 6.85 3.07368 5.74211 2.07105
mins: 6.1, 2.5, 4.9, 1.4,
maxs: 7.9, 3.8, 6.9, 2.5,
sds: 0.48761, 0.28625, 0.482118, 0.276165,

I have used this code to locate servers among clients to minimize the total distance between clients and their nearest server, when there was too many clients to calculate the absolute optimal locations directly.

The open source code for this can be seen at https://github.com/JamesBremner/KMeans

Posted in Uncategorized | Leave a comment

Talking to satellites

Starting work on SpaceCom  to enable error free communication between satellites and the ground using the  NASA TC SPACE DATA LINK PROTOCOL CCSDS 232.1-B-2

SpaceDataLink

Posted in Uncategorized | Leave a comment

New Mexico Senate Webcaster

Every session of the New Mexico state senate since 2009 has been webcast using a computer application designed and coded by SpeakerToRobots.

The chair recognizes one of the senators. When the senator begins to speak, one of three cameras has already swung into position and is webcasting the perfect image. The application stores over 50 preset positions for each camera, automatically selecting and moving the cameras into position whenever the speaker changes, using the VISCA protocol over RS232.

Posted in Projects | Leave a comment

SWEEPEM

In the 1980s this Canso flying boat was photographed over the Gatineau Hills searching for ore deposits using a new electromagnetic system called SWEEPEM.  Built in the 1940s to hunt submarines under the North Atlantic, the aircraft’s ability to flow low, slow and long was ideal for detecting metallic ores buried deep underground.  I developed the signal processing and real time control software for SWEEPEM and operated the system aboard the Canso for the calibration flights.  In this article written for Survey Magazine and published in 1985 I described the work.

sweepem_article

 

Posted in Uncategorized | Leave a comment

PELEX-MAX

A showcase for some recent work on real time signal processing

http://pinmed.net/wireless_mri-compatible_12-lead_ecg_pressure_oximetry/

There are five applications comprising the heart of the software in this system:

  1.  Mixer which does the signal processing
  2.  GUI which helps the user to edit the 100 plus configuration parameters
  3.  PDG which produces the pretty graphs seen in the showcase video
  4.  WV ( waveform visualizer ) which enables user to monitor and “teach” the Mixer how to identify cardiac signals.
  5.  Unit Tester

Added together these have 40,000 lines of pure code, excluding comments and white space.

 

Posted in Projects | 1 Comment

Nana

Nana is a cross-platform library for GUI programming in modern C++ style.

v1.5.5 was released this week and includes a small contribution from me that allows application code to set the default width of text entry fields.

Posted in Uncategorized | Leave a comment