Questions tagged [mixed-integer-programming]

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

411 questions
Filter by
Sorted by
Tagged with
116 views

How to determine whether the solution is integer feasible in a CPLEX heuristic callback?

I am working with a MILP formulation of a routing problem using Concert CPLEX 12.10. And I am implementing a greedy heuristic that uses the variables fractional values to attempt to construct an ...
48 views

104 views

What kind of scheduling problem is this?

I am trying to develop algorithm to solve following basic version of the problem. 1) I would like to know what this problem is called in literature so that I can look it up 2) What are efficient ...
846 views

Non-constant expressions cannot be multiplied

I am trying to solve a valued n-queens problem, in which queens in black squares worth double of those in white squares. I solved it in AMPL just fine, but I would like to try that in Python using a ...
63 views

Complexity of determining whether a LP or MIP is infeasible

What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
1k views

Open source MILP solver for quick “good enough” solution

I have a problem that I have already posted elsewhere in OR.stack, but the question is focused around a large binary MILP (about 1 million decision variables). Ultimately, I am more time constrained ...
191 views

2k views

Are valid inequalities worth the effort given modern solvers?

In Laurence Wolsey's Integer Programming[1], he presents a well-known procedure for deriving valid inequalities (VI) suitable for integer and mixed integer linear problems (see Section 8.3, and also ...
170 views

How to write quantity discount constraint?

In a simple transportation problem like below image, how to model a constraint for shipment discount e.g. if quantity transported from any origin to any destination is more than 100 unit then the ...
205 views

Nested set in OPL/CPLEX

I'm trying to solve a scheduling problem using OPL/CPLEX. In the model, there are nine tasks in which each task has its specific precedence. the precedence relationship is as follows: ...
94 views

Is working with equations in an MILP more efficient than working with inequaltities?

I have the following model \begin{align}\max&\quad B_{1} + B_{2}\\\text{s.t.}&\quad 0 \leq B_{1} \leq c_{1}\cdot Y_{1} \\&\quad 0 \leq B_{2} \leq c_{2}\cdot Y_{2} \\&\quad \end{align} ...
118 views

179 views

69 views

Adding redundant inequality to a model

The following relationship is part of my optimization model ($W_k$ denotes a binary variable) $$W_{1} \le \cdots \le W_{k-1} \le W_{k} \le W_{k+1} \le \cdots \le W_{k^{\max}}$$ My question is, do ...
169 views

Modeling Linear Program to decide if an inequality is facet

Suppose you have a set of points $v_1,\ldots,v_n$, which are the vertices of the polytope $P=\operatorname{conv}\{v_1,\ldots,v_n\}$ and a linear inequality $a^\top v \leq b$. What would be a linear ...
246 views

Advanced Heuristics for MIP vehicle routing problem in PuLP

I am currently trying to speed up an MIP. An approach I was considering was to implement a cut callback heuristic with PuLP (one which rounds relaxed integer variables greater than .9 to 1). ...
239 views

Linearizing objective function with variables inside an indicator function

I am working on a problem in which I am trying to maximize the average of a variable only for the data that meet a certain condition with a constraint on the number of data that meet this condition. I ...
88 views

How to linearize difference of absolutes?

How to linearize difference of absolutes? $$|a|\ge k|b|$$ where $a,b$ are variables and $k$ is a constant.
84 views

How to design the objective function of an MILP problem

In an MILP problem, I wonder if it is better to use an objective function that involves as many of the variables of the problem as possible as opposed to an objective function with only a few ...
124 views

How to write a LP/MIP to mark the items in a time-series list after a fixed delta?

I have a time series list like this. ...
150 views

How to exploit known solution in MILP

I have an MILP model to which I get an integer feasible solution as a result of a heuristic search. In this particular example, the initial solution turns out to be the optimal solution, which I prove ...
98 views

Benders subproblem feasible region dependent upon solution master problem

Suppose I want to solve a naturally MINLP problem of the following form: $$\min_{x,y} \{c'x + y \mid Ax \leq b, Dx + Ey \leq f, G(x)y\leq g, x \in \mathbb{Z}, y \in \mathbb{R}^+\}$$ Here $G(x)$ ...
158 views

Find the cheapest shopping cart

Given a list of items to buy on an e-commerce, generate the cheapest possible cart (which obviously includes all the items). The items can be purchased from many sellers at different prices. Sellers ...
61 views

Integer variable optimization - decreasing execution time

I have a variable declared as follows in AMPL: ...
2k views

IF X = 0 THEN Y = 1, IF X > 0 THEN Y => 0

I'm trying to model the following IF $tS = 0$ THEN $Y = 1$, IF $tS \gt 0$ THEN $Y \ge 0$ $tS$ is a positive real number and $Y$ is binary. I tried the following: $tS - \epsilon \ge -M Y$ but ...