2
$\begingroup$

I have two variables $a$ and $b$, in which $a$ is the amount of goods and $b$ is the amount of boxes of the given sizes. So $b$ (box size + number) is dependent on a (goods quantity). If $a$ is allocated to a given path, then $b$ will increase based on $a$, based on a rule to increase the number of boxes and select the best size.

The objective is to minimize the total cost of using boxes for all paths (i.e. tells the proportion of $a$ that is allocated to path_1, path_2, path_n, where the combined cost (spending on boxes) is minimal.)

Problem: How to express the relationship between $a$ and $b$ in the model? Should I model their dependency in the objective function or in the constraint? If constraint, how to describe such a relationship?

$\endgroup$

2 Answers 2

2
$\begingroup$

We need to make $n$ deliveries. Each delivery $i$ has $a_i$ units of a single product to be delivered. We have $m$ box types. Each box of type $j$ costs $c_j$ and it can hold $s_j$ units of the product. We would like to minimize the total cost of boxes used.

Decision variable $b_{ij}$ denotes the number of boxes of type $j$ used in delivery $i$.

Corresponding math programming model is as follows \begin{array}{rrll} \min & \sum_{ij} c_i b_{ij} \\ \text{s.t.} & \sum_j s_j b_{ij} & \geq a_i &\forall i \in {1, \ldots, n} \\ & b_{ij} &\geq 0 , \text{integer} & \forall i \in {1, \ldots, n}, j \in {1, \ldots, m} \end{array}

The first constraint ensures we use the correct number of boxes, while the objective ensures we use them in a cost efficient manner.

$\endgroup$
1
$\begingroup$

You should model this using a set of constraints. Off the cuff you could try this:

\begin{equation} \begin{array}{ll} \text{minimize} & \sum_{i} c_ib_i \\ \text{subject to} & a \leq A_i \rightarrow b_i = n_i \end{array} \end{equation}

where $A_i$ is meant to be the path allocation and $n_i$ the number of boxes assigned. The $\rightarrow$ constraint is called an indicator constraint, and most modern MIP solvers support it. I would start with this.

$\endgroup$
6
  • $\begingroup$ many thanks. could you take a look at a fuller problem description with data is here: or.stackexchange.com/questions/5980/… $\endgroup$
    – Jack
    Mar 24, 2021 at 7:37
  • $\begingroup$ is indicator constraint = Channeling constraints? is this "If-Then-Else expressions" an implementation of what you say to model the relationship between a and b? github.com/google/or-tools/blob/master/ortools/sat/doc/… $\endgroup$
    – Jack
    Mar 24, 2021 at 7:59
  • $\begingroup$ Indicator constraints are essentially an "If-Then" implementation, see also here: or.stackexchange.com/questions/4367/… $\endgroup$
    – Richard
    Mar 24, 2021 at 8:51
  • 2
    $\begingroup$ $a \leq A_i \rightarrow b_i = n_i$ is not really an indicator constraint. Indicator constraints have the form $\delta=0 \text{ (or 1)} \Rightarrow \text{linear constraint}$ (where $\delta$ is a binary variable, a.k.a. indicator variable). $\endgroup$ Mar 25, 2021 at 0:29
  • $\begingroup$ @Erwin Kalvelagen any thought? $\endgroup$
    – Jack
    Mar 25, 2021 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.