I was facing the same issue during developing a search window for inventory. I also had searched a lot on web but no success. I had tackled this problem as below.
Following is the window for my search:

Here you can see that there are 6 comboboxes and each have four options like:
<ComboBoxItem IsSelected="True">Contains</ComboBoxItem>
<ComboBoxItem>Does Not Contain</ComboBoxItem>
<ComboBoxItem>Begins With</ComboBoxItem>
<ComboBoxItem>Ends With</ComboBoxItem>
I had solved this problem by storing the selection and value in list as:
public class FilterList
{
public string combobox { get; set; }
public string value { get; set; }
}
On search button click:
List<FilterList> filter = new List<FilterList>();
filter.Add(new FilterList { combobox = cmbPart.Text, value = txtPart.Text });
filter.Add(new FilterList { combobox = cmbDescription.Text, value = txtDescription.Text });
filter.Add(new FilterList { combobox = cmbVendor.Text, value = txtVendor.Text });
filter.Add(new FilterList { combobox = cmbVendorPart.Text, value = txtVendorPart.Text });
filter.Add(new FilterList { combobox = cmbManufacture.Text, value = txtManufacture.Text });
filter.Add(new FilterList { combobox = cmbManuPartNumber.Text, value = txtManuPartNumber.Text });
Now in list i am having all the searched criteria with value. Now i have to filter record from database. For this first i am selecting all records from database, then using switch according to list items like:
if (!string.IsNullOrEmpty(filter[0].value))
{
switch (filter[0].combobox)
{
case "Contains":
break;
case "Does Not Contain":
break;
}}
if (!string.IsNullOrEmpty(filter[1].value))
{
switch (filter[1].combobox)
{
case "Contains":
//code
}}
in cases you can use different queries on the list which had got from database.
Overall you can say it is impossible to create runtime query in linq as we can do in sql.
Hope this will help you.