Questions tagged [mixed-integer-programming]

For questions about mathematical optimization problems involving both continuous and binary or general integer variables.

Filter by
Sorted by
Tagged with
4
votes
1answer
37 views

Expressing a chain of boolean if-then with logical ANDs using MIP

How to express a chain of boolean If-then as MIP such as: If $(x_{10} \ge b_1$ and $x_{11} \le b_1)$ AND $(x_{20} \ge b_2$ and $x_{21} \le b_2)$... AND... then $y_1 = 1$ else $y_1 = 0$. So basically,...
5
votes
0answers
46 views

Data Formulation for Mixed-Integer-Programming Models

Until now, I have used the Gurobi, CPLEX and OR-Tools (GCO) interface to formulate mixed-integer-programming models. Recently, I have discovered MiniZinc and want to utilize it to formulate big ...
4
votes
0answers
127 views

Publishing paper that uses LP solver to solve equation

I was reading this paper by Cerna et al. (2018)1. In the paper there are only CPLEX-solvable equations given by the authors and the results. How valuable is this paper, and what is its quality? Can ...
4
votes
4answers
172 views

MIP for similar production percentages in production planning

As a task, I want to produce three products $x,y,z$ in different quantities $a,b,c>0$ respectively. It is not always possible to produce the full amount of each product, because of a lack of ...
7
votes
1answer
138 views

Why is there a constant in the objective function of the *best subset selection problem*?

This article presents the following formulation of the best subset selection problem $$\min_{\|\beta\|_0\leq k}\frac{1}{2}\|y-X\beta\|^2_2$$ I wonder where the $1/2$ comes from. Help appreciated.
10
votes
1answer
75 views

CPLEX allows manually inserted solutions to violate lazy constraints

I am using CPLEX 12.9 to solve a mixed integer linear programming problem. Some of my constraints are enforced through a legacy LazyConstraintCallback. Heuristic solutions are inserted through a ...
10
votes
1answer
110 views

k-means/k-medoids Clustering Implementation in CPLEX Java

I am trying to model a grouping algorithm as k-means clustering problem, by referring to the general definition as mentioned in Wikipedia. In my system, I have $N$ nodes that I want to group in $m$ ...
8
votes
1answer
79 views

Complexity comparision between purely BLP and MILP problems?

Could someone please comment and answer on the complexity of purely binary linear programming (BLP) and mixed-integer linear programming (MILP)? In MILP, we have both binary and continuous variables ...
8
votes
1answer
78 views

How to remove or replace sub tour elimination constraints in the VRP variant models?

