Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

Filter by
Sorted by
Tagged with
3
votes
0answers
39 views

Extract binary value from continuous variable [duplicate]

I have a continuous variable $c$ which has value in between $[-R, +R]$. I want to create a boolean variable $x$ and, $x = 1$ when $c = 1.0$ otherwise $x = 0$ In more general form: $x = 1$ when $c \...
6
votes
0answers
77 views

Benefits of removing slack variables during presolve

I was reading Tobias Achterberg's thesis, and on page 138 he mentions the following presolving technique for linear equations (I'm slightly paraphrasing Example 10.2): Consider the equation $4x_1+...
9
votes
4answers
996 views

Open Source MILP software for Python with user-friendly API to define the optimization problem

Following the accepted answer to Assignment problem where assignments must be done sequentially I would like to write a Python script which can solve the problem defined there. It's a Mixed Integer ...
4
votes
0answers
64 views

Continue on “Is there a known MILP to schedule routes after routes are made”

I have made some progress on my previous question (Is there a known MILP to schedule routes after routes are made). I have derived the sets of the problem, which are: 1) Itineraries of vehicle: $i \in ...
6
votes
1answer
150 views

How to propagate time using linear inequalities?

I have an adjacency matrix $G_{i,j}$ that tells the distance between $i$ to $j$ (between 0 to 1) if there is no edge between $i$ to $j$ I am putting a large integer $100$. This is my previous ...
7
votes
1answer
164 views

Is Dantzig-Wolfe decomposition finite if variables are unbounded?

Most descriptions of the Dantzig-Wolfe decomposition, I have seen end up with subproblems like this: $$\min_{x_j \in \mathbb{R}^n} \{ (\pi A_j - c_j)x_j \mid x_j \in P_j \}$$ They argue that $P_j$ ...
12
votes
1answer
107 views

Improving cuts from sub-problem with problem-specific hierarchical information

I'm solving an assignment-alike problem with a Logic-based Benders decomposition-alike (LBBD) method. The master problem provides an assignment, which is checked in the sub-problem. Define the set of ...
8
votes
2answers
133 views

Bounding arrival time at a node in a resource-constrained shortest path problem

Given a city map (a graph) $G$, $b_{i,j}$ is a Boolean variable for whether or not edge $i$,$j$ is allocated, $d_{i,j}$ denotes the distance between $i$,$j$. The objective is to move from $s$ to $e$ ...
6
votes
1answer
77 views

Linearizing objective function with absolute differences

I want to turn this objective function $$\max \sum_{i=1}^{N-1} \sum_{j=i+1}^N |TX_i^T - TX_j^T|$$ where $T$ is just a vector with increasing integers (e.g $[1 \ 2]$) and $X_i$ is a vector ...
5
votes
1answer
154 views

How to model shipment size constraint?

