Efficient way to create master-detail records

You're doing it right, you will need to create the Master records first before attempting to create the child records.

You have a couple of options :

Using the External Id : You can use the Invoice_Id__c to hook up to the parent. Here's an example , where you instantiate an instance of the parent, setting the External Id on it, and then just set that reference on the child record. You can then upsert the child records.

An important consideration is "When batch updating multiple records where the external ID is the same for two or more records in your batch call, those records will be marked as errors in the UpsertResult file. The records will be neither created or updated."

Using the Salesforce Id : If the upsert of the parent records has been successful, you will be able to get the Id from each element in the Upsert Result, using the getId() method.

I'm guessing Invoice_Id__c is the external id that you're using to upsert and will be available on both the parent and child records, to establish the relationship.

You could add all the child records to a Map <Invoice_Id__c, List<InvoiceLineItem>>

After successful upsert of parent, iterate through the UpsertResult, grabbing the relevant parent node and set the resulting id on all the child InvoiceLineItems in that list corresponding to that parent Id.

What I would do in your situation is create a custom webservice method that would allow me to insert the data in one API request. What you could do is create a wrapper class that contains the Invoice and and array of the Invoice Line Items that you pass into this method. Then, in the implementation of the webservice method, you could handle first inserting the Invoice, then associating the line items to that invoice using the relationship fields and then inserting those.

Pseudo-ish Example:

global class MyInvoiceClass {

  webservice static Boolean insertInvoices(InvoiceWrapper[] invoices) {
    // insert invoices
    // insert line items 
    return true; // or false if there is a problem
  }

  global class InvoiceWrapper {
    webservice Invoice__c invoice;
    webservice Invoice_Line__c[] invoiceLines;
  }

}

This methodology allows you to reduce the api requests to 1 call and handle all of the implementation on the server side.