In many of vehicle routing problems variant (VRP), which can be formulated using MIPs, to avoid creating sub tour, we need to use sub tour elimination constraints (SEC). One of the known SEC is (I ...
5
votes
1answer
56 views

Interface for Cbc - COIN-OR

I would like to code some IP/MIP models in python and test them with an open-source solver. As of now, I only know the Cbc - COIN-OR open-source solver. I have already tried the or-tools interface, ...
11
votes
1answer
256 views

Metaheuristic to solve general MIPs

Many papers formulate their (NP-hard) problem as ILP or MILP and then show Cplex/Gurobi are unable to solve instances of a certain size. Then they introduce a meta-heuristic solution approach to solve ...
7
votes
1answer
224 views

Finding the optimal, spatially compact set of grid cells

I have a regular grid of cells, maybe square, maybe hexagonal. Each cell has a numeric value associated with it. How can I find a subset of cells that are: a connected, compact set and have an ...
10
votes
1answer
242 views

LP sum of variables that are above a threshold

I am trying to code a constraint of the form: $$\sum_i y_i < K\,\text{where}\,\begin{cases}y_i = x_i\quad\text{if}\,x_i>k_i\\0\quad\text{otherwise}.\end{cases}$$ In other words, I want to ...
11
votes
0answers
123 views

Tools to implement branch-and-price algorithms

As far as I know, implementing a branch-and-price algorithm is a task far from trivial. However, there are tools such as SCIP or the BCP framework of COIN-OR that help implement such algorithms. I ...
5
votes
2answers
441 views

Integer programming problem

I have the following exercise: Stockco is considering four investments. Investment 1 will yield a net present value (NPV) of \$16,000; investment 2, an NPV of \$22,000; investment 3, an NPV of \$12,...
5
votes
1answer
91 views

How is Big M calculated?

Because of excessive pollution on the Momiss River, the state of Momiss is going to build pollution control stations. Three sites (1, 2, and 3) are under consideration. Momiss is interested in ...
6
votes
0answers
92 views

Cplex is stuck after root node relaxation solution

I am solving an MIP through Benders decomposition (coded both generic and legacy callback versions), by employing Java with Cplex 12.9. For some of the instances, Cplex is stuck for two hours (time ...
7
votes
2answers
224 views

How can I transform this MILP into an LP problem?

I have a MILP problem with one of the constraints is given below. Sometimes, even for a small-sized problem, the solver takes a very long time to find a solution. What could be an efficient ...
12
votes
2answers
125 views

Dual bounds of integer programming problems

I often read in papers when branch-and-X algorithms are used to solve mixed integer programming problems, that the lower bound (in the minimization case) obtained from solving a linear programming ...
14
votes
2answers
603 views

Obtaining optimality gaps when using hybrid exact-heuristic approaches to vehicle routing problems

I'm starting to read about column generation-based approaches to vehicle routing problems (VRP). Let's say that I want to solve very large instances of an intricate VRP, I'm not looking to always ...
8
votes
1answer
136 views

Speedup or Caching for a Multi-Iteration MIP problem

I'm solving an MIP: \begin{align}\mathrm{arg\,min}&\quad\sum\limits_{i}{x_i}\\\text{s.t.}&\quad A\,x\geq1,\end{align} where both the matrix $A$ and vector $x$ are boolean valued, and $A$ is ...
9
votes
1answer
253 views

Partial Relaxation

In the context of a larger optimization problem I realized that I am missing the skill to implement/exploit the following observation: In the problem I was faced with two related sets of indicator ...
12
votes
1answer
173 views

LP how to sum up positive free variables and negative free variables separately?

For an LP problem where $x_1,\dots,x_n$ are free variables (which may take positive or negative values), I want to bound the sums of $a_i\cdot x_i$ where $x_i>0$, and where $x_i<0$. I suspect ...
6
votes
0answers
54 views

Modelling a simple ordering problem to have balanced delivery days

Assuming that I should buy 50 items from 25 different vendors with pre-known delivery duration between 2-7 day for each, which day of a week should I place each order so that the delivery days be even ...
7
votes
0answers
68 views

Automatic detection of SOS variables and constraints

We've been working on a new feature for Octeract Engine, namely to automatically extract SOS structure from a model and then exploit it. While the literature is quite rich on what to do with SOS once ...
8
votes
0answers
83 views

For subset selection regression as a mixed integer program, how tightly should the bounding box be set?

When solving best subset regression as a mixed integer program, how do you decide how tightly to bound the range of values of the $X$ values? When the box is tight, the solver finds a solution ...
8
votes
3answers
370 views

Interval variables in MIP

In Constraint Programming it is possible to use interval variables to represent intervals of time during which something happens (see here), usable in scheduling problems, for example. Is there ...
10
votes
1answer
130 views

Linearization of the product of two real valued variables - Binary expansion approach

I want to minimize the following objective function: \begin{align}\min &\quad x\cdot y\\\text{s.t.}&\quad2 \le x \le 5\\&\quad5 \le y \le 10.\end{align} Since the objective function is ...
10
votes
3answers
698 views

Do solvers use GUB/SOS1 branching?

GUB/SOS1 branching is an old and well-known idea (see for example page 9 of Jeff Linderoth's notes). Is this implemented in commercial solvers these days? The Gurobi documentation mentions SOS1 ...
10
votes
2answers
119 views

Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint

I have a MIP minimization problem where I have a maximization in the constraints: $$\max(c_1x_2,\, c_2x_2,\, \ldots,\, c_nx_n) \geq q$$ Where: $c_n$ constants $x_n$ binary variables $q$ constant $...
9
votes
1answer
70 views

MIP: If integer variable $>0$ it should be equal to other integer variables $>0$

I have an MIP problem where $n$ different types of cars are delivering packages. Sometimes multiple types of cars are required to go to a single location. For example if car $1$ makes two deliveries ...
10
votes
2answers
197 views

MILP: is it NP-complete or NP-hard?

The pieces of information I get online are sometimes confusing. Someone says MILP problems are NP-hard, and somewhere else I found the claim that MILP problems are NP-complete. Can someone please ...
8
votes
2answers
421 views

Complexity of LP and MILP Problems?

My original problem is an MILP. I make it an LP by relaxing the integer variables. Can someone please comment on the complexity, solvability and optimality of MILP and LP problems, in general? Is ...
6
votes
2answers
100 views

A heuristic approach to solve a MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. This one I posted here Is there a heuristic approach to the MILP problem? Since I have an additional but ...
13
votes
6answers
186 views

How to formulate: each pair of elements in $A$ has one common unit in $B$

We have two sets, $A$ and $B$. Some elements of $A$ must be connected to some elements of $B$, but no element of a given set is connected to another element of the same set. (Think of a bipartite ...
8
votes
2answers
374 views

Is there a greedy heuristic approach to the MILP problem?

I have the following optimization problem which is an MILP. I can solve it with an MILP solver. \begin{alignat}{1}\max_{x_n,t}\,&\quad t\quad\\\text{s.t.}&\quad\sum_{n=1}^{N} x_n \,&= M\\...
10
votes
3answers
1k views

Is there a heuristic approach to the MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. \begin{align}\min_t&\quad t\\\text{s.t.}&\quad d_{c}-t\le \sum_{n=1}^{N} B_{n,c}x_{n}\le d_{c}+t,...
10
votes
2answers
286 views

How difficult is it to understand a Machine Learning method based on integer optimization?

I'm trying to understand a paper called "Supersparse Linear Integer Models for Predictive Scoring Systems" by Ustun, Tracà and Rudin, who introduce a really interesting method for generating an ...
10
votes
1answer
84 views

Wild oscillation of dual infeasibility in Gurobi mixed-integer solver

As the question says, I am wondering what happens "behind the scene" when the Dual Infeasibility column of the Gurobi runtime log oscillates wildly, before Gurobi eventually quits with infeasibility. ...
9
votes
2answers
554 views

How to use warm start to solve MIPs efficiently?

I'm working on the scheduling model which takes a long time to solve to optimality (even for a small instance), therefore I would like to use a warm start (MIP start) to solve the problem. I'm using ...
9
votes
3answers
681 views

Modeling the Choose function

In statistics, one often encounters the choose function ${x \choose y}$ which encodes the number of ways of choosing $y$ items from a set of $x$ items. How would one go about modeling a choose ...
12
votes
1answer
154 views

If-then constraints in MIP programming

For continuous variables $x$ and $y$, the constraints are: ...
9
votes
2answers
140 views

How to formulate a MIP that can minimize the costs with a combination of subsets given a set?

I am trying to solve the following problem. I have a set $\{1,2,3\}$, which gives the following subsets with its costs: $\{1\}=8$, $\{2\}=9$, $\{3\}=7$, $\{1,2\}=9$, $\{1,3\}=18$, $\{2,3\}=15$ and $\{...
7
votes
1answer
148 views

Logical Constraints Modelling using Big-M formulation

I am trying to model some logical constraints in ILOG. Logical constraints could be given such as: Constraint 1 or Constraint 2, Constraint 3 or Constraint 4, Constraint 5 or Constraint 6. The ...
8
votes
0answers
107 views

Solving large-scale stochastic mixed integer program

What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the ...
8
votes
3answers
366 views

Linearization of a scheduling objective function

I am trying to maximize the workload per employee. An example: $e$ the index of an employee $j$ the index of a project decision variable: $x_{e,j} \in \mathbb{Z}$ and $0 \leq x_{e,j} \leq 100$ ...
14
votes
1answer
351 views

Duality in mixed integer linear programs

I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ...
8
votes
4answers
677 views

Modeling the Round (Nearest Integer) function

Modeling various non-differentiable functions is quite common knowledge including $\operatorname{abs}$, $\min$ and $\max$ functions. How would one go about modeling the nearest integer function, say ...
9
votes
1answer
199 views

Should I factor in time as a parameter or a variable in a scheduling problem with MILP?

I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed. To keep the information confidential, I will refer to my tasks as papers that need to be written....
10
votes
3answers
128 views

Theoretical results on performance of branch-and-bound

Are there any theoretical results on the performance of branch-and-bound, even for a subset of instances of a particular discrete optimization problem? As an example, does there exist a result of ...