New answers tagged optimization
0
First, you need to understand how you are going to pick. That means, in one tote, do you want only one order or multiple items of different orders can end up into one tote. If it is latter, is there any sorting or consolidation area to separate out?
Is it like one order must go into one carton?
After we have those answers, I would always prefer first cubing ...
0
This problem is NP-hard as it can be seen by a reduction from $3$-partition.
In the $3$-partition problem we are given a (multi-)set $\mathcal{S}$ containing $3n$ positive integers $x_1, \dots, x_{3n}$ and the goal is that of deciding whether there exists a partition of $\mathcal{S}$ into $n$ sets $S_1, \dots, S_n$ of $3$ elements each, such that, for each $...
1
Here is a counterexample to your proposed algorithm:
The optimal solution consists of 3 edges and costs 3+1+1=5, but the min-cost maximum-cardinality matching, which consists of 2 edges and costs 3+3=6, will be chosen by the first step of your algorithm and immediately returned, as it is already a solution. (The only other maximum-cardinality matching costs ...
1
Let's start with an integer program for vertex cover:
\begin{align}
&\min \sum_{v \in V} x_v \\
\text{s.t.}\;\; & x_u + x_v \geq 1 &&\text{for every } (u,v) \in E \\
& x_v \in \{0,1\} &&\text{for every } v \in V
\end{align}
Here $V$ is the set of vertices and $E$ is the set of edges.
The optimal solution for this integer program ...
0
This kind of scheduling problem might fall within the area of operations research.
I would suggest using integer linear programming. You can formulate this as an instance of ILP, and then solve with an off-the-shelf ILP solver (e.g., Gurobi or CPLEX).
I'll outline a way you could formulate this as an instance of ILP. We'll let $\ell$ range over locations, $...
4
This problem is NP-hard: it is at least as hard as independent set. In particular, if you want to know whether there exists an independent set of size $N$, ask for a coloring with as many colors of size $N$; if you find any coloring where a single color occurs $N$ times, you know there's an independent set of size $N$. So, you should not expect any ...
1
If we focus solely on the dispensing operation, we can formulate this as a Set Cover Problem. Namely, we are given a set of tips that have already aspirated some source liquids and we are asked to minimze the number of dispense operations to fill up a given column of target vials. In this simplified set up, we aren't allowed to go back and aspirate new ...
0
One approach would be to view this as an operations research problem, where you have a scheduling problem with a bunch of constraints. A plausible approach would be to formulate this as an integer linear programming problem (or an instance of SAT), then solve using an off-the-shelf solver.
This reminds a bit of job shop scheduling, where you are minimizing ...
2
Your problem is NP-hard. Given an instance $T_1,\ldots,T_n$ of Maximum Coverage, let $x_1,\ldots,x_n$ be new variables, and create an instance $S_1,\ldots,S_n$ of your problem, where $S_i = T_i \cup \{x_i\}$. We have
$$
\left| \bigcup_{i \in I} S_i \right| -|I| = \left| \bigcup_{i \in I} T_i \right|.
$$
On the positive side, consider the following greedy ...
2
One systematic way to analyze these problems is to rewrite the function in continuation-passing style. For our purposes this means that the function takes an extra argument which is another function describing the postprocessing that is to be applied to the returned value. Your third function F in continuation-passing style would look like
fn F(x, k):
if p(...
Top 50 recent answers are included
