penguin-project

• penguin-project
• Rust Instructions
  • Requirements
  • Usage
    • list or ls
    • api or q
    • solve
      • EXAMPLES:
  • Directory Structure
  • Development
  • Documentation
• Manual Labor
• Python Instructions
  • Requirements
  • Usage
    • Generating instances
    • Solving
    • Merging
    • Visualizing Instances

Rust Instructions

This replaces the dependencies and development

If on Ubuntu, install dependencies with:

./dependencies

following the prompt instructions and typing in password for sudo (might have to exit and reopen shell) TODO: source cargo env

Then run the formatter + build in release mode with

make

Then install the pengwin binary with

sudo make install

Now you can run the solver with

pengwin <SUBCOMMAND> [OPTIONS]

Requirements

It is recommended to use Linux or WSL since we use coin-or cbc, which is easier to set up on Linux.

First, install Rust using rustup by following the instructions on the website, by running

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Next, install coin-or cbc, the LP solver we currently use by either running the below (for Linux) or following the instructions on their repo

sudo apt-get install coinor-cbc coinor-libcbc-dev

You will need a C compiler:

sudo apt-get install gcc

If you want to access the api:

sudo apt-get install pkg-config libssl-dev

Usage

This command builds and runs the project

cargo run --release -- <SUBCOMMAND>

OR equivalently,first build the project with

cargo build --release

Then, in the root of the directory (or ensuring the inputs folder is in the same directory), run

./target/release/penguin-project <SUBCOMMAND>

Or equivalently (this builds it for you)

list or ls

This lists all available solvers

api or q

USAGE:

... api <size>

Where size can be

• small (s)
• medium (m)
• large (l)

This queries the 170 leader board API to find which outputs have better/worse scores than the current ones.

The API is limited to 5 QPS, so the output pauses sometimes

solve

USAGE:

... solve [OPTIONS] -s <SOLVER> <PATHS>..

Where you can input any number of PATH arguments, each one in the form <size>/<ids>

• <size> can be small, medium, or large
• <ids> can be a single id or a range of ids

OPTIONS:

• -w only runs the solver on provided inputs we are worse than

EXAMPLES:

solve -s lp large runs the lp solver on everything in the large folder

solve -s greedy small/1..220 medium/1 runs the greedy solver on ids 001 through 220 in the small folder and id 001 in the medium

solve -s benchmark small/1..40 -w runs the benchmark solver on small ids 001 through 040 that we are worse (higher) than

NOTE: We used a combination of rand_hillclimb and hillclimb to generate most outputs, as well as tuning some by hand. As a result, your results may vary when trying to run our solver as it inherently relies on randomness to generate solutions.

Directory Structure

Development

A github workflow runs rustfmt whenever pushing to main or creating a pull request to main but its a good idea to install and run:

rustup component add rustfmt
cargo fmt

On the Nightly toolchain (to support features on the rustfmt.toml):

rustup toolchain install nightly
rustup component add rustfmt --toolchain nightly
cargo +nightly fmt

Documentation

In addition to the above, we used the following crates/libraries:

good_lp	Github	Docs
clap	Derive Doc	Derive Tutorial
pfh	Documentation
rustfmt-check	Github	Actions Marketplace
rustfmt	Github	Toml Docs
argmin	Github	Docs
rayon	Github	Docs

Manual Labor

First install poetry and if prompted add the directory to the path.

sudo apt install python3-tk python3-pip
pip install poetry
# add given path to bashrc
echo "export PATH='/home/<>/.local/bin:$PATH'" > .bashrc
source .bashrc

Then in the project root

poetry install
poetry run gui <INPUT>

Where input is in the form small/3

This saves the current solution (if it has one) to edited/small/003.out and further edits are saved there

NOTE: ADDING DOES NOT WORK DO NOT TRY IT UNLESS NOT ZOOMED

Python Instructions

Requirements

A Python skeleton is available in the python subdirectory. The Python skeleton was developed using Python 3.9, but it should work with Python versions 3.6+.

Usage

Generating instances

To generate instances, read through python/instance.py, which contains a dataclass (struct) that holds the data for an instance, as well as other relevant methods. Then modify the python/generate.py file by filling in the make_{small,medium,large}_instance functions.

After you have filled in those functions, you can run make generate in the python directory to generate instances into the input directory.

To run unit tests, run make check.

Solving

We've created a solver skeleton at python/solve.py.

python3 solve.py case.in --solver=naive case.out

We've also created a skeleton that runs your solver on all cases and puts them in the output directory. To use it, modify python/solve_all.py to use your solver function(s). Then run

python3 python/solve_all.py inputs outputs

in the root directory.

Merging

To merge multiple output folders, taking the best solutions, see python/merge.py.

Visualizing Instances

To visualize problem instances, run python3 visualize.py, passing in the path to your .in file as the first argument (or - to read from standard input). To visualize a solution as well, pass in a .out file to the option --with-solution.

By default, the output visualization will be written as a SVG file to standard output. To redirect it to a file, use your shell's output redirection or pass in an output file as an additional argument.

For example, you could run

python3 visualize.py my_input.in out.svg

to create an out.svg file visualizing the my_input.in problem instance.

To visualize a solution file for this instance as well, you could run

python3 visualize.py my_input.in --with-solution my_soln.out out.svg