Come usare programmazione con vincoli per ottimizzare cestini per la spesa?

Question

Ho un elenco di elementi che voglio comprare. Gli articoli sono offerti da diversi negozi e prezzi diversi. I negozi hanno costi di consegna individuali. Sto cercando una strategia ottimale di shopping (e una libreria Java che lo sostengono) per l'acquisto di tutti gli elementi con un prezzo totale minimo.

Esempio:

• Item1 è offerto a Shop1 per $ 100, a shop2 a $ 111.
• Item2 è offerto a Shop1 per $ 90, a shop2 per $ 85.
• Costo di consegna di Shop1: $ 10 se ordine totale <$ 150; $ 0 altrimenti
• Costo di consegna di shop2: $ 5 Se ordine totale <$ 50; $ 0 altrimenti

• Se compro Item1 e Item2 al Shop1 il costo totale è di $ 100 + $ 90 + $ 0 = $ 190.
• Se compro Item1 e Item2 al shop2 il costo totale è di $ 111 + $ 85 + $ 0 = $ 196.
• Se compro Item1 a Shop1 e Item2 al shop2 il costo totale è di $ 100 + $ 10 + $ 85 + $ 0 = 195.

ottengo il prezzo minimo se ordino Item1 e Item2 a Shop1: $ 190

Quello che ho provato finora

un'altra domanda prima che mi ha portato a campo della programmazione con vincoli. Ho dato un'occhiata al crema e Choco , ma non ho capire come creare un modello per risolvere il mio problema.

         | shop1 | shop2 | shop3 | ...
-----------------------------------------
item1    | p11   | p12   | p13   |
item2    | p21   | p22   | p23   |
 .       |       |       |       |
 .       |       |       |       |
-----------------------------------------
shipping | s1    | s2    | s3    |
limit    | l1    | l2    | l3    |
-----------------------------------------
total    | t1    | t2    | t3    |
-----------------------------------------

La mia idea era quella di definire questi vincoli:

• ogni prezzo "p xy " è definito nel dominio (0, c) dove c è il prezzo del prodotto in questo negozio
• un solo prezzo in linea dovrebbe essere diverso da zero
• se uno o più elementi vengono acquistati da un negozio e la somma dei prezzi è inferiore al limite, quindi aggiungere costo per il costo di trasporto totale
• negozio costo totale è la somma dei prezzi di tutti gli elementi in un negozio
• costo totale è la somma di tutti i totali negozio

L'obiettivo è "costo totale". Voglio minimizzare questo.

In crema non è stato in grado di esprimere il vincolo "se allora" dei costi di trasporto condizionali.

In Choco esistono questi vincoli, ma anche per i 5 articoli e 10 negozi Attivi per 10 minuti senza trovare una soluzione.

Domanda

Come dovrei esprimere i miei vincoli per rendere questo problema risolvibile per un risolutore programmazione a vincoli?

Answer 1

Ho implementato questo problema in MiniZinc (un vincolo di alto livello linguaggio di programmazione): shopping_basket.mzn . E 'abbastanza avanti e forse potrebbe essere utilizzato come modello per il vostro modello di Java.

Per il modello Choco, hai provato diverse strategie di ricerca? Una diversa strategia può essere più veloce.

A proposito, un altro Java programmazione a vincoli risolutore si consiglia di verificare è Jacop .

Answer 2

Cosa si sta chiedendo è di circa, in sostanza, il k-zaino problema . La pagina di wikipedia mi piaceva ha una ricchezza di risorse sulle soluzioni per esso. Il problema è comunque NP-completo per risolvere in interezza, così che cosa si potrebbe desiderare di fare è cercare una stretta al meglio soluzione attraverso simulato ricottura o altre forme per la ricerca attraverso lo spazio problema.

La prima cosa da ricordare è che nei problemi di vincolo è probabile che finiscono per prendere un buon pezzo di tempo per generare una soluzione. Nel tuo esempio precedente, anche se cinque articoli e negozi dieci sembra piccolo che, in realtà, genera un grande problema di spazio (dell'ordine di 1E5 esclusa la complicazione del pricing condizionale che ha ulteriormente engrosses il problema).

I vincoli sul problema sono che si acquista uno di ogni elemento. L'obiettivo è il prezzo minimo. Penso che quello che hai è abbastanza buona, anche se non sono troppo sicuro di punti elenco uno e due.

  

ogni prezzo "p xy" è definito nel dominio (0, c) dove c è il prezzo del prodotto in questo negozio

   

soltanto un prezzo in linea dovrebbe essere non

nullo

vorrei prendere in considerazione ammortizzare la spedizione il costo degli articoli acquistati anziché aggiungerlo come un valore complessivo quando si fa i calcoli.

Answer 3

Io non sono troppo sicuro che questo è un problema k-zaino. La domanda ha menzionato le parole "Shopping canestri", ma non ha specificato la capacità di un determinato carico. Se è stata specificata una dimensione massima della spedizione, quindi il problema inizia a cercare più come un problema di zaino.

Il problema è in realtà solo un problema di base del flusso di rete con costi transporation sugli archi ed i costi all'origine. Perché si ha una chiara funzione obiettivo - ridurre al minimo il trasporto + costo del prodotto e perché non v'è probabile che sia una sola soluzione, CP non può essere l'approccio migliore.

Si consideri risolvere come problema di programmazione lineare:

Min: costi di trasporto + del prodotto

ST: prodotto totale spedito> = richiesta (per ogni prodotto)

Potrebbe essere necessario sviluppare alcune lineare a tratti equazioni per il costo del trasporto, ma questo non dovrebbe essere un problema.