I am working on an LP problem where I have to model a constraint as: "The total number of units of product A and B should be shipped in multiples of $1200$" e.g. $700\text{(product A)} + 500\text{(...
4
votes
0answers
163 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 ...
5
votes
4answers
201 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 ...
5
votes
1answer
205 views

How to express this constraint?

I have the constraint \begin{align}\max&\quad\gamma\\\text{s.t.}&\quad a\ge\gamma b\\&\quad\gamma\le 1\end{align} where $\gamma$ is an optimization variable and $a$ is a function of some ...
6
votes
1answer
202 views

GUROBI Re-optimize a model

(For Linear Programming) I am aware of CPLEX's reoptimize methods. If I am not wrong, if you solve a problem and after that you add a new constraint, then you can call the reoptimize method for not to ...
4
votes
1answer
413 views

CPLEX Python API

I am trying to run the following optimization problem at Python by using the CPLEX API: $$\min \{x_1 + x_2\ | \ x_1 \geq 3, x_2 \geq 2, 2x_1 + x_2 \geq 9\} $$ I just want to give a matrix of ...
10
votes
1answer
267 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 ...
8
votes
1answer
240 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 ...
7
votes
2answers
298 views

shadow prices associated with nonnegativity constraints

Why are shadow prices associated with nonnegativity constraints also called as reduced costs, even if they have the same interpretation as shadow prices associated with an optimal solution? Why the ...
13
votes
1answer
293 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 ...
7
votes
0answers
69 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
2answers
271 views

Max flow problem without splitting the flow from the supply nodes - LP formulation help

Since max flow formulation can be easily solved using LP, I wanted to ask the following: I am trying to solve a simple max flow problem where the graph is bipartite but with one added constraint. The ...
15
votes
2answers
252 views

Search approach to solve optimization problem with only a minimum where time series get scaled

Currently, I am working on a relatively simple optimization problem: There is a set of time series (red) that get summed up to a cumulated time series (blue). The red time series have different forms ...
10
votes
1answer
86 views

Variable Sensitivity Analysis

I am working with the following MIP : \begin{alignat}2\min&\quad\sum_{j\in J} c_j x_j\\\text{s.t.}&\quad l_j \le f(x_j,t_j) \le u_j \quad &\forall j \in J \\&\quad x_j \in \mathbb{N} \...
5
votes
3answers
1k views

Finding a solution to a linear program with a small number of zeros

It is known that, in a linear program with $k$ constraints, there exists a basic feasible solution in which at most $k$ variables are non-zero. How can I find such a solution? Is there a polynomial-...
13
votes
2answers
353 views

Black-box optimization with linear programming?

In my research, I do a black-box optimization based on a simulation model with nonlinear properties. The simulation model gets an operation plan for a time period and then returns a time series, which ...
8
votes
1answer
322 views

Is there any relationship between KKT and duality?

I noticed the similarities between KKT and complementary slackness, but I do not fully understand it.
3
votes
2answers
224 views

Find all Combinations of a Matrix

I have a $16\times11$ matrix and want to find all eligible* combinations of this matrix including always entities from all 11 columns. A simple example from a $2\times3$ matrix would be the following:...
9
votes
1answer
128 views

Introducing a big M variable in given equations

While I do understand the general workings of the Big-M-method I am struggling with the following sample exercise, in which the Big-M-method has to be used to find a first feasible solution: \begin{...
7
votes
1answer
163 views

Is this formulation linear or non-linear?

Can you help me figure out if this formulation constitutes a non-linear problem? I believe It is a linear problem but my solver (GAMS) is unable to produce a acceptable solution. $x,y$ and $\text{...
7
votes
2answers
150 views

Linear constraint formulation (OR-statement)

I have the decision variable $X_{iz}$ And I have two parameters $T_i\in\{0,1\}$ and $IT_z\in\{0,1,2\}$. I can only assign $i$ to $z$ if the following holds: for $T_i=0$, $IT_z$ needs to be $0$ or $2$...
8
votes
1answer
251 views

GLPK: meaning of the "marginal' column in the solution output

I'm using GLPK to solve an LP. I use it through its standalone solver, that I call with the glpsol command, and I get the solution detail written in a file using ...
17
votes
3answers
1k views

TSP with revenue maximization

How to approach a travelling salesman problem with an aim to maximize revenue at each town visited in a certain number of days (total number of towns is greater than what can be visited in the given ...
10
votes
2answers
193 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
0answers
74 views

What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
10
votes
1answer
428 views

Linear programming with if-then-else (big-M)

I am trying to formulate the following in linear programming. \begin{cases}\text{if}\,\,a>b\,\,\text{then}\,\,c=a\\\text{else}\,\,c=b.\end{cases} I tried some things with big $M$, like $$a + my &...
11
votes
2answers
926 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
1k 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 ...
10
votes
1answer
132 views

How to access neighboring extreme points to an optimal extreme point of an LP?

Suppose that I have access to an optimal non-degenerate extreme point of an LP. I need to find some $\epsilon$-optimal extreme points. That is, a point $x$ where $c'x \le z^{*} + \epsilon$. One way ...
9
votes
1answer
144 views

Finding Dual Objective

I have the following simplified optimization problem: \begin{align}\max &\quad ax+by\\\text{s.t.}&\quad0 \le x \le \overline X\\&\quad0 \le y \le\overline Y\\&\quad z = E-x+\beta\cdot ...
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,...
9
votes
2answers
156 views

Linear Programming: Objective function goodness if variable holds value above a given constant value

In a Linear Programming formulation, stating that a punishment is to be introduced in an objective minimization function if a variable $S$ holds a value above a given constant $K$ ($K = 35$ in the ...
8
votes
1answer
620 views

How to linearize the multiplication of an integer and a binary integer variable?

I have the following constraints \begin{align}\sum_{i=1}^{N}{x_it_i}&= M\\\sum_{i=1}^{N}{t_i}&\le S\end{align} where $x_i\ge 0$ is an integer variable, $t_i\in\{0,1\}$ is a binary variable ...
9
votes
2answers
135 views

Partial derivative of LP solution $(x_1 , \ldots, x_n)$ w.r.t. $x_i$ or $a_i$

Suppose I have an optimal solution and I want to know how the solution would (likely) change if one of the coefficients in the objective function changes, or if I add a constraint that forces $x_i$ ...
9
votes
1answer
165 views

Doubt on finding simplex's initial canonical tableau (II Phase)

Good day. Given the following notation for an initial canonical tableau for a linear program in standard form: $$ T_1 = \begin{bmatrix} I & B^{-1}N & \bar{x}_{B} \\ 0^\intercal & \hat{x}...
9
votes
1answer
1k views

Graphical method in linear programming

This page describes the graphical method to solve a linear program. The formulation is as follows. $$\begin{alignat}{2} \max &\quad Z = 200W + 100B\\ \text{s.t.} &\quad 1W + 0.8B &&\...
5
votes
0answers
33 views

In a binary logistic regression context, how to introduce a constraint to model the dependency between consecutive samples

Imagine we are running a logistic regression to identify opportunities for car sale promotion, using previous promotion campaign's result. Each $y$ is the increase of car sale after the promotion. ...
15
votes
1answer
552 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 ...
14
votes
4answers
277 views

Does this $0-1$ integer program have any speciality?

Given matrix $A \in \{0,1\}^{m \times n}$ and vector $b \in (\mathbb{Z^+})^m$, where $\mathbb{Z^+}$ is the set of positive integers, $$\begin{array}{ll} \text{maximize} & c^\top x\\ \text{subject ...
6
votes
1answer
292 views

Network flow model - How can I turn this diagram into a matrix that when converted to RREF solves for max flow?

I have the following network flow model diagram and I have already calculated maximum flow using the R package igraph to be 28. However, what I would like to know ...
9
votes
1answer
110 views

Constraint to state the relation between 2 binary variables

I'm trying to deal with a process planning and machine layout allocation simultaneously. I have the following variables: $X_p{_w}_{cj}=1$ if an operation $p$ is done by a machine $w$ with a ...

1
3 4
5
6 7